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)
 A: 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. 
A: 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.
