login
Number of parallelogram polyominoes with n cells (also called staircase polyominoes, although that term is overused).
(Formerly M1175)
33

%I M1175 #146 Oct 14 2024 12:17:57

%S 1,2,4,9,20,46,105,242,557,1285,2964,6842,15793,36463,84187,194388,

%T 448847,1036426,2393208,5526198,12760671,29466050,68041019,157115917,

%U 362802072,837759792,1934502740,4467033943,10314998977,23818760154,55000815222,127004500762

%N Number of parallelogram polyominoes with n cells (also called staircase polyominoes, although that term is overused).

%C Same as: number of skew Ferrers diagrams. - _Joerg Arndt_, Mar 18 2014

%C 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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Seiichi Manyama, <a href="/A006958/b006958.txt">Table of n, a(n) for n = 1..2752</a> (terms 1..1000 from Robert Israel)

%H Abderrahim Arabi, Hacène Belbachir, and Jean-Philippe Dubernard, <a href="https://arxiv.org/abs/2105.00971">Enumeration of parallelogram polycubes</a>, arXiv:2105.00971 [cs.DM], 2021.

%H Peter Bala, <a href="/A006958/a006958_1.pdf">Illustration for the initial terms of the sequence</a>

%H Peter Bala, <a href="/A161492/a161492_1.pdf">Fountains of coins and skew Ferrers diagrams</a>

%H E. A. Bender, <a href="http://dx.doi.org/10.1016/0012-365X(74)90134-4">Convex n-ominoes</a>, Discrete Math., 8 (1974), 219-226.

%H M. P. Delest, J. M. Fedou, <a href="http://dx.doi.org/10.1016/0012-365X(93)90224-H">Enumeration of skew Ferrers diagrams</a>, Discrete Mathematics, vol. 112 (1993), no. 1-3, pp. 65-79.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.

%H P. Flajolet, <a href="/A006958/a006958.pdf">Email to N. J. A. Sloane & S. Plouffe, Aug. 1991</a>

%H P. Flajolet, <a href="https://hal.inria.fr/inria-00075055">Polya Festoons</a>, INRIA Research Report, No 1507, September 1991. 6pp.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 661.

%H Atli Fannar Franklín, <a href="https://arxiv.org/abs/2410.07467">Pattern avoidance enumerated by inversions</a>, arXiv:2410.07467 [math.CO], 2024. See pp. 2, 4-5.

%H Atli Fannar Franklín, Anders Claesson, Christian Bean, Henning Úlfarsson, and Jay Pantone, <a href="https://arxiv.org/abs/2406.16403">Restricted Permutations Enumerated by Inversions</a>, arXiv:2406.16403 [cs.DM], 2024. See p. 2.

%H D. Gouyou-Beauchamps and P. Leroux, <a href="https://arxiv.org/abs/math/0403168">Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice</a>, arXiv:math/0403168 [math.CO], 2004.

%H D. A. Klarner and R. L. Rivest, <a href="https://doi.org/10.1016/0012-365X(74)90107-1">Asymptotic bounds for the number of convex n-ominoes</a>, Discrete Math., 8 (1974), 31-40.

%F 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

%F 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

%F 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

%F 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

%F a(n) ~ c * d^n, where d = A276994 = 2.309138593330494731098720305017212531911814472581628401694402900284456440748..., c = 0.29745350581112195107675842441785013227507248969090226252518932405713367... . - _Vaclav Kotesovec_, Sep 21 2016

%F From _Peter Bala_, Jul 21 2019: (Start)

%F 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.

%F The constant d = 2.30913... in the above asymptotic formula is a zero of D(q) (as is 1/d).

%F Continued fraction representations for the o.g.f.:

%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) - (...) ))))).

%F 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/( (...) ))))).

%F 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)

%e 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 + ...

%e From _Michael B. Porter_, Sep 21 2016; corrected by _Riccardo Moschetti_, Aug 11 2017: (Start)

%e 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:

%e _ _ _

%e _ _ _ /_ / /_ /_ /

%e _ /_ /_ / /_ /_ / /_ / _ _ _ _

%e /_ /_ / /_ / /_ / /_ /_ /_ /_ /

%e _

%e _ /_ / _ _ _ _ _

%e /_ / /_ / /_ /_ /_ / _ /_ /_ /

%e _ /_ / /_ / /_ / _ _ /_ / /_ /_ /

%e /_ /_ / /_ / /_ /_ /_ /

%e (End)

%p N:= 100: # to get a(1) to a(N)

%p M:= ceil(sqrt(N+1)):

%p C:= 1:

%p for j from M to 1 by -1 do C:= 1/(1-x^j/(1-x^j*C)) od:

%p S:= series(C,x,N+1):

%p seq(coeff(S,x,j),j=1..N); # _Robert Israel_, Sep 20 2016

%t 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 *)

%t 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 *)

%o (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

%o (PARI) /* From the Delest/Fedou reference: */

%o N=44; q='q+O('q^N); t=1;

%o qn(n) = prod(k=1, n, 1-q^k );

%o nm = sum(n=0, N, (-1)^n* q^(n*(n+1)/2) / ( qn(n) * qn(n+1) ) * (t*q)^(n+1) );

%o dn = sum(n=0, N, (-1)^n* q^(n*(n-1)/2) / ( qn(n)^2 ) * (t*q)^n );

%o Vec(nm/dn) \\ _Joerg Arndt_, Mar 18 2014

%Y Cf. A075125, A276994, A275761, A275762, A161492.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_, _Simon Plouffe_

%E More terms from _Paul D. Hanna_, May 14 2005

%E Definition modified by _Don Knuth_, Sep 20 2016