Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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)

share|improve this question
Is $n$ the total number of vertices including leaves, or just the length of the spine? – Henning Makholm Nov 26 '11 at 22:57
1  
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
1  
@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

up vote 3 down vote

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.

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.