login
A375835
Triangle read by rows: T(n, k) is the number of chains of length k in the poset of permutations of an n-set.
3
1, 0, 1, 0, 2, 1, 0, 6, 8, 3, 0, 24, 64, 59, 18, 0, 120, 574, 970, 695, 180, 0, 720, 5858, 16124, 20240, 11955, 2700, 0, 5040, 67752, 285264, 556591, 559895, 282555, 56700, 0, 40320, 880584, 5459712, 15519287, 23585870, 19879370, 8780940, 1587600, 0, 362880, 12746208, 113511982, 451541898, 971214825, 1213062690, 882179550, 347072040, 57153600
OFFSET
0,5
FORMULA
Let Stirling1(n, k) denote the unsigned Stirling numbers of the first kind (A132393).
T(0, 0) = 1, T(0, k) = 0 for k > 0.
T(n, k) = Sum_{i_k=k..n} (Sum_{i_(k-1)=k-1..i_k - 1} (... (Sum_{i_2=2..i_3 - 1} (Sum_{i_1=1..i_2 - 1} Stirling1(n, i_k) * Stirling1(i_k, i_(k-1)) * ... * Stirling1(i_3, i_2) * Stirling1(i_2, i_1)))...)), where 1 <= k <= n.
EXAMPLE
The triangle T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 ...
0 1
1 0 1
2 0 2 1
3 0 6 8 3
4 0 24 64 59 18
5 0 120 574 970 695 180
6 0 720 5858 16124 20240 11955 2700
7 0 5040 67752 285264 556591 559895 282555 56700
...
The T(3, 2) = 8 chains in the poset of the permutations of {1, 2, 3} are:
{(1)(2)(3) < (1)(23), (1)(2)(3) < (2)(13), (1)(2)(3) < (3)(12), (1)(2)(3) < (123),(1)(2)(3) < (132), (1)(23) < (123), (2)(13) < (132), (3)(12) < (123)}.
MAPLE
b := proc(n, k, t) option remember; if k < 0 then return 0 fi; if {n, k} = {0} then return 1 fi; add(ifelse(k = 1, 1, b(v, k - 1, 1))*abs(Stirling1(n, v)), v = k..n-t) end: T := (n, k) -> b(n, k, 0): seq((seq(T(n, k), k=0..n)), n = 0..10); # Peter Luschny, Sep 05 2024
MATHEMATICA
b[n_, k_, t_] := b[n, k, t] = If[k < 0, 0, If[n == 0 && k == 0, 1,
Sum[If[k == 1, 1, b[v, k - 1, 1]] * Abs[StirlingS1[n, v]], {v, k, n - t}]]];
T[n_, k_] := b[n, k, 0]; Table[T[n, k], {n, 0, 10}, {k, 0, n}]
CROSSREFS
Cf. A000007 (column k=0), A000142 (column k=1), A006472 (main diagonal), A375836 (row sums).
Sequence in context: A163936 A288874 A356545 * A187555 A358188 A117651
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved