|
%I M1175 #136 May 04 2021 09:00:58
%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 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
| 