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.

1, 1, 4, 17, 89, 552, 3895, 30641, 265186, 2497551, 25373097, 276105106, 3199697517, 39297401197, 509370849148, 6943232742493, 99217486649933, 1482237515573624, 23093484367004715, 374416757914118941, 6304680593346141746, 110063311977033807187

Offset: 0

Author

Alois P. Heinz, Aug 12 2008

Keywords

• nonn

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

Examples

			a(2) = 4, because there are 4 forests for 2 labels: {1,2}, {1}{2}, {1}<-2, {2}<-1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..504
• Vaclav Kotesovec, Asymptotics for a certain group of exponential generating functions, arXiv:2207.10568 [math.CO], Jul 13 2022.
• Vaclav Kotesovec, Asymptotics of OEIS A143405, A355291 and the generalization, Jul 12 2022 (this version also includes several figures).
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A055882, A143395, A143396, A143397, A048993, A008277, A007318, A000110, A355291.

Programs

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:
seq(a(n), n=0..23);  # Alois P. Heinz, Oct 05 2019

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 *)

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

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).

E.g.f.: exp(exp(x)*(exp(x)-1)). - Vladeta Jovovic, Dec 08 2008

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) = Sum_{k=0..n} A047974(k) * Stirling2(n,k). - Seiichi Manyama, May 14 2022

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