# On the number of caterpillars

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)

-
Is $n$ the total number of vertices including leaves, or just the length of the spine? – Henning Makholm Nov 26 '11 at 22:57
Also, is the vertex set labeled or not? – Dimitrije Kostic Nov 26 '11 at 23:12
@DimitrijeKostic My guess is unlabeled because there are $n!$ labeled paths already and presumably many more caterpillars. – Srivatsan Nov 26 '11 at 23:24
@Henning, the case $n=4$ convinces me we're including the leaves. – Gerry Myerson Nov 26 '11 at 23:30
"It should use Polya's Theorem" why? Mathematicians usually take any proof we can get, no matter what theorem it uses. Is this, by any chance, a homework problem? NTTAWWT, but, if it is a homework problem, it should have a homework tag. – Gerry Myerson Nov 27 '11 at 0:22
show 2 more comments

## 1 Answer

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.

-
BTW the article is available here: deepblue.lib.umich.edu/bitstream/2027.42/33977/1/0000249.pdf – Martin Sleziak Nov 27 '11 at 8:41