• Non ci sono risultati.

# Let fk(G) be the number of k-element independent sets of vertices of G

N/A
N/A
Protected

Condividi "Let fk(G) be the number of k-element independent sets of vertices of G"

Copied!
1
0
0

Testo completo

(1)

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



Riferimenti

Documenti correlati

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

[r]

[r]

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. Let N b (k) be the set of

For positive integer n and i ∈ {0, 1}, let D i (n) be the number of derangements on n elements whose number of cycles has the same parity

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. We first show that if n is

in such a way that U 1 receives at least one ball, and while any balls remain, each successive urn receives at least as many balls as in all the previous urns combined.. Let b(n)

[r]