A330804 - OEIS

%I #51 Sep 03 2020 17:28:00

%S 1,1,3,15,127,1743,36047,1051039,41082783,2073110239,131183712063,

%T 10171782421727,948427290027807,104693416370374783,

%U 13502772386271932927,2011983769934772172799,343000542276546601893439,66334607666382842941084991,14444628785932359077548728255,3518072269888902413311442552511

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

%C Also the number of fuzzy equivalence matrices of order n.

%C Number of chains of equivalence relations on a set of n-elements.

%C Number of chains in Stirling numbers of the second kind.

%C Number of chains in the unordered partition of {1,...,n}.

%H Alois P. Heinz, <a href="/A330804/b330804.txt">Table of n, a(n) for n = 0..262</a>

%H 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 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 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 a(n) = Sum_{k=0..n} A331955(n,k).

%F a(n) = Bell(n) + Sum_{i=1..n-1} Stirling2(n,i)*a(i). - _Alois P. Heinz_, Sep 03 2020

%e 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 {{1},{2},{3}}  {{1},{2},{3}} < {{1,2},{3}}  {{1},{2},{3}} < {{1,2},{3}} < {{1,2,3}}

%e {{1,2},{3}}    {{1},{2},{3}} < {{1,3},{2}}  {{1},{2},{3}} < {{1,3},{2}} < {{1,2,3}}

%e {{1,3},{2}}    {{1},{2},{3}} < {{1},{2,3}}  {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}

%e {{1},{2,3}}    {{1},{2},{3}} < {{1,2,3}}

%e {{1,2,3}}      {{1,2},{3}} < {{1,2,3}}

%e                {{1,3},{2}} < {{1,2,3}}

%e                {{1},{2,3}} < {{1,2,3}}

%p b:= proc(n, k, t) option remember; `if`(k<0, 0, `if`({n, k}={0}, 1,

%p       add(`if`(k=1, 1, b(v, k-1, 1))*Stirling2(n, v), v=k..n-t)))

%p     end:

%p a:= n-> add(b(n, k, 0), k=0..n):

%p seq(a(n), n=0..20);  # _Alois P. Heinz_, Feb 07 2020

%p # second Maple program:

%p a:= proc(n) option remember; uses combinat;

%p       bell(n) + add(stirling2(n, i)*a(i), i=1..n-1)

%p     end:

%p seq(a(n), n=0..20);  # _Alois P. Heinz_, Sep 03 2020

%t 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 a[n_] := Sum[b[n, k, 0], {k, 0, n}];

%t a /@ Range[0, 20] (* _Jean-François Alcover_, Feb 08 2020, after _Alois P. Heinz_ *)

%o (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 a(n) = sum(k=0, n, b(n, k, 0);); \\ _Michel Marcus_, Feb 08 2020

%Y Cf. A008277, A048993, A000110, A143494, A006472.

%Y Cf. A007047, A328044, A330301, A330302, A331955.

%Y Cf. A131407.

%K nonn

%O 0,3

%A S. R. Kannan, _Rajesh Kumar Mohapatra_, Jan 01 2020

%E More terms from _Michel Marcus_, Feb 07 2020