cp's OEIS Frontend

A331957 Number of rooted chains in set partitions of {1, 2, ..., n}.

%I A331957 #53 Jul 01 2025 14:37:21
%S A331957 1,1,2,8,64,872,18024,525520,20541392,1036555120,65591856032,
%T A331957 5085891210864,474213645013904,52346708185187392,6751386193135966464,
%U A331957 1005991884967386086400,171500271138273300946720,33167303833191421470542496,7222314392966179538774364128,1759036134944451206655721276256
%N A331957 Number of rooted chains in set partitions of {1, 2, ..., n}.
%C A331957 Also the number of chains of Stirling numbers of the second kind such that the first term of the chains is either {{1}, {2}, ..., {n}} or {{1,2,...,n}}.
%C A331957 Number of rooted fuzzy equivalence matrices of order n.
%H A331957 Alois P. Heinz, <a href="/A331957/b331957.txt">Table of n, a(n) for n = 0..261</a>
%H A331957 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 A331957 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 A331957 R. B. Nelsen and H. Schmidt, Jr., <a href="https://www.jstor.org/stable/2690450">Chains in power sets</a>, Math. Mag., 64 (1) (1991), 23-31.
%F A331957 a(n) = Sum_{k=0..n} A331956(n,k).
%F A331957 Conjecture from _Mikhail Kurkov_, Jun 25 2025: (Start)
%F A331957 a(n) = R(n,0) where
%F A331957   R(0,0) = 1,
%F A331957   R(n,k) = (k+1) * Sum_{j=k..n-1} R(n-1,j) for 0 <= k < n,
%F A331957   R(n,n) = Sum_{j=0..n-1} R(n,j). (End)
%F A331957 a(n) ~ A086053 * n!^2 / (2^(n-1) * log(2)^n * n^(1 + log(2)/3)). - _Vaclav Kotesovec_, Jul 01 2025
%F A331957 a(n) = 1 + Sum_{k=1..n-1} Stirling2(n,k)*a(k). - _Rajesh Kumar Mohapatra_, Jul 01 2025
%e A331957 The a(3) = 8 in the lattice of set partitions of {1,2,3}:
%e A331957   {{1},{2},{3}},
%e A331957   {{1},{2},{3}} < {{1,2},{3}},
%e A331957   {{1},{2},{3}} < {{1,3},{2}},
%e A331957   {{1},{2},{3}} < {{1},{2,3}},
%e A331957   {{1},{2},{3}} < {{1,2,3}},
%e A331957   {{1},{2},{3}} < {{1,2},{3}} < {{1,2,3}},
%e A331957   {{1},{2},{3}} < {{1,3},{2}} < {{1,2,3}},
%e A331957   {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}.
%e A331957 Or,
%e A331957   {{1,2,3}},
%e A331957   {{1,2,3}} > {{1,2},{3}},
%e A331957   {{1,2,3}} > {{1,3},{2}},
%e A331957   {{1,2,3}} > {{1},{2,3}},
%e A331957   {{1,2,3}} > {{1},{2},{3}},
%e A331957   {{1,2,3}} > {{1},{2,3}} > {{1},{2},{3}},
%e A331957   {{1,2,3}} > {{2},{1,3}} > {{1},{2},{3}},
%e A331957   {{1,2,3}} > {{3},{1,2}} > {{1},{2},{3}}.
%p A331957 b:= proc(n, k, t) option remember; `if`(k<0 or k>n, 0, `if`(k=1 or
%p A331957       {n, k}={0}, 1, add(b(v, k-1, 1)*Stirling2(n, v), v=k..n-t)))
%p A331957     end:
%p A331957 a:= n-> add(b(n, k, 0), k=0..n):
%p A331957 seq(a(n), n=0..20);  # _Alois P. Heinz_, Feb 09 2020
%t A331957 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 A331957 a[n_] := Sum[b[n, k, 0], {k, 0, n}];
%t A331957 a /@ Range[0, 30]
%o A331957 (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 A331957 a(n) = sum(k=0, n, b(n, k, 0); ); \\ _Michel Marcus_, Feb 09 2020
%o A331957 (Python)
%o A331957 from sympy.functions.combinatorial.numbers import stirling as s
%o A331957 from functools import cache
%o A331957 @cache
%o A331957 def a(n): return 1 + sum(s(n, k) * a(k) for k in range(1, n)) # _David Radcliffe_, Jul 01 2025
%Y A331957 Row sums of A331956.
%Y A331957 Cf. A000110, A058692, A006472.
%Y A331957 Cf. A008277, A048993, A328044, A330301, A330302.
%Y A331957 Cf. A086053.
%K A331957 nonn
%O A331957 0,3
%A A331957 S. R. Kannan and _Rajesh Kumar Mohapatra_, Feb 02 2020
%E A331957 More terms from _Michel Marcus_, Feb 08 2020