A356073 Number of labeled trees on [n] having a centroid.

0, 1, 0, 3, 4, 125, 486, 16807, 118784, 4782969, 50781250, 2357947691, 33981990912, 1792160394037, 32942263538380, 1946195068359375, 43756164738973696, 2862423051509815793

Offset: 0

Author

Geoffrey Critzer, Jul 31 2022

Keywords

• nonn

Comments

This is the labeled version of A027416 where the pertinent definitions can be found.

Examples

			a(6) = 486.  In the illustrations by Sloane found in the link above, for n = 6, there are A027416(3) = 3 trees with a centroid: the third, fourth and fifth trees shown.  They have 360, 120, and 6 labelings respectively.  360 + 120  + 6 = 486.
		

Links

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

Crossrefs

Cf. A356186, A000272, A027416.

Programs

Mathematica

Prepend[Table[If[EvenQ[n], n^(n - 2) - Binomial[n, n/2] (n/2)^(n - 2)/2, n^(n - 2)], {n, 1, 17}], 0]

Formula

If n is even, a(n) = n^(n-2) - binomial(n,n/2)*(n/2)^(n-2)/2 = A000272(n) - A000984(n)*A356186(n/2)/2.

If n is odd, a(n) = n^(n-2).

For n >= 1, a(n) = n!*[x^n] x*exp(T(x)) where T(x) = Sum_{i=1..ceiling(n/2)-1} i^(i-1)x^i/i!.