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

Author

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

Keywords

• nonn
• tabl

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.

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

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.

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.

Programs

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 *)
T[n_, k_] := T[n, k] = If[k < 0 || k > n, 0, If[(n == 0 && k == 0), 1, If[k == 1, BellB[n], Sum[If[r >= 0, StirlingS2[n, r]*T[r, k - 1], 0], {r, k - 1, n - 1}]]]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Rajesh Kumar Mohapatra, Jul 02 2025 *)

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

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.

T(n,k) = Sum_{j=k-1..n-1} Stirling2(n,j)*T(j,k-1), 2 <= k <= n; T(n,1) = Bell(n), n >= 1; T(n,0) = A000007(n). - Rajesh Kumar Mohapatra, Jul 01 2025