A075125 -id:A075125 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane, Simon Plouffe

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

			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 + ...
From _Michael B. Porter_, Sep 21 2016; corrected by _Riccardo Moschetti_, Aug 11 2017: (Start)
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)

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.19, p. 380.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..2752 (terms 1..1000 from Robert Israel)
Abderrahim Arabi, Hacène Belbachir, and Jean-Philippe Dubernard, Enumeration of parallelogram polycubes, arXiv:2105.00971 [cs.DM], 2021.
Peter Bala, Illustration for the initial terms of the sequence.
Peter Bala, Fountains of coins and skew Ferrers diagrams.
E. A. Bender, Convex n-ominoes, Discrete Math., 8 (1974), 219-226.
M. P. Delest and J. M. Fedou, Enumeration of skew Ferrers diagrams, Discrete Mathematics, vol. 112 (1993), no. 1-3, pp. 65-79.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
P. Flajolet, Email to N. J. A. Sloane & S. Plouffe, Aug. 1991.
P. Flajolet, Polya Festoons, INRIA Research Report, No 1507, September 1991. 6pp.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 661.
Atli Fannar Franklín, Pattern avoidance enumerated by inversions, arXiv:2410.07467 [math.CO], 2024. See pp. 2, 4-5.
Atli Fannar Franklín, Anders Claesson, Christian Bean, Henning Úlfarsson, and Jay Pantone, Restricted Permutations Enumerated by Inversions, arXiv:2406.16403 [cs.DM], 2024. See p. 2.
D. Gouyou-Beauchamps and P. Leroux, Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice, arXiv:math/0403168 [math.CO], 2004.
D. A. Klarner and R. L. Rivest, Asymptotic bounds for the number of convex n-ominoes, Discrete Math., 8 (1974), 31-40.

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

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):
seq(coeff(S,x,j),j=1..N); # Robert Israel, Sep 20 2016

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

{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

/* 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 );
Vec(nm/dn)  \\ Joerg Arndt, Mar 18 2014

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
From Peter Bala, Jul 21 2019: (Start)
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)

More terms from Paul D. Hanna, May 14 2005

Definition modified by Don Knuth, Sep 20 2016

A075126 Number of bargraphs of site-perimeter n.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 2, 4, 8, 14, 26, 52, 97, 193, 377, 752, 1500, 3022, 6107, 12429, 25365, 52042, 107090, 221235, 458316, 952439, 1984262, 4144601, 8676232, 18202536, 38263456, 80585694, 170013976, 359277183, 760400787, 1611721413, 3420839200, 7270098883

Offset: 1

Andrew Rechnitzer (a.rechnitzer(AT)ms.unimelb.edu.au), Sep 09 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.

Cf. A075125.

Row sums of A274207.

b:= proc(n, y, t, w) option remember; `if`(n<0, 0, `if`(n=0, (1-t),
     `if`(t<0, 0, b(n-`if`(w>0 or t=0, 1, 2), y+1, 1, max(0, w-1)))+
     `if`(t>0 or y<2, 0, b(n, y-1, -1, `if`(t=0, 1, w+1)))+
     `if`(y<1, 0, b(n-`if`(t<0, 1, 2), y, 0, `if`(t<0, w, 0)))))
    end:
a:= n-> b(n, 0, 1, 0):
seq(a(n), n=1..45);  # Alois P. Heinz, Jun 05 2016

b[n_, y_, t_, w_] := b[n, y, t, w] = If[n<0, 0, If[n==0, 1-t, If[t<0, 0, b[n - If[w>0 || t==0, 1, 2], y+1, 1, Max[0, w-1]]] + If[t>0 || y<2, 0, b[n, y-1, -1, If[t==0, 1, w+1]]] + If[y<1, 0, b[n - If[t<0, 1, 2], y, 0, If[t<0, w, 0]]]]]; a[n_] := b[n, 0, 1, 0]; Table[a[n], {n, 1, 45}] (* Jean-François Alcover, Nov 28 2016 after Alois P. Heinz *)

The generating function is known in closed form. Closed, but complicated. It is proved to be non-D-finite.

Offset corrected by Alois P. Heinz, Jun 04 2016

a(31)-a(38) from Alois P. Heinz, Jun 05 2016

A166299 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having k UUDD's starting at level 0.

Original entry on oeis.org

1, 0, 0, 1, 1, 0, 1, 0, 1, 2, 2, 0, 5, 2, 0, 1, 10, 4, 3, 0, 22, 11, 3, 0, 1, 50, 22, 6, 4, 0, 113, 49, 18, 4, 0, 1, 260, 114, 36, 8, 5, 0, 605, 260, 81, 26, 5, 0, 1, 1418, 604, 193, 52, 10, 6, 0, 3350, 1419, 444, 118, 35, 6, 0, 1, 7967, 3350, 1041, 288, 70, 12, 7, 0, 19055, 7966

Offset: 0

Emeric Deutsch, Nov 07 2009

Sum of entries in row n is the secondary structure number A004148(n-1) (n>=2).
Number of entries in row n is 1 + floor(n/2).
T(n,0)=A166300(n).
Sum(k*T(n,k), k>=0)=A075125(n+2).

			T(7,2)=3 because we have (UUDD)(UUDD)UUUDDD, (UUDD)UUUDDD(UUDD), and UUUDDD(UUDD)(UUDD) (the UUDD's starting at level 0 are shown between parentheses).
Triangle starts:
1;
0;
0,1;
1,0;
1,0,1;
2,2,0;
5,2,0,1;
10,4,3,0;

Cf. A004148, A166300, A075125

G := 2/(1+z+z^2+sqrt((1+z+z^2)*(1-3*z+z^2))-2*t*z^2): Gser := simplify(series(G, z = 0, 18)): for n from 0 to 16 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 16 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

G.f.=G(t,z)=1/(1 + z - zg - tz^2), where g=g(z) satisfies g=1 + zg(g - 1 + z).
G.f. of column k is z^{2k}/(1 + z - zg)^{k+1} (k>=0).
G(t,z)=2/[1+z+z^2+sqrt((1+z+z^2)(1-3z+z^2)-2tz^2)].

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A075126 Number of bargraphs of site-perimeter n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A166299 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having k UUDD's starting at level 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula