Problem 11775
(American Mathematical Monthly, Vol.121, May 2014) Proposed by I. Sofair (USA).
Let A1, . . . , An be finite sets. For k = 1, . . . , n, let Sk =P
|J |=k
S
j∈JAj
with J ⊆ {1, . . . , n}.
(a) Express in terms of S1, . . . , Sn the number of elements that belong to exactly m of the sets A1, . . . , An.
(b) Same question as in (a), except that we now require the number of elements belonging to at least m of the sets A1, . . . , An.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
(a) The number of elements that belong to exactly 1 ≤ m ≤ n of the sets A1, . . . , An is em= (−1)n−m
n
X
j=n−m
(−1)j−1
j n − m
Sj.
In fact, an element that is in exactly r of the sets A1, . . . , An is counted
r
X
i=1
r i
n − r j − i
=n j
−n − r j
times in Sj where ri is the number of ways to choose i of the r sets and n−rj−i is the number of ways complete a set of j elements. Therefore, in the above formula, such an element is counted
(−1)n−m
n
X
j=n−m
(−1)j
j n − m
n − r j
−n j
=
1 if r = m, 0 otherwise, times because for 0 ≤ t ≤ n,
n
X
j=n−m
(−1)j
j n − m
n − t j
= n − t n − m
n
X
j=n−m
(−1)j
m − t j − (n − m)
= (−1)n−m n − t n − m
(1 − 1)m−t=
(−1)n−m if t = m,
0 otherwise,
(b) The number of elements belonging to at least 1 ≤ m ≤ n of the sets A1, . . . , An is am=
n
X
k=m
ek=
n
X
k=m
(−1)n−k
n
X
j=n−k
(−1)j−1
j n − k
Sj=
n
X
j=1
(−1)j−1Sj n
X
k=m
(−1)n−k
j n − k
=
n
X
j=1
(−1)j−1Sj n−m
X
k=0
(−1)kj k
= (−1)n−m
n
X
j=n−m+1
(−1)j−1 j − 1 n − m
Sj.
Note that in a similar way one can prove that
em=
n
X
k=m
(−1)k−m k m
Tk and am=
n
X
k=m
(−1)k−mk − 1 m
Tk
where Tk=P
|J|=k
T
j∈JAj
. Moreover for k = 1, . . . , n, Sk =
k
X
j=1
(−1)j−1n − j k − j
Tj and Tk =
k
X
j=1
(−1)j−1n − j k − j
Sj.
