cp's OEIS Frontend

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

%I A331955 #67 Jul 03 2025 04:07:04
%S A331955 1,0,1,0,2,1,0,5,7,3,0,15,45,49,18,0,52,306,640,565,180,0,203,2268,
%T A331955 8176,13055,9645,2700,0,877,18425,108388,279349,359555,227745,56700,0,
%U A331955 4140,163754,1523922,5967927,11918270,12822110,7095060,1587600
%N A331955 Triangle T(n,k) of number of chains of length k in partitions of an n-set ordered by refinement.
%C A331955 Also the number of chains of equivalence relations of length k on a set of n-points.
%C A331955 Number of chains of length k in Stirling numbers of the second kind.
%C A331955 Number of chains of length k in the unordered partition of {1,2,...,n}.
%C A331955 Number of k-level fuzzy equivalence matrices of order n.
%H A331955 Alois P. Heinz, <a href="/A331955/b331955.txt">Rows n = 0..140, flattened</a>
%H A331955 S. R. Kannan and Rajesh Kumar Mohapatra, <a href="https://arxiv.org/abs/1909.13678">Counting the Number of Non-Equivalent Classes of Fuzzy Matrices Using Combinatorial Techniques</a>, arXiv preprint arXiv:1909.13678 [math.GM], 2019.
%H A331955 V. Murali, <a href="https://doi.org/10.1016/j.ins.2004.08.008">Equivalent finite fuzzy sets and Stirling numbers</a>, Inf. Sci., 174 (2005), 251-263.
%H A331955 V. Murali, <a href="https://doi.org/10.1016/j.fss.2006.03.005">Combinatorics of counting finite fuzzy subsets</a>, Fuzzy Sets Syst., 157(17)(2006), 2403-2411.
%H A331955 R. B. Nelsen and H. Schmidt, Jr., <a href="http://www.jstor.org/stable/2690450">Chains in power sets</a>, Math. Mag., 64 (1) (1991), 23-31.
%F A331955 T(0, 0) = 1, T(0, k) = 0 for k > 0.
%F A331955 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.
%F A331955 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
%e A331955 The triangle T(n,k) begins:
%e A331955   n\k 0   1     2      3      4       5     6     7...
%e A331955   0   1
%e A331955   1   0   1
%e A331955   2   0   2     1
%e A331955   3   0   5     7      3
%e A331955   4   0  15    45     49     18
%e A331955   5   0  52   306    640    565    180
%e A331955   6   0 203  2268   8176  13055   9645   2700
%e A331955   7   0 877 18425 108388 279349 359555 227745 56700
%e A331955   ...
%e A331955 The T(3,2) = 7 in the lattice of set partitions of {1,2,3}:
%e A331955   {{1},{2},{3}} < {{1,2},{3}},
%e A331955   {{1},{2},{3}} < {{1,3},{2}},
%e A331955   {{1},{2},{3}} < {{1},{2,3}},
%e A331955   {{1},{2},{3}} < {{1,2,3}},
%e A331955   {{1,2},{3}} < {{1,2,3}},
%e A331955   {{1,3},{2}} < {{1,2,3}},
%e A331955   {{1},{2,3}} < {{1,2,3}}.
%p A331955 b:= proc(n, k, t) option remember; `if`(k<0, 0, `if`({n, k}={0}, 1,
%p A331955       add(`if`(k=1, 1, b(v, k-1, 1))*Stirling2(n, v), v=k..n-t)))
%p A331955     end:
%p A331955 T:= (n, k)-> b(n, k, 0):
%p A331955 seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Feb 07 2020
%t A331955 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 A331955 T[n_, k_] := b[n, k, 0];
%t A331955 Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Feb 08 2020, after _Alois P. Heinz_ *)
%t A331955 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 *)
%o A331955 (PARI)
%o A331955 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));}
%o A331955 T(n, k) = b(n, k, 0);
%o A331955 matrix(8, 8, n, k, T(n-1, k-1)) \\ to see the triangle \\ _Michel Marcus_, Feb 08 2020
%Y A331955 Cf. A000007 (column k=0), A000110 (column k=1), A006472 (diagonal), A330804 (row sums).
%Y A331955 T(2n,n) gives A332244.
%Y A331955 Cf. A008277, A048993, A328044, A330301, A330302.
%K A331955 nonn,tabl
%O A331955 0,5
%A A331955 S. R. Kannan, _Rajesh Kumar Mohapatra_, Feb 02 2020