todai-math 2016 Q3

todai-math · Japan · translated Combinations & Selection Counting Integer Solutions to Equations
Answer the following questions.
(1) Calculate the number of possible ways to distribute $n$ equivalent balls to $r$ distinguishable boxes such that each box contains at least one ball, where $n \geq 1$ and $1 \leq r \leq n$.
Next, consider to place $n$ black balls and $m$ white balls in a line uniformly at random. A run is defined to be a succession of the same color. Let $r$ be the number of runs of black balls and $s$ be the number of runs of white balls. Assume that $n \geq 1 , m \geq 1,1 \leq r \leq n$, and $1 \leq s \leq m$.
(2) Calculate the total number of arrangements when we do not distinguish among balls of the same color.
(3) Calculate the probability $P ( r , s )$ that the number of runs of black balls is $r$ and the number of runs of white balls is $s$.
(4) Calculate the probability $P ( r )$ that the number of runs of black balls is $r$.
(5) Using $( 1 + x ) ^ { n } ( 1 + x ) ^ { m } = ( 1 + x ) ^ { n + m }$, show that the following equations hold.
$$\begin{aligned} \sum _ { \ell = 0 } ^ { \min \{ n , m \} } \binom { n } { \ell } \binom { m } { \ell } & = \binom { n + m } { m } \\ \sum _ { \ell = 0 } ^ { \min \{ n - 1 , m \} } \binom { n } { \ell + 1 } \binom { m } { \ell } & = \binom { n + m } { m + 1 } \end{aligned}$$
(6) Calculate the expected value $E ( r )$ and the variance $V ( r )$ of $r$.
Calculate $\lim _ { N \rightarrow \infty } \frac { E ( r ) } { N }$ and $\lim _ { N \rightarrow \infty } \frac { V ( r ) } { N }$ supposing that $N = n + m$ and $\lim _ { N \rightarrow \infty } \frac { n } { N } = \lambda$, where $\lambda$ is a real constant.
Answer the following questions.

(1) Calculate the number of possible ways to distribute $n$ equivalent balls to $r$ distinguishable boxes such that each box contains at least one ball, where $n \geq 1$ and $1 \leq r \leq n$.

Next, consider to place $n$ black balls and $m$ white balls in a line uniformly at random. A run is defined to be a succession of the same color. Let $r$ be the number of runs of black balls and $s$ be the number of runs of white balls. Assume that $n \geq 1 , m \geq 1,1 \leq r \leq n$, and $1 \leq s \leq m$.

(2) Calculate the total number of arrangements when we do not distinguish among balls of the same color.

(3) Calculate the probability $P ( r , s )$ that the number of runs of black balls is $r$ and the number of runs of white balls is $s$.

(4) Calculate the probability $P ( r )$ that the number of runs of black balls is $r$.

(5) Using $( 1 + x ) ^ { n } ( 1 + x ) ^ { m } = ( 1 + x ) ^ { n + m }$, show that the following equations hold.

$$\begin{aligned}
\sum _ { \ell = 0 } ^ { \min \{ n , m \} } \binom { n } { \ell } \binom { m } { \ell } & = \binom { n + m } { m } \\
\sum _ { \ell = 0 } ^ { \min \{ n - 1 , m \} } \binom { n } { \ell + 1 } \binom { m } { \ell } & = \binom { n + m } { m + 1 }
\end{aligned}$$

(6) Calculate the expected value $E ( r )$ and the variance $V ( r )$ of $r$.

Calculate $\lim _ { N \rightarrow \infty } \frac { E ( r ) } { N }$ and $\lim _ { N \rightarrow \infty } \frac { V ( r ) } { N }$ supposing that $N = n + m$ and $\lim _ { N \rightarrow \infty } \frac { n } { N } = \lambda$, where $\lambda$ is a real constant.
Paper Questions