A356259 Number of labeled rooted trees on [n] that have a primary branch.

0, 2, 6, 60, 500, 7290, 100842, 1978368, 38263752, 949218750, 23579476910, 709026379776, 21505924728444, 760772509715764, 27246730957031250, 1109165339867873280, 45798768824157052688, 2109518949433090534902

Offset

1,2

Comments

This sequence is the labeled version of A027415 where the definition can be found.

Links

Table of n, a(n) for n=1..18.

N. J. A. Sloane, Illustration of initial terms

Formula

a(n) = Sum_{i=1..floor(n/2)} binomial(n,n-i)*r(n-i)*r(i) where r(i) = A000169(i).

a(n) = A000169(n) - A356073(n).

Example

a(5) = 500. In the illustrations by Sloane found in the link above, for n = 5, there are A027415(5) = 6 rooted trees with a primary branch: the first six trees shown.

Mathematica

Table[Sum[Binomial[n, n - i] (n - i)^(n - i - 1)*i^(i - 1), {i, 1, Floor[n/2]}], {n, 1, 20}]

Crossrefs

Cf. A027415, A356074, A000169.

Sequence in context: A083135 A056604 A362702 * A215720 A371018 A211936

Adjacent sequences: A356256 A356257 A356258 * A356260 A356261 A356262

Keyword

nonn

Author

Geoffrey Critzer, Jul 31 2022

Status

approved