login
A330804
Number of chains in partitions of [n] ordered by refinement.
9
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
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
KEYWORD
nonn
AUTHOR
S. R. Kannan, Rajesh Kumar Mohapatra, Jan 01 2020
EXTENSIONS
More terms from Michel Marcus, Feb 07 2020
STATUS
approved