A375837 Triangle read by rows: T(n,k) is the number of rooted chains starting with the cycle (1)(2)(3)...(n) of length k of permutation poset of n letters.

1, 0, 1, 0, 1, 1, 0, 1, 5, 3, 0, 1, 23, 41, 18, 0, 1, 119, 455, 515, 180, 0, 1, 719, 5139, 10985, 9255, 2700, 0, 1, 5039, 62713, 222551, 334040, 225855, 56700, 0, 1, 40319, 840265, 4619447, 10899840, 12686030, 7193340, 1587600, 0, 1, 362879, 12383329, 101128653, 350413245, 620801580, 592261110, 289918440, 57153600

Offset

0,9

Links

Table of n, a(n) for n=0..54.

Sean A. Irvine, Java program (github)

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 and T(n, 1) = 1 for n > 1.

T(n, k) = Sum_{i_(k-1)=k-1..n-1} (Sum_{i_(k-2)=k-2..i_(k-1) - 1} (... (Sum_{i_2=2..i_3 - 1} (Sum_{i_1=1..i_2 - 1} Stirling1(n,i_(k-1)) * Stirling1(i_(k-1),i_(k-2)) * ... * Stirling1(i_3,i_2) * Stirling1(i_2,i_1)))...)), where 2 <= k <= n.

Example

Triangle T(n,k) begins:
  n\k | 0  1   2     3     4      5      6     7 ...
 -----+-----------------------------------------
  0   | 1;
  1   | 0, 1;
  2   | 0, 1, 1;
  3   | 0, 1, 5, 3;
  4   | 0, 1, 23, 41, 18;
  5   | 0, 1, 119, 455, 515, 180;
  6   | 0, 1, 719, 5139, 10985, 9255, 2700;
  7   | 0, 1, 5039, 62713, 222551, 334040, 225855, 56700;
  ...
The T(3, 2) = 5 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)}.

Mathematica

b[n_, k_, t_] := b[n, k, t] = If[k < 0 || k > n, 0, If[k == 1 || Union@{n, k} == {0}, 1, Sum[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, 20}, {k, 0, n}] // Flatten

Crossrefs

Cf. A000007 (column k=0), A057427 (column k=1), A006472 (diagonal), A375838 (row sums).

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

Sequence in context: A322758 A077602 A238008 * A375772 A193547 A144481

Adjacent sequences: A375834 A375835 A375836 * A375838 A375839 A375840

Keyword

nonn,tabl

Author

Rajesh Kumar Mohapatra, Ranjan Kumar Dhani, and Subhashree Sahoo, Aug 31 2024

Status

approved