|
| |
|
|
A006958
|
|
Number of staircase polyominoes with n cells.
(Formerly M1175)
|
|
0
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
REFERENCES
| 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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
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)
|
|
|
MATHEMATICA
| n = 5; C11q = 1 - 2*q^n - q^(2*n + 1); Do[ C11q = 1 - 2*q^i - q^(2*i + 1)/C11q , {i, n - 1, 1, -1}]; Drop[ CoefficientList[ Series[q/C11q, {q, 0, 30}], q], 1] (* From Jean-François Alcover, Oct 05 2011, after Maple *)
|
|
|
PROG
| (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 * A036617 A007902 A057417
Adjacent sequences: A006955 A006956 A006957 * 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
|
| |
|
|
