|
|
A143405
|
|
Number of forests of labeled rooted trees of height at most 1, with n labels, where any root may contain >= 1 labels, also row sums of A143395, A143396 and A143397.
|
|
13
|
|
|
1, 1, 4, 17, 89, 552, 3895, 30641, 265186, 2497551, 25373097, 276105106, 3199697517, 39297401197, 509370849148, 6943232742493, 99217486649933, 1482237515573624, 23093484367004715, 374416757914118941, 6304680593346141746, 110063311977033807187
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is the number of the partitions of an n-set where each block is endowed with a nonempty subset. - Emanuele Munarini, Sep 15 2016
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n} Sum_{t=k..n} C(n,t) * Stirling2(t,k)*k^(n-t).
a(n) = Sum_{k=0..n} Sum_{t=0..k} C(n,k) * Stirling2(k,t)*t^(n-k).
a(n) = Sum_{k=0..n} Sum_{t=0..k} C(n,k-t) * Stirling2(n-(k-t),t)*t^(k-t).
a(n) = sum(binomial(n,k)*2^k*bell(k)*S(n-k,-1),k=0..n), where bell(n) are the Bell numbers (A000110) and S(n,x) = sum(Stirling2(n,k)*x^k,k=0..n) are the Stirling (or exponential) polynomials. - Emanuele Munarini, Sep 15 2016
Identity: sum(binomial(n,k)*a(k)*bell(n-k),k=0..n) = 2^n*bell(n). - Emanuele Munarini, Sep 15 2016
a(n) ~ exp(exp(2*z) - exp(z) - n) * (n/z)^(n + 1/2) / sqrt(2*(1 + 2*z)*exp(2*z) - (1 + z)*exp(z)), where z = LambertW(n)/2 - 1/(1 + 2/LambertW(n) - 4 * n^(1/2) * (1 + LambertW(n)) / LambertW(n)^(3/2)). - Vaclav Kotesovec, Jul 03 2022
a(n) ~ 2^n * n^n / (sqrt(1 + LambertW(n)) * LambertW(n)^n * exp(n + 1/8 - n/LambertW(n) + sqrt(n/LambertW(n)))). - Vaclav Kotesovec, Jul 08 2022
|
|
EXAMPLE
|
a(2) = 4, because there are 4 forests for 2 labels: {1,2}, {1}{2}, {1}<-2, {2}<-1.
|
|
MAPLE
|
a:= n-> add(add(binomial(n, t)*Stirling2(t, k)*k^(n-t), t=k..n), k=0..n):
seq(a(n), n=0..30);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
a(n-j)*binomial(n-1, j-1)*(2^j-1), j=1..n))
end:
|
|
MATHEMATICA
|
CoefficientList[Series[Exp[Exp[t] (Exp[t] - 1)], {t, 0, 12}], t] Range[0, 12]! (* Emanuele Munarini, Sep 15 2016 *)
Table[Sum[Binomial[n, k] 2^k BellB[k] BellB[n - k, -1], {k, 0, n}], {n, 0, 12}] (* Emanuele Munarini, Sep 15 2016 *)
Table[Sum[BellY[n, k, 2^Range[n] - 1], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)
|
|
PROG
|
(PARI) a(n) = sum(k=0, n, k!*sum(j=0, k\2, 1/(j!*(k-2*j)!))*stirling(n, k, 2)); \\ Seiichi Manyama, May 14 2022
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|