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.

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

Author

Rajesh Kumar Mohapatra, Aug 31 2024

Keywords

• nonn
• tabl

Examples

			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)}.
		

Crossrefs

Cf. A000007 (column k=0), A000142 (column k=1), A006472 (main diagonal), A375836 (row sums).

Cf. A048994, A331955, A330804, A331956, A331957.

Programs

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}]

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.