Question

Find the number of r-permutations of the multiset {∞?1, ∞?2, … , ∞??} such that in
every such permutation each type of an element of the multiset appears at least
once. (You do not need to provide a short answer. Assume r ≥ n.)

Answer 1

Let us consider that the number of r-combinations of the multiset is

Let xj be the number of occurrences of aj where 1≤j≤k. Then we need to find the number of solutions of the equation is

---------------(1)

in the nonnegative integers subject to the restriction that x1≤1

If x1=0, equation 1 reduces to

-----------------(2)

Since there are k−1 terms in the sum, a particular solution of equation 2 corresponds to the placement of k−2 addition signs in a row of r ones. The number of such solutions is

since we must choose which k−2 of the r+k−2 positions for rr ones and k−2 addition signs will be filled with addition signs.

If x1=1, equation 1 reduces to

-----------(3)

In this case, a particular solution of equation 3 corresponds to the placement of k−2 addition signs in a row of r−1 ones. The number of such solutions is

From the Equations 1,2,3 we can consider that..

since we must choose which k−2 of the r−1+k−2=r+k−3 positions for r−1 ones and k−2 addition signs will be filled with addition signs.

Since the two cases are mutually exclusive and exhaustive, the number of solutions of equation 1 is found by adding the results for equations 2 and 3.