cp's OEIS Frontend

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

%I A331956 #39 Sep 06 2024 12:36:16
%S A331956 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,
%T A331956 6110,6945,2700,0,1,876,17549,90839,188510,171045,56700,0,1,4139,
%U A331956 159615,1364307,4603620,7314650,5507460,1587600
%N A331956 Triangle T(n,k) read by rows: number of rooted chains of length k in set partitions of n labeled points.
%C A331956 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}}.
%C A331956 Number of rooted k-level fuzzy equivalence matrices of order n.
%H A331956 Alois P. Heinz, <a href="/A331956/b331956.txt">Rows n = 0..140, flattened</a>
%H A331956 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 A331956 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 A331956 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 A331956 T(0, 0) = 1, T(0, k) = 0 for k > 0 and T(n, 1) = 1 for n > 1.
%F A331956 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.
%e A331956 Triangle T(n,k) begins:
%e A331956 n\k | 0 1   2     3     4      5      6     7
%e A331956 ----+-----------------------------------------
%e A331956   0 | 1
%e A331956   1 | 0 1
%e A331956   2 | 0 1   1
%e A331956   3 | 0 1   4     3
%e A331956   4 | 0 1  14    31    18
%e A331956   5 | 0 1  51   255   385    180
%e A331956   6 | 0 1 202  2066  6110   6945   2700
%e A331956   7 | 0 1 876 17549 90839 188510 171045 56700
%e A331956   ...
%e A331956 The T(3,2) = 4 in the lattice of set partitions of {1,2,3}:
%e A331956 {{1},{2},{3}} < {{1,2},{3}},
%e A331956 {{1},{2},{3}} < {{1,3},{2}},
%e A331956 {{1},{2},{3}} < {{1},{2,3}},
%e A331956 {{1},{2},{3}} < {{1,2,3}}.
%e A331956 Or,
%e A331956 {{1,2,3}} > {{1,2},{3}},
%e A331956 {{1,2,3}} > {{1,3},{2}},
%e A331956 {{1,2,3}} > {{1},{2,3}},
%e A331956 {{1,2,3}} > {{1},{2},{3}}.
%p A331956 b:= proc(n, k, t) option remember; `if`(k<0 or k>n, 0, `if`(k=1 or
%p A331956       {n, k}={0}, 1, add(b(v, k-1, 1)*Stirling2(n, v), v=k..n-t)))
%p A331956     end:
%p A331956 T:= (n, k)-> b(n, k, 0):
%p A331956 seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Feb 09 2020
%t A331956 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 A331956 T[n_, k_] := b[n, k, 0];
%t A331956 Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten
%o A331956 (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));}
%o A331956 T(n, k) = b(n, k, 0);
%o A331956 matrix(8,8,n, k, T(n-1, k-1)) \\ to see the triangle \\ _Michel Marcus_, Feb 09 2020
%Y A331956 Cf. A000007 (column k=0), A057427 (column k=1), A058692 (column k=2), A006472 (diagonal), A331957 (row sums).
%Y A331956 Cf. A000110, A008277, A048993, A328044, A330301, A330302.
%K A331956 nonn,tabl
%O A331956 0,9
%A A331956 S. R. Kannan, _Rajesh Kumar Mohapatra_, Feb 02 2020