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,5

Comments

First differs from A000055 at a(10).

First differs from A130131 at a(10), n >= 1.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Andrey Zabolotskiy, Python script for the sequence

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

Example

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)

Prog

(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

Crossrefs

Cf. A000055, A130131.

Sequence in context: A359392 A199142 A090344 * A389602 A198662 A198620

Adjacent sequences: A277792 A277793 A277794 * A277796 A277797 A277798

Keyword

nonn

Author

Gabriel Burns, Oct 31 2016

Extensions

Corrections and more terms from Andrey Zabolotskiy, Nov 21 2016

a(24) onwards from Andrew Howroyd, Feb 06 2025

Status

approved