A349562 Number of labeled rooted forests with 2-colored leaves.

1, 2, 8, 56, 576, 7872, 134656, 2771456, 66744320, 1842237440, 57354338304, 1988721131520, 76015173369856, 3175757373243392, 143980934947930112, 7040807787705663488, 369414622819764928512, 20700889684976244621312, 1233951687316746828513280, 77963762014950356953333760

Offset

0,2

Comments

a(n) is the number of labeled trees on vertices 0,1,...,n rooted at 0, where all leaves have 2 colors (except the singleton tree 0 has only 1 color).

Links

Seiichi Manyama, Table of n, a(n) for n = 0..372

Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.

Eric Weisstein's World of Mathematics, Lambert W-Function.

Formula

a(n) = Sum_{k=0..n} binomial(n,k)*(k+1)^(n-1).

a(n) = A216857(n+1)/(n+1).

a(n) = A038049(n+1)/(n+1) for n>=1, and a(0) = A038049(1)/2.

a(n) = 2*A201595(n) - A000007(n).

E.g.f. satisfies: A(x) = e^(x*(1 + A(x))).

E.g.f. satisfies: A(-x*A(x)) = 1/A(x).

From Vaclav Kotesovec, Nov 25 2021: (Start)

E.g.f.: -LambertW(-x*exp(x))/x.

a(n) ~ sqrt(1 + LambertW(exp(-1))) * n^(n-1) / (exp(n) * LambertW(exp(-1))^(n+1)).

(End)

From Seiichi Manyama, Nov 26 2021: (Start)

G.f.: Sum_{k>=0} (k+1)^(k-1) * x^k/(1 - (k+1)*x)^(k+1).

a(n) = 2^n * A007889(n). (End)

Example

a(2)=8 counts trees 0-1-2B, 0-1-2R, 0-2-1B, 0-2-1R, 1B-0-2B, 1B-0-2R, 1R-0-2B, 1R-0-2R (where B and R stand for colors Blue and Red).

Mathematica

CoefficientList[u/.AsymptoticSolve[u-E^(x(1+u))==0, u->1, {x, 0, 24}][[1]], x]Factorial/@Range[0, 24]
nmax = 20; CoefficientList[Series[-LambertW[-x*Exp[x]]/x, {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Nov 25 2021 *)

Prog

(PARI) my(N=20, x='x+O('x^N)); Vec(sum(k=0, N, (k+1)^(k-1)*x^k/(1-(k+1)*x)^(k+1))) \\ Seiichi Manyama, Nov 26 2021

Crossrefs

Cf. A000007, A007889, A216857, A038049, A201595,

Sequence in context: A124212 A326009 A372160 * A325290 A197949 A363589

Adjacent sequences: A349559 A349560 A349561 * A349563 A349564 A349565

Keyword

nonn

Author

Alexander Burstein, Nov 22 2021

Status

approved