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
Keywords
Examples
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}}
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.
Crossrefs
Programs
-
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 *) -
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
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
a(n) ~ A086053 * n!^2 / (2^(n-2) * log(2)^n * n^(1 + log(2)/3)). - Vaclav Kotesovec, Jul 01 2025
Extensions
More terms from Michel Marcus, Feb 07 2020
Comments