Principles of Mathematics in Operations Research

Solutions 209

not taking Mathematics for O.R. out of n — r M.E.T.U. students not taking

Mathematics for O.R. These two are equivalent.

(e)(s)+rr

l

)+-+(

B

r) = (

B+

r

r+1

):

Trivial:

Apply item (b) r-times to the right hand side.

Combinatorial Method:
The right hand side, (n+^+1), denotes the number of different ways of selecting
r balls out of m — n + 2 balls with repetition, known as the multi-set problem.
Let | be the column separator if we reserve a column for each of m objects, let
\J be used as the tally mark if the object in the associated column is selected.
Then, we have a string of size r + (m — 1) in which there are r tally marks
and m — 1 column separators. For instance, if we have three objects {x, y, z},
and we sample four times, "\/l\A/lv/" means x and z are selected once and y
is selected twice. Then, the problem is equivalent to selecting the places of r
tally marks in the string of size r + (m — 1), which is (r+™_1).
Let us fix the super ball again. The left hand side is the list of the number
of times that the super ball is selected in the above multi-set problem instance.
That is, (Q) refers to the case in which the super ball is not selected, (n~J~ )
refers to the case in which the super ball is selected once, and (n+r) refers to
the case in which the super ball is always selected.
These two are equivalent.