A331955 Triangle T(n,k) of number of chains of length k in partitions of an n-set ordered by refinement.

1, 0, 1, 0, 2, 1, 0, 5, 7, 3, 0, 15, 45, 49, 18, 0, 52, 306, 640, 565, 180, 0, 203, 2268, 8176, 13055, 9645, 2700, 0, 877, 18425, 108388, 279349, 359555, 227745, 56700, 0, 4140, 163754, 1523922, 5967927, 11918270, 12822110, 7095060, 1587600

Offset

0,5

Comments

Also the number of chains of equivalence relations of length k on a set of n-points.

Number of chains of length k in Stirling numbers of the second kind.

Number of chains of length k in the unordered partition of {1,2,...,n}.

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

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.

V. Murali, Combinatorics of counting finite fuzzy subsets, Fuzzy Sets Syst., 157(17)(2006), 2403-2411.

R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1) (1991), 23-31.

Formula

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} Stirling2(n,i_k) * Stirling2(i_k,i_(k-1)) * ... * Stirling2(i_3,i_2) * Stirling2(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   5     7      3
4   0  15    45     49     18
5   0  52   306    640    565    180
6   0 203  2268   8176  13055   9645   2700
7   0 877 18425 108388 279349 359555 227745 56700
...
The T(3,2) = 7 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}},
{{1,2},{3}} < {{1,2,3},
{{1,3},{2}} < {{1,2,3}},
{{1},{2,3}} < {{1,2,3}}.

Maple

b:= proc(n, k, t) option remember; `if`(k<0, 0, `if`({n, k}={0}, 1,
      add(`if`(k=1, 1, 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 07 2020

Mathematica

b[n_, k_, t_] := b[n, k, t] = If[k < 0, 0, If[Union@{n, k} == {0}, 1, Sum[If[k == 1, 1, 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, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 08 2020, after Alois P. Heinz *)

Prog

(PARI)
b(n, k, t) = {if (k < 0, return(0)); if ((n==0) && (k==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 08 2020

Crossrefs

Cf. A000007 (column k=0), A000110 (column k=1), A006472 (diagonal), A330804 (row sums).

T(2n,n) gives A332244.

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

Sequence in context: A292323 A059720 A140589 * A185209 A316659 A241218

Adjacent sequences: A331952 A331953 A331954 * A331956 A331957 A331958

Keyword

nonn,tabl

Author

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

Status

approved