China Mathematical Competition

Question

It is given that there are two sets of real numbers

A = {a_{1}, a_{2}, \dots, a_{100}}

and

B = {b_{1}, b_{2}, \dots, b_{50}}

. If there is a mapping

f

from

A

to

B

such that every element in

B

has an inverse image and

f (a_{1}) \leq f (a_{2}) \leq \dots \leq f (a_{100}),

then the number of such mappings is ( ).

(A)

C_{100}^{50}

(B)

C_{50}^{50}

(C)

C_{100}^{49}

(D)

C_{50}^{49}

Accepted Answer

We might as well suppose b_1 < b_2 < < b_50, and divide elements a_1, a_2, , a_100 in A into 50 nonempty groups according to their order. Define a mapping f: A B, so that the images of all the elements in the i-th group are b_i (i = 1, 2, , 50) under the mapping. Obviously, f satisfies the requirements given in the problem. Furthermore, there is a one-to-one correspondence between all groups so divided and the mappings satisfying the condition. So the number of mappings f satisfying the requirements is equal to the number of ways dividing A into 50 groups according to the order of the subscripts. The number of ways dividing A is C_99^49. Then there are, in all, C_99^49 such mappings. Answer: D.