Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The probability of choosing $(n_1, \space n_2, \space \cdots \space n_k)$ randomly from a set of $(N_1, \space N_2, \space \cdots \space N_k)$ such that for $1\le i\le k, \space i\in \mathbb N$

  • $n_i \le N_i$
  • $\displaystyle \sum_{1\le i\le k} n_i = n$
  • $\displaystyle \sum_{1\le i\le k} N_i = N$
  • $p_i = \cfrac {N_i}{n_i}$

is $$\cfrac {n!} {n_1!\cdots n_k!}p_1^{n_1}\cdots p_k^{n_k}$$ The number of possible outcome is $N^n$ while the number of required outcome is $\cfrac {n!} {n_1!\cdots n_k!} N_1^{n_1}\cdots N_k^{n_k}$.

My question breaks down to proving that $$\displaystyle \prod_{1\le i\le k} \left(\! \begin{array}{c} n - (n_1 + n_2 + \cdots +n_{i-1}) \\ n_i \end{array} \!\right) = \cfrac {n!} {n_1!\cdots n_k!}$$

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Note that you have $\binom nk = \frac{n!}{k!(n-k)!}$ and hence \begin{align*} \prod_{i=1}^k \binom{n - (n_1 + \cdots + n_{i-1})}{n_i} &= \prod_{i=1}^k \frac{\bigl(n - (n_1 + \cdots + n_{i-1})\bigr)!}{n_i!\cdot \bigl(n - (n_1 + \cdots + n_{i-1} + n_i)\bigr)!}\\ &= \prod_{i=1}^k \frac 1{n_i!} \prod_{i=1}^k \frac{\bigl(n - (n_1 + \cdots + n_{i-1})\bigr)!}{\bigl(n - (n_1 + \cdots + n_{i-1} + n_i)\bigr)!}\\ &= \prod_{i=1}^k \frac 1{n_i!} \cdot \frac{n!}{\bigl(n-(n_1 + \cdots + n_k)\bigr)!}\\ &= \frac{n!}{n_1! \cdots n_k!} \end{align*} so its just your term in another form.

share|improve this answer
    
why do you have double product there and how did $n!$ appear? –  user31280 Oct 25 '12 at 11:27
    
$n!$ is the numerator of the first product for $i = 1$ (then there is no $n_j$ to be subtracted) and the "double" product arises from $\prod_i a_i b_i = \prod_i a_i \cdot \prod_i b_i$ –  martini Oct 25 '12 at 11:45
    
i didn't see the telescoping product before! thanks!! –  user31280 Oct 26 '12 at 23:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.