OFFSET
1,2
COMMENTS
Row sums are n!*n = A001563(n) (see example).
From Natalia L. Skirrow, Feb 03 2026: (Start)
Generate a random permutation of [n], then iterate over elements in a random order and observe each one's containing cycle. T(n,k) is n! times the expected number of elements in the k-th distinct cycle observed. Orders of iteration correspond with renumbering nodes and applying the definition. This can be performed in reverse to generate uniform random permutations one cycle at a time, in which T(n,k) measures the k-th cycle generated.
The probability of the k-th cycle having length l is |Stirling1(l; n, k+l-1)| * (l-1)! / n!, where |Stirling1(r; n, k)| is an r-Stirling number; thus, T(n,k) = Sum_{l=1..n-k+1} l!*|Stirling1(l; n, k+l-1)|.
n-th row has center of mass 2 - H_n/n and variance 2 - (H_n^2*(1+1/n) + H_n - H^(2)_n)/n, where H^{(2)}_n = Sum_{k=1..n} 1/k^2 is a second-order harmonic number. (End)
LINKS
Alois P. Heinz, Rows n = 1..141, flattened
Andrei Z. Broder, The r-Stirling numbers. (1984). Discrete Mathematics, vol. 49, iss. 3, pp. 241-259.
Natalia L. Skirrow, a little-known permutation generator
Wikipedia, Permutation
FORMULA
For fixed k>=1, T(n,k) ~ n!*n/2^k. - Vaclav Kotesovec, Apr 25 2017
From Natalia L. Skirrow, Feb 03 2026: (Start)
E.g.f.: (1/(1-x)^2 - 1/(1-x)^y) * y/(2-y).
n-th row o.g.f.: ((n+1)! - Pochhammer[y,n]) * y/(2-y).
T(n,k) = Sum_{i=k..n} |Stirling1(i-1,k-1)| * (n+1)! / (i+1)!.
T(n,k) = (n+1)!/2^k - Sum_{i=1..k} |Stirling1(n,k-i)| / 2^i. [Refining Kotesovec's asymptotic to ~ (n+1)!/2^k * (1 + O(polylog(n)/n^2)).]
T(n+1,k) = n*T(n,k) + T(n,k-1).
T(n+1,k+1) = Sum_{l=0..n-k} (n! / (n-l)!) * T(n-l,k). (End)
EXAMPLE
The six permutations of n=3 in ordered cycle form are:
{ {1}, {2}, {3} }
{ {1}, {2, 3}, {} }
{ {1, 2}, {3}, {} }
{ {1, 2, 3}, {}, {}}
{ {1, 3, 2}, {}, {}}
{ {1, 3}, {2}, {} }
The lengths of the cycles in position k=1 sum to 12, those of the cycles in position k=2 sum to 5 and those of the cycles in position k=3 sum to 1.
Triangle begins:
1;
3, 1;
12, 5, 1;
60, 27, 8, 1;
360, 168, 59, 12, 1;
2520, 1200, 463, 119, 17, 1;
20160, 9720, 3978, 1177, 221, 23, 1;
181440, 88200, 37566, 12217, 2724, 382, 30, 1;
...
MAPLE
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
add((p-> p+coeff(p, x, 0)*j*x^i)(b(n-j, i+1))*
binomial(n-1, j-1)*(j-1)!, j=1..n)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 1)):
seq(T(n), n=1..12); # Alois P. Heinz, Apr 15 2017
MATHEMATICA
Table[it = Join[RotateRight /@ ToCycles[#], Table[{}, {k}]] & /@ Permutations[Range[n]]; Tr[Length[Part[#, k]]& /@ it], {n, 7}, {k, n}]
(* Alternative: *)
b[n_, i_] := b[n, i] = Expand[If[n==0, 1, Sum[Function[p, p + Coefficient[ p, x, 0]*j*x^i][b[n-j, i+1]]*Binomial[n-1, j-1]*(j-1)!, {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 1]];
Array[T, 12] // Flatten (* Jean-François Alcover, May 30 2018, after Alois P. Heinz *)
PROG
(Python)
from math import factorial as fact
from sympy.functions.combinatorial.numbers import stirling
A185105=lambda n, k: sum(fact(n+1)//fact(i+1)*stirling(i-1, k-1, kind=1) for i in range(k, n+1)) # Natalia L. Skirrow, Feb 03 2026
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Wouter Meeussen, Dec 26 2012
EXTENSIONS
More terms from Alois P. Heinz, Apr 15 2017
STATUS
approved
