A121552 -id:A121552 - cp's OEIS frontend

A129178 Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that invc(p)=k (n >= 0; 0 <= k <= (n-1)(n-2)/2) (see comment for invc definition).

1, 1, 2, 4, 2, 8, 8, 6, 2, 16, 24, 28, 26, 16, 8, 2, 32, 64, 96, 120, 126, 110, 82, 52, 26, 10, 2, 64, 160, 288, 432, 564, 658, 680, 638, 542, 416, 284, 172, 90, 38, 12, 2, 128, 384, 800, 1376, 2072, 2824, 3526, 4058, 4344, 4346, 4066, 3562, 2912, 2218, 1566, 1016, 598

Offset: 0

Emeric Deutsch, Apr 11 2007

invc(p) is defined (by Carlitz) in the following way: express p in standard cycle form (i.e., cycles ordered by increasing smallest elements with each cycle written with its smallest element in the first position), then remove the parentheses and count the inversions in the obtained word.
Row n has 1+(n-1)*(n-2)/2 - delta_{0,n} terms. Row sums are the factorials (A000142). T(n,0) = 2^(n-1) = A011782(n) = A000079(n-1). T(n,1) = (n-2)*2^(n-2) = A036289(n-2) for n>=2. T(n,k) = A121552(n,n+k).
It appears that Sum_{k>=0} k*T(n,k) = A126673(n).

			T(3,0)=4, T(3,1)=2 because we have 123=(1)(2)(3), 132=(1)(23), 213=(12)(3), 231=(123) with the resulting word (namely 123) having 0 inversions and 312=(132) and (321)=(13)(2) with the resulting word (namely 132) having 1 inversion.
Triangle starts:
   1;
   1;
   2;
   4,   2;
   8,   8,   6,   2;
  16,  24,  28,  26,  16,   8,   2;
  32,  64,  96, 120, 126, 110,  82,  52,  26,  10,  2;
  ...

L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.

Alois P. Heinz, Rows n = 0..50, flattened
Toufik Mansour, Mark Shattuck, A q-analog of the hyperharmonic numbers, Afrika Matematika 25.1 (2014): 147-160.
M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

Cf. A000142, A011782, A000079, A036289, A121552, A126673.

s:=j->2+sum(t^i, i=1..j): for n from 0 to 9 do P[n]:=sort(expand(simplify(product(s(j), j=0..n-2)))) od: for n from 0 to 9 do seq(coeff(P[n], t, j), j=0..degree(P[n])) od;  # yields sequence in triangular form

nMax = 9; s[j_] := 2 + Sum[t^i, {i, 1, j}]; P[0] = P[1] = 1; P[2] = 2; For[ n = 3, n <= nMax, n++, P[n] = Sort[Expand[Simplify[Product[s[j], {j, 0, n-2}]]]]]; Table[Coefficient[P[n], t, j], {n, 0, nMax}, {j, 0, Exponent[ P[n], t]}] // Flatten (* Jean-François Alcover, Jan 24 2017, adapted from Maple *)

Generating polynomial of row n is P[n](t) = 2*(2+t)*(2+t+t^2)*...*(2 + t + t^2 + ... + t^(n-2)) for n >= 3, P[1](t)=1, P[2](t)=2.

One term for row n=0 prepended by Alois P. Heinz, Dec 16 2016

A121553 Total area of all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

Original entry on oeis.org

1, 4, 20, 122, 874, 7164, 65988, 674064, 7558416, 92276640, 1218255840, 17293495680, 262656570240, 4250077896960, 72992067321600, 1326101675673600, 25410150701107200, 512158576546713600, 10832221231772774400

Offset: 1

Emeric Deutsch, Aug 08 2006

nonn

a(n)=Sum(k*A121552(n,k), k=n..1+n(n-1)/2).

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

Cf. A121552.

a[1]:=1: for n from 2 to 22 do a[n]:=n*a[n-1]+(n-1)!*(1+n*(n-1)/2) od: seq(a[n],n=1..22);

a(1)=1; a(n)=n*a(n-1)+(n-1)!*[1+n(n-1)/2] for n>=2 (see Barcucci et al. reference, p. 34).
a(n)=n![n(n-1)/4 + 1/1 + 1/2 + ... +1/n]. - Emeric Deutsch, Apr 06 2008
Conjecture D-finite with recurrence a(n) +(-2*n-3)*a(n-1) +(n^2+4*n-3)*a(n-2) +2*(-n^2+n+3)*a(n-3) +2*(n-3)^2*a(n-4)=0. - R. J. Mathar, Jul 22 2022

A121691 Number of deco polyominoes of area n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

Original entry on oeis.org

1, 2, 4, 10, 24, 62, 158, 410, 1064, 2774, 7236, 18908, 49428, 129286, 338254, 885188, 2316766, 6064184, 15874084, 41555086, 108785772, 284792646, 745574864, 1951901064, 5110072712, 13378217392, 35024400076, 91694660704, 240059002292

Offset: 1

Emeric Deutsch, Aug 16 2006

nonn

Column sums of the triangle in A121552.

			a(2)=2 because the only deco polyominoes of area 2 are the vertical and horizontal dominoes.

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29- 42.

Cf. A121552.

P:=n->2*t^n*product(2+sum(t^i,i=1..j),j=1..n-2): g:=expand(simplify(sum(P(n),n=1..36))): seq(coeff(g,t,n),n=1..32);

G.f.=Sum(P(n,t), n=1..infinity), where P[n,t]=2t^n*product(2+sum(t^i, i=1..j), j=1..n-2) [in particular, P[1,t]=t; P[2,t]=2t^2; P[3,t]=2t^3*(2+t), P[4,t]=2t^4*(2+t)(2+t+t^2)].

cp's OEIS Frontend

A129178 Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that invc(p)=k (n >= 0; 0 <= k <= (n-1)(n-2)/2) (see comment for invc definition).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A121553 Total area of all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Maple

Formula

A121691 Number of deco polyominoes of area n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Formula