-1

Take a look at the following question,

There is a group of $10$ objects, $2$ red, $3$ blue, and $5$ green. The objects are indistinguishable. In how many ways they can be arranged on a line?

Solution:

$\binom{10}{2}\cdot\binom{8}{3}\cdot\binom{5}{5} = \frac{10!~~~8!~~~5!}{2!8!3!5!5!0!} = \frac{10!}{2!3!5!} = 2520$

What is the formula for this kind of problems so that someone can directly apply the formula to find the result?

YuiTo Cheng
  • 4,705
user366312
  • 1,641
  • Which part of the forumla given in the original post do you not understand? These problems usually stream from Multinomial theory and Inclusion-Exclusion principles. http://www.randomservices.org/random/bernoulli/Multinomial.html – Tony Hellmuth Jun 02 '18 at 12:24
  • A notation for it is $\binom{10}{2,3,5}$ which equals $\frac{10!}{2!3!5!}$ by definition. In this case a trinomial coëfficiënt. – Vera Jun 02 '18 at 12:30
  • 1
    Over reliance on formulas is a trap, especially for problems like this. Much better to think about what the calculation means. You first need to place the red objects, $\binom {10}2$ ways to do that. Then you need to place the blue objects in the open slots, $\binom 83$ ways to do it. Then the remaining five slots are all taken by green objects, so $\binom {10}2\times \binom 83$. – lulu Jun 02 '18 at 13:04

3 Answers3

2

The general formula for the

  • number of arrangements of $n = k_1 + \cdots + k_r$ objects consisting of
  • $r$ groups of
  • $k_1, \ldots , k_r$ indistinguishable objects within each group is $$\frac{n!}{k_1! \cdot \ldots \cdot k_r!}$$

This fraction is also called multinomial coefficient and is written as $\binom{n}{k_1, \ldots ,k_r}$.

By your example you can quickly understand why it works:

  • $n=10=2+3+5$ objects can be arranged in $10!$ ways
  • Consider a given arrangements, then any permutation of the $k_1=2$, $k_2=3$, and $k_3 = 5$ indistinguishable objects reproduces the same arrangement

So, a given permutation appears $k_1!\cdot k_2!\cdot k_3! = 2!\cdot 3! \cdot 5!$ times within the $n!= 10!$ arrangements of all $10$ objects. Hence, in your case it follows that the number of (distinguishable) arrangements is $$\frac{10!}{2!\cdot 3! \cdot 5!}$$

trancelocation
  • 32,243
1

That is usually known as multinomial coefficients.

Rócherz
  • 3,976
0

It is Permutation of multisets. You can think of making different (unique) $10$ letter words from: $$RRBBBGGGGG.$$ Note that there $10!$ permutations of all words in total, however not all unique, because switching places of two $R$s, three $B$s or five $G$s does not change the word. Therefore you must divide by $2!$, $3!$ and $5!$: $$\frac{10!}{2!\cdot 3!\cdot 5!}.$$

farruhota
  • 31,482