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

1, 1, 3, 15, 127, 1743, 36047, 1051039, 41082783, 2073110239, 131183712063, 10171782421727, 948427290027807, 104693416370374783, 13502772386271932927, 2011983769934772172799, 343000542276546601893439, 66334607666382842941084991, 14444628785932359077548728255, 3518072269888902413311442552511

Offset

0,3

Comments

Also the number of fuzzy equivalence matrices of order n.

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

Number of chains in Stirling numbers of the second kind.

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..262

S. R. Kannan and Rajesh Kumar Mohapatra, Counting the Number of Non-Equivalent Classes of Fuzzy Matrices Using Combinatorial Techniques, arXiv preprint arXiv:1909.13678 [math.GM], 2019.

V. Murali, Equivalent finite fuzzy sets and Stirling numbers, Inf. Sci., 174 (2005), 251-263.

R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1) (1991), 23-31.

Formula

a(n) = Sum_{k=0..n} A331955(n,k).

a(n) = Bell(n) + Sum_{i=1..n-1} Stirling2(n,i)*a(i). - Alois P. Heinz, Sep 03 2020

Example

Consider the set S = {1, 2, 3}. The a(3) = 5+ 7+ 3 = 15 in the lattice of set partitions of {1,2,3}:
{{1},{2},{3}}  {{1},{2},{3}} < {{1,2},{3}}  {{1},{2},{3}} < {{1,2},{3}} < {{1,2,3}}
{{1,2},{3}}    {{1},{2},{3}} < {{1,3},{2}}  {{1},{2},{3}} < {{1,3},{2}} < {{1,2,3}}
{{1,3},{2}}    {{1},{2},{3}} < {{1},{2,3}}  {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
{{1},{2,3}}    {{1},{2},{3}} < {{1,2,3}}
{{1,2,3}}      {{1,2},{3}} < {{1,2,3}}
               {{1,3},{2}} < {{1,2,3}}
               {{1},{2,3}} < {{1,2,3}}

Maple

b:= proc(n, k, t) option remember; `if`(k<0, 0, `if`({n, k}={0}, 1,
      add(`if`(k=1, 1, b(v, k-1, 1))*Stirling2(n, v), v=k..n-t)))
    end:
a:= n-> add(b(n, k, 0), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 07 2020
# second Maple program:
a:= proc(n) option remember; uses combinat;
      bell(n) + add(stirling2(n, i)*a(i), i=1..n-1)
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 03 2020

Mathematica

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}]]];
a[n_] := Sum[b[n, k, 0], {k, 0, n}];
a /@ Range[0, 20] (* Jean-François Alcover, Feb 08 2020, after Alois P. Heinz *)

Prog

(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)); }
a(n) = sum(k=0, n, b(n, k, 0); ); \\ Michel Marcus, Feb 08 2020

Crossrefs

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

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

Cf. A131407.

Sequence in context: A266091 A135255 A182489 * A335390 A075475 A074241

Adjacent sequences: A330801 A330802 A330803 * A330805 A330806 A330807

Keyword

nonn

Author

S. R. Kannan, Rajesh Kumar Mohapatra, Jan 01 2020

Extensions

More terms from Michel Marcus, Feb 07 2020

Status

approved