Let $C_m$ be the cycle with $m$ vertices, defined so that $C_1$ has a self-loop on its unique vertex. Let $p_m$ be the generating function enumerating the number of ways to choose $k$ vertices in $C_m$ so that no two are adjacent. Thus the coefficient of $z^k$ in $p_m(z)$ is the number of independent sets in $C_m$ of size $k$.

For instance, $p_1(z) = 1$, $p_2(z) = 1+2z$, $p_3(z) = 1+3z$, $p_4(z) = 1+4z + 2z^2$, $p_5(z) = 1 + 5z+5z^2$ and $p_6(z) = 1 + 6z + 9z^2 + 2z^3$. Set $p_0 = 2$.

It is not hard to show by algebraic arguments (related to the theory of Chebyshev polynomials) that if $\ell, m \in \mathbb{N}_0$ with $\ell \ge m$ then

$$p_\ell p_m = p_{\ell+m} + (-1)^m z^{m} p_{\ell-m}.$$

In particular, $p_m^2 = p_{2m} + 2(-1)^m z^{m}$, and so if $k < m$ then the coefficients of $z^k$ in $p_m^2$ and $p_{2m}$ are equal. I would like a bijective proof of this, or ideally, of the more general identity above.

Is there a bijective proof that if $k < m$ then the number of independent sets of size $k$ in the disjoint union $C_m \sqcup C_m$ is equal to the number of independent sets of size $k$ in $C_{2m}$?

American Math. Monthly123(March 2016), but the published solution (in a later issue that I don't have a reference for) is not bijective. $\endgroup$ – Richard Stanley Jul 6 '20 at 19:59The American Math. Monthly125(January 2018). $\endgroup$ – RobPratt Jul 6 '20 at 21:10