|
|
A331957
|
|
Number of rooted chains in set partitions of {1, 2, ..., n}.
|
|
5
|
|
|
1, 1, 2, 8, 64, 872, 18024, 525520, 20541392, 1036555120, 65591856032, 5085891210864, 474213645013904, 52346708185187392, 6751386193135966464, 1005991884967386086400, 171500271138273300946720, 33167303833191421470542496, 7222314392966179538774364128, 1759036134944451206655721276256
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also the number of chains of Stirling numbers of the second kind such that the first term of the chains is either {{1}, {2}, ..., {n}} or {{1,2,...,n}}.
Number of rooted fuzzy equivalence matrices of order n.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The a(3) = 8 in the lattice of set partitions of {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}} < {{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}} < {{1,2,3}}.
Or,
{{1,2,3}},
{{1,2,3}} > {{1,2},{3}},
{{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}} > {{2},{1,3}} > {{1},{2},{3}},
{{1,2,3}} > {{3},{1,2}} > {{1},{2},{3}}.
|
|
MAPLE
|
b:= proc(n, k, t) option remember; `if`(k<0 or k>n, 0, `if`(k=1 or
{n, k}={0}, 1, add(b(v, k-1, 1)*Stirling2(n, v), v=k..n-t)))
end:
a:= n-> add(b(n, k, 0), k=0..n):
|
|
MATHEMATICA
|
b[n_, k_, t_] := b[n, k, t] = If[k < 0 || k > n, 0, If[k == 1 || Union@{n, k} =={0}, 1, Sum[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, 30]
|
|
PROG
|
(PARI) b(n, k, t) = {if (k < 0, return(0)); if ((n==0) && (k==0), return (1)); if ((k==1) && (n>0), return(1)); sum(v = k, n - t, if (k==1, 1, b(v, k-1, 1))*stirling(n, v, 2)); }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|