Problem 11898
(American Mathematical Monthly, Vol.123, March 2016) Proposed by R. Stanley (USA).
Let n and k be integers, with n ≥ k ≥ 2. Let G be a graph with n vertices whose components are cycles of length greater than k. Let fk(G) be the number of k-element independent sets of vertices of G. Show that fk(G) depends only on k and n. (A set of vertices is independent if no two of them are adjacent.)
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We will show that for n ≥ k ≥ 2,
fk(G) = fk(Cn) =n k
n − k − 1 k − 1
where Cn si the cycle of length n.
The number kfk(Cn)/n, is the number of k-element independent sets of vertices of Cn where one of the vertices of the independent set is the vertex labeled 1. Then kfk(Cn)/n is equal to the number of solutions of the equation
x1+ x2+ · · · + xk = n − k
where xi> 0 is the number of vertices between two consecutive vertices of the k-element independent set. Therefore
fk(Cn) =n k
n − k − 1 k − 1
. For any positive integer m, let
Pm(x) := 1 +
⌊m/2⌋
X
k=1
m k
m − k − 1 k − 1
xk= Am(x) + Bm(x) with
A(x) = 1 +√ 1 + 4x
2 and B(x) = 1 −√ 1 + 4x
2 .
Now A(x)B(x) = −x, and if n1≤ n2 then
Pn1+n2(x) − Pn1(x)Pn2(x) = (An1+n2(x) + Bn1+n2(x)) − (An1(x) + Bn1(x))(An2(x) + Bn2(x))
= −(A(x)B(x))n1(An2−n1(x) + Bn2−n1(x))
= −(−x)n1(An2−n1(x) + Bn2−n1(x)) ≡ 0 (mod xn1) (1) that is, the polynomials Pn1+n2(x) and Pn1(x)Pn2(x) coincide up to the degree n1− 1.
If the components of G are Cn1, Cn2, . . . , Cnr with
n1+ n2+ · · · + nr= n and k < n1≤ n2≤ · · · ≤ nr
then, by applying r − 1 times the congruence (1), we obtain fk(G) = [xk]
r
Y
j=1
Pnj(x) = [xk]Pn1+n2(x)
r
Y
j=3
Pnj(x)
= [xk]Pn1+n2+n3(x)
r
Y
j=4
Pnj(x) = · · ·
= [xk]Pn(x) = n k
n − k − 1 k − 1
= fk(Cn).
