Advanced book on Mathematics Olympiad

756 Combinatorics and Probability

Remark.This property is usually phrased as follows: Prove that the number of partitions
ofninto distinct parts is equal to the number of partitions ofninto odd parts.
(L. Euler)

875.The number of subsets with the sum of the elements equal tonis the coefficient of
xnin the product

G(x)=( 1 +x)( 1 +x^2 )···( 1 +xp).

We are asked to compute the sum of the coefficients ofxnforndivisible byp. Call this
numbers(p). There is no nice way of expanding the generating function; instead we
computes(p)using particular values ofG. It is natural to trypth roots of unity.
The first observation is that ifξis apth root of unity, then

∑p

k= 1 ξ

pis zero except

whenξ=1. Thus if we sum the values ofGat thepth roots of unity, only those terms
with exponent divisible bypwill survive. To be precise, ifξis apth root of unity
different from 1, then

∑p

k= 1

G(ξk)=ps(p).

We are left with the problem of computingG(ξk),k= 1 , 2 ,...,p. Fork=p, this is
just 2p. Fork= 1 , 2 ,...,p−1,

G(ξk)=

∏p

j= 1

( 1 +ξkj)=

∏p

j= 1

( 1 +ξj)=(− 1 )p

∏p

j= 1

((− 1 )−ξj)=(− 1 )p((− 1 )p− 1 )

= 2.

We therefore haveps(p)= 2 p+ 2 (p− 1 )= 2 p+ 2 p−2. The answer to the problem
iss(p)=^2
p− 2
p +2. The expression is an integer because of Fermat’s little theorem.
(T. Andreescu, Z. Feng,A Path to Combinatorics for Undergraduates, Birkhäuser
2004)

876.We introduce the generating function

Gn(x)=

(

x+

1

x

)(

x^2 +

1

x^2

)

···

(

xn+

1

xn

)

.

ThenS(n)is the term not depending onxinGn(x). If in the expression
(
x+

1

x

)(

x^2 +

1

x^2

)

···

(

xn+

1

xn

)

=S(n)+

∑

k   = 0

ckxk

we setx=eitand then integrate between 0 and 2π, we obtain