login
A356073
Number of labeled trees on [n] having a centroid.
1
0, 1, 0, 3, 4, 125, 486, 16807, 118784, 4782969, 50781250, 2357947691, 33981990912, 1792160394037, 32942263538380, 1946195068359375, 43756164738973696, 2862423051509815793
OFFSET
0,4
COMMENTS
This is the labeled version of A027416 where the pertinent definitions can be found.
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!.
EXAMPLE
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.
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]
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Jul 31 2022
STATUS
approved