2
$\begingroup$

We have $n_1$ number of balls each labelled by the number $1$, $n_2$ number of balls each labelled $2$,..., $n_k$ number of balls each labelled $k$. In how many ways can we permute them in $r$ number of boxes assuming each box can hold exactly $1$ ball.

Edit:

Finding permutations for $n_1$ + $n_2$ + ... + $n_k$ = $r$ would be the same as finding permutations with repetition. Moreover if we have $n_1$ + $n_2$ + ... + $n_k$ < $r$ we may introduce $r$ - ($n_1$ + $n_2$ + ... + $n_k$) balls of another type and find permutations with repetition for $r$ total balls. So finding permutations for $n_1$ + $n_2$ + ... + $n_k$ > $r$ would be enough to answer this question.

$\endgroup$
  • $\begingroup$ Hint: How many ways are there to permute $N$ objects in $r$ ways given that there are $n_k$ repetitions in the $N$ objects for each $k$ ? $\endgroup$ – Prasun Biswas Oct 8 '17 at 10:31
  • $\begingroup$ @HDatta - I didn't get the significance of adding $r$ - ($n_1$ + $n_2$ + ... + $n_k$) balls when total balls $< r$. Would you pls write down your solution for this case! $\endgroup$ – KGhatak Oct 14 '17 at 18:28
  • $\begingroup$ @KGhatak By adding extra balls the total no. of balls become $r$. These new balls just represent empty boxes. So permutation with repetition for $r$ balls should give us the solution for this case. $\endgroup$ – HDatta Oct 14 '17 at 18:32
  • $\begingroup$ @HDatta - So, are you saying # of ways arranging 2 red and 3 blue balls in 5 boxes is same as the # ways we can arrange a red and a blue balls in 5 boxes? Not sure if I'm missing anything! maybe writing exact answer might eliminate the confusion!! $\endgroup$ – KGhatak Oct 14 '17 at 18:54
  • $\begingroup$ @KGhatak - The balls added are of another kind acting just as empty sapces. For example if we want to find all arrangements for $n_1$ = $2$, $n_2$ = $3$ and $r$ = $7$ then we may introduce $n_3$ = $2$ balls of another kind and find permutations for $r$ total balls with repetitions. $\endgroup$ – HDatta Oct 15 '17 at 3:15
0
$\begingroup$

We have $ \sum_{i=1}^{k} n_i \leq r$. There are $ \binom{r}{n_1}$ ways to place the $1$'s. Then there are $ \binom{r-n_1}{n_2}$ ways to place the $2$'s. ... multiplying these binomial coefficients together gives the multinomial coeffiecient

\begin{eqnarray*} \binom{r}{n_1 , n_2, \cdots , n_k,r-\sum_{i=1}^{k} n_i}. \end{eqnarray*}

$\endgroup$
  • $\begingroup$ I didn't specify that n_1 + n_2 +...+n_k add up to r. They could be equal greater than or lesser than r. $\endgroup$ – HDatta Oct 7 '17 at 14:40
  • $\begingroup$ Thank you for responding earlier. I know that I am late but I still updated my question to clarify things a bit. Could you please have a look at this question again? $\endgroup$ – HDatta Oct 14 '17 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.