• Non ci sono risultati.

Sn the number of elements that belong to exactly m of the sets A1

N/A
N/A
Protected

Academic year: 2021

Condividi "Sn the number of elements that belong to exactly m of the sets A1"

Copied!
1
0
0

Testo completo

(1)

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.

Riferimenti

Documenti correlati

Government Printing Office , Social Security Administration (US)..

There- fore an important development of the present work would be represented by the implementation of the developed algorithms on GPU-base hardware, which would allow the

When an aqueous solution of metal ion is shaken with an immiscible organic solvent containing such an organic ligand, the metal-ion complex is distributed between the two phases..

decreases the activation energy of the forward reaction and increases the activation energy of the reverse reaction.. increases the activation energy of the forward reaction

[r]

[r]

[r]

Let µ be the M¨ obius function of