A122105 -id:A122105 - cp's OEIS frontend

A350274 Triangle read by rows: T(n,k) is the number of n-permutations whose fourth-shortest cycle has length exactly k; n >= 0, 0 <= k <= max(0,n-3).

1, 1, 2, 6, 23, 1, 109, 1, 10, 619, 16, 45, 40, 4108, 92, 210, 420, 210, 31240, 771, 1645, 2800, 2520, 1344, 268028, 6883, 17325, 15960, 26460, 18144, 10080, 2562156, 68914, 173250, 148400, 226800, 211680, 151200, 86400, 27011016, 757934, 1854930, 1798720, 1801800, 2494800, 1940400, 1425600, 831600

Offset: 0

Steven Finch, Dec 22 2021

If the permutation has no fourth cycle, then its fourth-longest cycle is defined to have length 0.

			Triangle begins:
[0]      1;
[1]      1;
[2]      2;
[3]      6;
[4]     23,    1;
[5]    109,    1,    10;
[6]    619,   16,    45,    40;
[7]   4108,   92,   210,   420,   210;
[8]  31240,  771,  1645,  2800,  2520,  1344;
[9] 268028, 6883, 17325, 15960, 26460, 18144, 10080;
    ...

Alois P. Heinz, Rows n = 0..100, flattened
Steven Finch, Second best, Third worst, Fourth in line, arxiv:2202.07621 [math.CO], 2022.

Column 0 is 1 for n=0, together with A000142(n) - A122105(n-1) for n>=1.
Row sums give A000142.
Cf. A126074, A145877, A332908, A349979, A349980, A350015, A350016, A350273.

m:= infinity:
b:= proc(n, l) option remember; `if`(n=0, x^`if`(l[4]=m,
      0, l[4]), add(b(n-j, sort([l[], j])[1..4])
               *binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [m$4])):
seq(T(n), n=0..11);  # Alois P. Heinz, Dec 22 2021

m = Infinity;
b[n_, l_] := b[n, l] = If[n == 0, x^If[l[[4]] == m, 0, l[[4]]], Sum[b[n-j, Sort[Append[l, j]][[1 ;; 4]]]*Binomial[n-1, j-1]*(j-1)!, {j, 1, n}]];
T[n_] := With[{p = b[n, {m, m, m, m}]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
Table[T[n], {n, 0, 11}] // Flatten (* Jean-François Alcover, Dec 29 2021, after Alois P. Heinz *)

Sum_{k=0..n-3} k * T(n,k) = A332908(n) for n >= 4.

More terms from Alois P. Heinz, Dec 22 2021

A122104 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and such that the sum of the bottom levels of all columns is k (n>=1, k>=0; informally, the number of the "missing" cells in the right bottom corner of the polyomino). 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, 5, 1, 16, 5, 3, 65, 23, 20, 10, 2, 326, 119, 115, 84, 57, 11, 8, 1957, 719, 714, 582, 526, 310, 137, 55, 34, 6, 13700, 5039, 5033, 4222, 4173, 3291, 2506, 972, 748, 348, 220, 38, 30, 109601, 40319, 40312, 34026, 34454, 29792, 28055, 18723, 10613, 6745

Offset: 1

Emeric Deutsch, Aug 24 2006

Row n has 1+floor((n-1)^2/4) terms. Row sums are the factorials (A000142). T(n,0)=A000522(n-1). T(n,1)=(n-1)!-1=A033312(n-1). T(n,2)=(n-1)!-n+1=A005096(n-1) for n>=2. Sum(k*T(n,k), k>=0)=A122105(n).

			Triangle starts:
1;
2;
5,1;
16,5,3;
65,23,20,10,2;
326,119,115,84,57,11,8;

E. Barcucci, S. Brunetti and F. Del Ristoro, Succession rules and deco polyominoes, Theoret. Informatics Appl., 34, 2000, 1-14.
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

Cf. A000142, A000522, A033312, A005096, A122105.

Q[1]:=x: for n from 2 to 10 do Q[n]:=simplify(subs(x=t*x,Q[n-1])/t+(n-1)*x*Q[n-1]) od: for n from 1 to 10 do P[n]:=sort(subs(x=1,Q[n])) od: for n from 1 to 10 do seq(coeff(P[n],t,j),j=0..floor((n-1)^2/4)) od; # yields sequence in triangular form

The row generating polynomials P[n](t) are given by P[n](t)=Q[n](t,1), where Q[1](t,x)=x and Q[n](t,x) = (1/t)Q[n-1](t,tx)+(n-1)xQ[n-1](t,x) for n>=2.

Keyword tabf added by Michel Marcus, Apr 09 2013

cp's OEIS Frontend

A350274 Triangle read by rows: T(n,k) is the number of n-permutations whose fourth-shortest cycle has length exactly k; n >= 0, 0 <= k <= max(0,n-3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions