Take the 2-minute tour ×
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.

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
1  
@Henning, the case $n=4$ convinces me we're including the leaves. –  Gerry Myerson Nov 26 '11 at 23:30
1  
"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
1  
@HenningMakholm, GIYF. –  Gerry Myerson Nov 27 '11 at 5:27

2 Answers 2

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

The ideas from the Harary paper referenced in the comments are not at all difficult, so I will try to give a summary here.

Start by considering the skeleton of the caterpillar, which is a path / spine with two special end nodes attached at either end by an edge. We will attach legs / leaves (any number of them) to the nodes on the path, excluding the end nodes, which act as leaves, ensuring that the length of the path is preserved when leaves are removed.

Now suppose we have $m$ available slots on the spine. The symmetries here are very simple and the application of the Polya Enumeration Theorem is quite straightforward. The only symmetries appear when the caterpillar is flipped, mapping its lower end to the upper end and vice versa. Therefore the cycle index $Z(Q_m)$ of the two-element permutation group $Q_m$ acting on the slots of the spine is $$Z(Q_m) = \frac{1}{2} (a_1^m + a_2^{m/2})$$ when $m$ is even and $$Z(Q_m) = \frac{1}{2} (a_1^m + a_1 a_2^{(m-1)/2})$$ when $m$ is odd.

The generating function $Q(z)$ of the set of caterpillars is then given by $$\frac{z}{1-z} + \sum_{m\ge 2} Z(Q_m)\left(\frac{z}{1-z}\right)$$ where the second parenthesis denotes cycle index substitution.

Note that one of the nodes placed at a slot on the spine goes onto the spine while the rest form leaves. This is the reason why the repertoire starts at $z$ and not at $1.$ The first term represents the contribution from star graphs, which can be considered caterpillars with a spine consisting of a single node (and thus a path).

Collecting the contributions from odd $m$ and even $m$ as well as the special case $m=1$ we obtain $$Q(z) = \frac{z}{1-z} + \sum_{k\ge 1} Z(Q_{2k})\left(\frac{z}{1-z}\right) + \sum_{k\ge 1} Z(Q_{2k+1})\left(\frac{z}{1-z}\right).$$ The first sum is $$\frac{1}{2} \sum_{k\ge 1} \left(\left(\frac{z}{1-z}\right)^{2k} + \left(\frac{z^2}{1-z^2}\right)^k\right)$$ and simplifies to $$\frac{1}{2} \frac{z^2}{1-2z} + \frac{1}{2} \frac{z^2}{1-2z^2}.$$ The second sum is $$\frac{1}{2} \sum_{k\ge 1} \left(\left(\frac{z}{1-z}\right)^{2k+1} + \frac{z}{1-z} \left(\frac{z^2}{1-z^2}\right)^k\right)$$ and simplifies to $$\frac{1}{2} \frac{z^3}{(1-z)(1-2z)} + \frac{1}{2}\frac{z^3}{(1-z)(1-2z^2)}.$$

Adding the two contributions and the contribution from star graphs we obtain $$Q(z) = \frac{z(1-3z^2)}{(1-2z)(1-2z^2)}.$$ It remains to extract coefficients which can be done e.g. by partial fractions which gives the formula $$2^{n-2} + 2^{\lfloor n/2 \rfloor -1}.$$

Finally recall those two extra nodes at the ends of the path, which must be taken into account, so that the above formula is shifted to $$2^{n-4} + 2^{\lfloor n/2 \rfloor -2}$$ which is the result from the Harary paper.

This is the following sequence (starting at $n=3$): $$1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080,\ldots$$ which is OEIS A005418.

share|improve this answer

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.