A331956 Triangle T(n,k) read by rows: number of rooted chains of length k in set partitions of n labeled points.

1, 0, 1, 0, 1, 1, 0, 1, 4, 3, 0, 1, 14, 31, 18, 0, 1, 51, 255, 385, 180, 0, 1, 202, 2066, 6110, 6945, 2700, 0, 1, 876, 17549, 90839, 188510, 171045, 56700, 0, 1, 4139, 159615, 1364307, 4603620, 7314650, 5507460, 1587600

Offset: 0

Author

S. R. Kannan, Rajesh Kumar Mohapatra, Feb 02 2020

Keywords

• nonn
• tabl

Comments

Also the number of chains of length k in unordered set partitions of {1,2,...,n} such that the first term of the chains is either {{1}, {2},...,{n}} or {{1,2,..,n}}.

Number of rooted k-level fuzzy equivalence matrices of order n.

Examples

			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   4     3
  4 | 0 1  14    31    18
  5 | 0 1  51   255   385    180
  6 | 0 1 202  2066  6110   6945   2700
  7 | 0 1 876 17549 90839 188510 171045 56700
  ...
The T(3,2) = 4 in the lattice of set partitions of {1,2,3}:
{{1},{2},{3}} < {{1,2},{3}},
{{1},{2},{3}} < {{1,3},{2}},
{{1},{2},{3}} < {{1},{2,3}},
{{1},{2},{3}} < {{1,2,3}}.
Or,
{{1,2,3}} > {{1,2},{3}},
{{1,2,3}} > {{1,3},{2}},
{{1,2,3}} > {{1},{2,3}},
{{1,2,3}} > {{1},{2},{3}}.
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• S. R. Kannan and Rajesh Kumar Mohapatra, Counting the Number of Non-Equivalent Classes of Fuzzy Matrices Using Combinatorial Techniques, arXiv preprint arXiv:1909.13678 [math.GM], 2019.
• V. Murali, Equivalent finite fuzzy sets and Stirling numbers, Inf. Sci., 174 (2005), 251-263.
• R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1) (1991), 23-31.

Crossrefs

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

Cf. A000110, A008277, A048993, A328044, A330301, A330302.

Programs

Maple

b:= proc(n, k, t) option remember; `if`(k<0 or k>n, 0, `if`(k=1 or
      {n, k}={0}, 1, add(b(v, k-1, 1)*Stirling2(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);  # Alois P. Heinz, Feb 09 2020

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]*StirlingS2[n, v], {v, k, n - t}]]];
T[n_, k_] := b[n, k, 0];
Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten

PARI

b(n, k, t) = {if (k < 0, return(0)); if ((n==0) && (k==0), return (1)); if ((k==1) && (n>0), return(1)); sum(v = k, n - t, if (k==1, 1, b(v, k-1, 1))*stirling(n, v, 2));}
T(n, k) = b(n, k, 0);
matrix(8,8,n, k, T(n-1, k-1)) \\ to see the triangle \\ Michel Marcus, Feb 09 2020

Formula

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} Stirling2(n,i_(k-1)) * Stirling2(i_(k-1),i_(k-2)) * ... * Stirling2(i_3,i_2) * Stirling2(i_2,i_1)))...)), where 2 <= k <= n.