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,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

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

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

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

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

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

Sequence in context: A357617 A350474 A058279 * A303793 A141154 A347340

Adjacent sequences: A143402 A143403 A143404 * A143406 A143407 A143408

Keyword

nonn

Author

Alois P. Heinz, Aug 12 2008

Status

approved