|
Search: id:A006958
|
|
|
| A006958 |
|
Number of staircase polyominoes with n cells. (Formerly M1175)
|
|
+0 1
|
|
| 1, 2, 4, 9, 20, 46, 105, 242, 557, 1285, 2964, 6842, 15793, 36463, 84187, 194388, 448847, 1036426, 2393208, 5526198, 12760671, 29466050, 68041019, 157115917, 362802072, 837759792, 1934502740, 4467033943, 10314998977, 23818760154
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
E. A. Bender, Convex n-ominoes, Discrete Math., 8 (1974), 219-226.
D. A. Klarner and R. L. Rivest, Asymptotic bounds for the number of convex n-ominoes, Discrete Math., 8 (1974), 31-40.
|
|
LINKS
|
P. Flajolet, Polya Festoons, INRIA Research Report, No 1507, September 1991. 6pp.
D. Gouyou-Beauchamps and P. Leroux, Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 661
|
|
FORMULA
|
G.f.: 1+A(x) = 1/(1-x/(1-x/(1-x^2/(1-x^2/(1-x^3/(1-x^3/(1-...)))))) (continued fraction). - Paul D. Hanna (pauldhanna(AT)juno.com), May 14 2005
The continued fraction given by P. Flajolet, "Polya Festoons", is derived from a q-expansion, C(x, y;q), where C(1, 1;q) = q/(1-2*q-q^3/(1-2*q^2-q^5/(1-2*q^3-q^7/(1-2*q^4-q^9/(1-...))))) = q + 2*q^2 + 4*q^3 + 9*q^4 + 20*q^5 + 46*q^6 + 105*q^7 +... - Paul D. Hanna (pauldhanna(AT)juno.com), May 14 2005
|
|
EXAMPLE
|
G.f. may be expressed by the continued fraction: 1/(1-x/(1-x/(1-x^2/(1-x^2/(1-x^3/(1-x^3/(1-x^4/(1-...))))))))) = 1 + x + 2*x^2 + 4*x^3 + 9*x^4 + 20*x^5 + 46*x^6 + 105*x^7 +...
|
|
MAPLE
|
n:=100: C11q:=1-2*q^n-q^(2*n+1): for i from n-1 by -1 to 1 do C11q:=1-2*q^i-q^(2*i+1)/C11q od:C11q:=q/C11q:seq(coeff(convert(series(C11q, q, 100), polynom), q, n), n=1..50); (Pab Ter)
|
|
PROGRAM
|
(PARI) {a(n)=local(CF=1+x*O(x^n), m); for(k=0, n\2, m=n\2-k+1; CF=(1-x^((m+1)\2)/CF)); polcoeff(1/CF, n)} (Hanna)
|
|
CROSSREFS
|
Sequence in context: A111099 A000632 A090245 this_sequence A036617 A007902 A057417
Adjacent sequences: A006955 A006956 A006957 this_sequence A006959 A006960 A006961
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe (simon.plouffe(AT)gmail.com)
|
|
EXTENSIONS
|
More terms from Paul D. Hanna (pauldhanna(AT)juno.com), May 14 2005
|
|
|
Search completed in 0.002 seconds
|