A caterpillar is a tree with the property that if all the leafs are removed then what remains is a path. Could you help me to prove that there are $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ caterpillar on $n$ vertices, $n\geq3$?
(It should use Polya's theorem)
A reference is Frank Harary and Allen J. Schwenk, The number of caterpillars, Discrete Mathematics 6 (1973) 359–365. Have a look, and report back to us on what you find.