Todai Entrance Exam: Math 2016 – Problem 3

(1) Distributing n equivalent balls to r distinguishable boxes is equivalent to choose r - 1 balls from n - 1 balls (first ball always go to first box). These chosen r - 1 balls take the role of bars splitting remaining balls into r boxes. So, the number of possible ways:

    \[ \begin{pmatrix} n-1\\  r-1 \end{pmatrix} = \frac{(n-1)!}{(r-1)!(n-r)!} \]

Reference for validation: Wikipedia

(2) This is the same as choosing n balls from n + m balls (combination):

    \[ \begin{pmatrix} m + n\\  n \end{pmatrix} =\frac{(m+n)!}{n!m!} \]

(3) From (1), there are \begin{pmatrix} n - 1\\  r - 1 \end{pmatrix} ways to distribute n black balls into r boxes and there are \begin{pmatrix} m - 1\\  s - 1 \end{pmatrix} ways to distribute m white balls into s boxes. There are r!s! ways to arrange those boxes in the way such that a black box is followed by a white box and vice versa (this sentence is wrong in the case that there are at least 2 boxes with the same number of balls). In conjunction with the formula in (2), we get:

    \[ P(r,s) = \frac{\begin{pmatrix}  n\\   r - 1  \end{pmatrix}\begin{pmatrix}  m\\   s - 1  \end{pmatrix}r!s!}{\begin{pmatrix}  m + n\\   n  \end{pmatrix}} \]

(4)

    \[ P(r) = P(r,r) + P(r,r+1) + P(r, r-1) \]

(5)

Working…

(6)

    \[ E(r) = \sum_{0}^{\infty} rP(r) \]


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *