cp's OEIS Frontend

A330804 Number of chains in partitions of [n] ordered by refinement.

%I A330804 #57 Jul 02 2025 10:57:20
%S A330804 1,1,3,15,127,1743,36047,1051039,41082783,2073110239,131183712063,
%T A330804 10171782421727,948427290027807,104693416370374783,
%U A330804 13502772386271932927,2011983769934772172799,343000542276546601893439,66334607666382842941084991,14444628785932359077548728255,3518072269888902413311442552511
%N A330804 Number of chains in partitions of [n] ordered by refinement.
%C A330804 Also the number of fuzzy equivalence matrices of order n.
%C A330804 Number of chains of equivalence relations on a set of n-elements.
%C A330804 Number of chains in Stirling numbers of the second kind.
%C A330804 Number of chains in the unordered partition of {1,...,n}.
%H A330804 Alois P. Heinz, <a href="/A330804/b330804.txt">Table of n, a(n) for n = 0..262</a>
%H A330804 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 A330804 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 A330804 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 A330804 a(n) = Sum_{k=0..n} A331955(n,k).
%F A330804 a(n) = Bell(n) + Sum_{i=1..n-1} Stirling2(n,i)*a(i). - _Alois P. Heinz_, Sep 03 2020
%F A330804 a(n) ~ A086053 * n!^2 / (2^(n-2) * log(2)^n * n^(1 + log(2)/3)). - _Vaclav Kotesovec_, Jul 01 2025
%F A330804 a(n) = 2 * A331957(n) - 1 = 4 * A005121(n) - 1 for n > 1. - _Rajesh Kumar Mohapatra_, Jul 01 2025
%e A330804 Consider the set S = {1, 2, 3}. The a(3) = 5+ 7+ 3 = 15 in the lattice of set partitions of {1,2,3}:
%e A330804 {{1},{2},{3}}  {{1},{2},{3}} < {{1,2},{3}}  {{1},{2},{3}} < {{1,2},{3}} < {{1,2,3}}
%e A330804 {{1,2},{3}}    {{1},{2},{3}} < {{1,3},{2}}  {{1},{2},{3}} < {{1,3},{2}} < {{1,2,3}}
%e A330804 {{1,3},{2}}    {{1},{2},{3}} < {{1},{2,3}}  {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
%e A330804 {{1},{2,3}}    {{1},{2},{3}} < {{1,2,3}}
%e A330804 {{1,2,3}}      {{1,2},{3}} < {{1,2,3}}
%e A330804                {{1,3},{2}} < {{1,2,3}}
%e A330804                {{1},{2,3}} < {{1,2,3}}
%p A330804 b:= proc(n, k, t) option remember; `if`(k<0, 0, `if`({n, k}={0}, 1,
%p A330804       add(`if`(k=1, 1, b(v, k-1, 1))*Stirling2(n, v), v=k..n-t)))
%p A330804     end:
%p A330804 a:= n-> add(b(n, k, 0), k=0..n):
%p A330804 seq(a(n), n=0..20);  # _Alois P. Heinz_, Feb 07 2020
%p A330804 # second Maple program:
%p A330804 a:= proc(n) option remember; uses combinat;
%p A330804       bell(n) + add(stirling2(n, i)*a(i), i=1..n-1)
%p A330804     end:
%p A330804 seq(a(n), n=0..20);  # _Alois P. Heinz_, Sep 03 2020
%t A330804 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 A330804 a[n_] := Sum[b[n, k, 0], {k, 0, n}];
%t A330804 a /@ Range[0, 20] (* _Jean-François Alcover_, Feb 08 2020, after _Alois P. Heinz_ *)
%o A330804 (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));}
%o A330804 a(n) = sum(k=0, n, b(n, k, 0);); \\ _Michel Marcus_, Feb 08 2020
%Y A330804 Cf. A008277, A048993, A000110, A143494, A006472.
%Y A330804 Cf. A007047, A328044, A330301, A330302, A331955.
%Y A330804 Cf. A131407, A086053.
%K A330804 nonn
%O A330804 0,3
%A A330804 S. R. Kannan, _Rajesh Kumar Mohapatra_, Jan 01 2020
%E A330804 More terms from _Michel Marcus_, Feb 07 2020