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

Author

Geoffrey Critzer, Jul 31 2022

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A027415, A356074, A000169.

Programs

Mathematica

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

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