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 A_{1}, . . . , A_{n}.

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 A_{1}, . . . , A_{n} 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 A_{1}, . . . , A_{n} is counted

r

X

i=1

r i

n − r j − i

=n j

−n − r j

times in Sj where ^{r}_{i} is the number of ways to choose i of the r sets and ^{n−r}_{j−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−1}Sj
n

X

k=m

(−1)^{n−k}

j n − k

=

n

X

j=1

(−1)^{j−1}Sj
n−m

X

k=0

(−1)^{k}j
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−m}k − 1
m

Tk

where T_{k}=P

|J|=k

T

j∈JA_{j}

. Moreover for k = 1, . . . , n,
S_{k} =

k

X

j=1

(−1)^{j−1}n − j
k − j

T_{j} and T_{k} =

k

X

j=1

(−1)^{j−1}n − j
k − j

S_{j}.