|
| |
|
|
A006958
|
|
Number of parallelogram polyominoes with n cells (also called staircase polyominoes, although that term is overused).
(Formerly M1175)
|
|
33
|
|
|
|
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, 55000815222, 127004500762
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Same as: number of skew Ferrers diagrams. - Joerg Arndt, Mar 18 2014
A coin fountain is an arrangement of coins in numbered rows such that the bottom row (row 0) contains contiguous coins and such that each coin in a higher row touches exactly two coins in the next lower row. See A005169. a(n) equals the number of coin fountains with exactly n coins in the even-numbered rows of the fountain. See the illustration in the Links section. See A161492 for a refinement of this sequence. - Peter Bala, Jul 20 2019
|
|
|
REFERENCES
|
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.
|
|
|
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, 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, May 14 2005
G.f.: 1/x/G(0) -1/x, where G(k)= 1 - x^(k+1)/(1 - x^(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Jun 29 2013
G.f.: W(0)/x - 1/x, where W(k) = 1 - x^(k+1)/( x^(k+1) - 1/(1 - x^(k+1)/( x^(k+1) - 1/W(k+1) ))); R=1 (continued fraction). - Sergei N. Gladkovskii, Aug 27 2013
a(n) ~ c * d^n, where d = A276994 = 2.309138593330494731098720305017212531911814472581628401694402900284456440748..., c = 0.29745350581112195107675842441785013227507248969090226252518932405713367... . - Vaclav Kotesovec, Sep 21 2016
O.g.f. as a ratio of q-series: 1 + A(q) = N(q)/D(q) = 1 + q + 2*q^2 + 4*q^3 + ..., where N(q) = Sum_{n >= 0} (-1)^n*q^((n^2 + 3*n)/2)/Product_{k = 1..n} (1 - q^k)^2 and D(q) = Sum_{n >= 0} (-1)^n*q^((n^2 + n)/2)/Product_{k = 1..n} (1 - q^k)^2.
The constant d = 2.30913... in the above asymptotic formula is a zero of D(q) (as is 1/d).
Continued fraction representations for the o.g.f.:
1 + A(q) = 1/(1 - q/(1 - q/(1 + q*(1 - q) - q/( 1 + q*(1 - q^2) - q/(1 + q*(1 - q^3) - (...) ))))).
1 + A(q) = 1/(1 - q - q^2/(1 - q*(1 + q) - q^4/(1 - q^2*(1 + q) - q^6/(1 - q^3(1 + q) - q^8/( (...) ))))).
1 + A(q) = 1/(1 - q - q^2/(1 - q^2 - q/(1 - q^3 - q^5/(1 - q^4 - q^2/(1 - q^5 - q^8/ (1 - q^6 - q^3/(1 - q^7 - q^11/(1 - q^8 - (...) )))))))). (End)
|
|
|
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 + ...
Here are the nine parallelogram polyominoes with 4 cells, i.e., polygons convex according to the -45-degree direction, according to "Polya Festoons" of P. Flajolet:
_ _ _
_ _ _ /_ / /_ /_ /
_ /_ /_ / /_ /_ / /_ / _ _ _ _
/_ /_ / /_ / /_ / /_ /_ /_ /_ /
_
_ /_ / _ _ _ _ _
/_ / /_ / /_ /_ /_ / _ /_ /_ /
_ /_ / /_ / /_ / _ _ /_ / /_ /_ /
/_ /_ / /_ / /_ /_ /_ /
(End)
|
|
|
MAPLE
|
N:= 100: # to get a(1) to a(N)
M:= ceil(sqrt(N+1)):
C:= 1:
for j from M to 1 by -1 do C:= 1/(1-x^j/(1-x^j*C)) od:
S:= series(C, x, N+1):
|
|
|
MATHEMATICA
|
NN = 100; (* to get a(1) to a(NN) *) M = Ceiling[Sqrt[NN+1]]; c = 1; For[j = M, j >= 1, j--, c = 1/(1-x^j/(1-x^j*c))]; c = Series[c, {x, 0, NN+1}]; CoefficientList[c, x][[2 ;; NN+1]] (* Jean-François Alcover, Sep 27 2016, adapted from Robert Israel's Maple code *)
nmax = 40; CoefficientList[Series[1/Fold[(1 - #2/#1) &, 1, Reverse[x^(Range[nmax + 1] - Floor[Range[nmax + 1]/2])]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Sep 05 2017 *)
|
|
|
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)} \\ Paul D. Hanna, May 14 2005
(PARI) /* From the Delest/Fedou reference: */
N=44; q='q+O('q^N); t=1;
qn(n) = prod(k=1, n, 1-q^k );
nm = sum(n=0, N, (-1)^n* q^(n*(n+1)/2) / ( qn(n) * qn(n+1) ) * (t*q)^(n+1) );
dn = sum(n=0, N, (-1)^n* q^(n*(n-1)/2) / ( qn(n)^2 ) * (t*q)^n );
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Definition modified by Don Knuth, Sep 20 2016
|
|
|
STATUS
|
approved
|
| |
|
|
