A277795 Number of trees with n unlabeled nodes such that all nodes with degree >2 lie on a single path with length equal to the tree's diameter.
1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 103, 223, 503, 1132, 2602, 5986, 13922, 32433, 75994, 178354, 419945, 990134, 2339033, 5531459, 13097217, 31036235, 73607165, 174677138, 414768535, 985315906, 2341687487, 5567158277, 13239573207, 31494089609, 74935197166, 178332248260, 424473745066
Offset: 0
Keywords
Examples
From _Andrey Zabolotskiy_, Nov 21 2016: (Start)
Three trees that are counted in A000055(10) but not in a(10):
(1)
o o-o-o
| |
o----o
| |
o o-o-o
(2)
o-o-o
|
o-o-o-o
|
o-o-o
(3)
o-o-o-o-o-o-o
|
o-o-o
(End)
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1000
- Andrey Zabolotskiy, Python script for the sequence
Programs
-
PARI
seq(n)={my(s=1+x, p=1+O(x^n), p2=p, q=p, q2=p); for(k=1, n\2, q*=p^2; q2*=p2; p /= 1-x^k; p2 /= 1-x^(2*k); s+=x^(2*k)*(q+q2)*(1+x*p)/2); Vec(s+O(x*x^n))} \\ Andrew Howroyd, Feb 06 2025
Formula
G.f.: Sum_{k>=0} x^(2*k)*(Q(k,x)^2 + Q(k,x^2))*(1 + x*P(k,x))/2, where P(x,k) = 1/Product_{i=1..k} (1-x^i) and Q(x,k) = 1/Product_{i=1..k-1} (1-x^i)^(k-i). - Andrew Howroyd, Feb 06 2025
Extensions
Corrections and more terms from Andrey Zabolotskiy, Nov 21 2016
a(24) onwards from Andrew Howroyd, Feb 06 2025
Comments