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



Is there a bijective proof of an identity enumerating independent sets in cycles?
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$).


