Is there a bijective proof of an identity enumerating independent sets in cycles?

Question

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}$?

Answer 1

It seems that I’ve seen this question here before, but I am not sure whether it had a bijective answer. Anyway, here you are.

Enumerate the vertices in two copies of $C_m$ as $1,2,\dots,m$ and $1’,2’,\dots,m’$, respectively. Take any independent set of size $k<m$ in the union of these cycles (regard it as marking some vertices). Choose the smallest $i$ such that both $i$ and $i’$ are not in the set. Arranging the vertices in the order $$ 1,2,\dots,i,(i+1)’,(i+2)’,\dots, m’, 1’, \dots,i’,i+1,i+2,\dots,m $$ you get a $C_{2m}$ with an independent set being marked.

The inverse map is to take $k$ marked vertices in $C_{2m}$, choose the smallest $i$ such that both $i$ and $i+m$ are not marked, cut $C_{2m}$ after them, and glue into two copies of $C_m$.

The same argument works for an arbitrary number of copies of $C_m$ (and still $k<m$).