login
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.
2
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
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).
Sequence in context: A322758 A077602 A238008 * A375772 A193547 A144481
KEYWORD
nonn,tabl
AUTHOR
Rajesh Kumar Mohapatra, Ranjan Kumar Dhani, and Subhashree Sahoo, Aug 31 2024
STATUS
approved