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

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

• But how do you prove that identity? A priori the $p_m$ are just some polynomials, which of their properties do you use in the proof? – მამუკა ჯიბლაძე Jul 6 at 19:27
• I think this is in I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Mathematica 24 (1983) 97-106. – Martin Rubey Jul 6 at 19:50
• The result also appears as Problem 11898, American Math. Monthly 123 (March 2016), but the published solution (in a later issue that I don't have a reference for) is not bijective. – Richard Stanley Jul 6 at 19:59
• The solution appears in The American Math. Monthly 125 (January 2018). – RobPratt Jul 6 at 21:10
• Here is a link to R. Tauraso's solution: mat.uniroma2.it/~tauraso/AMM/AMM11898.pdf. Incidentally Richard is very modestly not mentioning that he proposed the problem. – Mark Wildon Jul 8 at 11:22

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