Permutation, Combination

The sample space of an experiment of chance is simply a set of possible outcomes of the experiment.

• Permutation The number of arrangements that take $r$ objects from different $n$ objects is
  $${}_{n}P_{r} = n(n-1)(n-2)\cdots (n-r+1) = \frac{n!}{(n-r)!}$$
  Especially， ${}_{n}P_{n} = n!$，$0! = 1$．
• Repeated permutaion The number of arrangements that take $r$ objects from $n$ objects with repetetion is
  $${}_{n}\Pi_{r} = n^{r}$$

• Circular Permutation The number of arrangements which arrange different $n$ pieces in a circle is
  $$(n-1)!$$

• Permutations with repetition The number of permutations of $n$ objects with $p$ identical objects of type 1, $q$ identical objects of type 2, $\ldots$ ?and $r$ identical objects of type k is
  $${n \choose {p,q,\ldots,r}} = \frac{n!}{p! q! \cdots r!}, \ p+q+\cdots +r = n$$

Exercise 1

1. Find the following number of 4-digit integer when arranging 7 numbers from 0 to 6.

(a)

all numbers are different.

(b)

multiple of 5.

(c)

number can be repeated.

2. When arranging 6 cards from the cards numbered from 1 to 10, find the number of outcomes in the following cases．

(a)

all arrangements

(b)

including 1 and 2

(c)

including 1 or 2

3. When tossing a coin 5 times, find the number of outcomes in the following cases.

(a)

The head shows up none，1,2,3,4,5 times

(b)

all cases

4. Find the number of outcomes when arranging $a,b,c,d,e,f$ in the following sequence.

(a)

$a,b$ are next to each other

(b)

$a,b$ are not next to each other

(c)

$a,b$ are place to the each end

5. Show that the number of outcomes when arranging $a,a,a,a,b,b,c,d$ in a sequence is given by ${8 \choose 4,2,1,1}$.

Answer

1

(a) Consider the number of outcomes by putting the integers in $\square \ \square \ \square \ \square$. First of all, it has to be 4-digit integer. Thus we can not use 0 in the thousands. Then we have a choice of one of integers. Thus, there are 6 outcomes. For hundreds through ones, we can use any of the integers. But we can not use the same integer twice. Then there are 6 outcomes in the hundreds, 5 outcomes in the tens, 4 outcomes in the ones. Thus, total of

$$6\cdot6\cdot5\cdot4 = 720$$

(b) Note that multiples of 5 always have a ones digit of 0 or 5．Next, note that the case where the ones digit is 0 and the case where it is 5 are considered separately

When the ones place is 0．

Thousands, hundreds, and tens can use numbers from 1 to 6 once. The number of permutations to take out 3 out of 6 is ${}_6 P_{3}$．Therefore, 120

When the ones place is 5．

We can not use 0 in the thousands. Thus, there are 5 outcomes in the thousands. There are ${}_5P_{2}$ outcomes for the hundreds and tens and $5\cdot {}_5P_{2} = 5\cdot 5 \cdot 4 = 100$ outcomes in the ones. Thus,

$$120 + 100 = 220$$

(c) Here we can use the same number. Now the are 6 outcomes in the thousands and 7 outcomes in the hunreds, tens, and ones.，Therefore,

$$6\cdot {}_7 \Pi_{3} = 6 \cdot 7 \cdot 7 \cdot 7 = 2058 \$$

2

(a) The number of outcomes for taking 6 cards from 10 different cards is ${}_{10} C_{6}$. Now

$${}_{10} C_{6} = \frac{10!}{4! 6!} = \frac{10 \cdot 9 \cdot 8 \cdot 7 }{4 \cdot 3\cdot 2\cdot 1} = 210 \$$

(b) Cards 1 and 2 have to be in the arrangement. So, we consider the number of outcomes of selecting 4 cards from 8 cards. Thus we have ${}_8 C_{4} = 70$．

(c) Let $C_{1}$ be the case where 1 is included and $C_{2}$ be the case where 2 is included. Then there are ${}_9 C_{5}$ outcomes in $C_1$ and ${}_9 C_{5}$ outcomes in $C_2$. Thus, the outcomes for which the card 1 or 2 is included is

$${}_9 C_{5} + {}_9 C_{5} - 70 = 252 - 70 = 182 \$$

3

(a) $A_{i} = [$number of heads is i$]$．Then the heads can be shown $i$ times whithin 5 trials. Thus, the number of outcomes is ${}_5 C_{i}$．

The number of outcomes of $A_{0}$ is ${}_5 C_{0} = 1$，$A_{1}$ is ${}_5 C_{1} = 5$，$A_{2}$ is ${}_5 C_{2} = 10$，$A_{3}$ is ${}_5 C_{3} = 10$， $A_{4}$ is ${}_5 C_{4} = 5$，$A_{5}$ is ${}_5 C_{5} = 1$

(b) In all possible cases, the number of outcomes is ${}_2 \Pi_{5} = 2^5 = 32$.

4

(a) Since $a,b$ are nect to each other，let $A = a,b$. Then we have $A,c,d,e,f$.Thus, the nuber of outcomes is

$${}_5 P_{5} = 5! = 120$$

Also, let $B = b,a$. Then the number of outcomes is

$${}_5 P_{5} = 5! = 120$$

Therefore, total of $240$.

(b) Let $E =$[$a,b$ are not next to each other]. Then $\bar{E} =$[$a,b$ are next to each other]. Thus the number of outcomes of $E =$

$$6! - 240 = 720 - 240 = 480 \$$

(c) $a,b$ are at the ends. Then there are two cases. case 1. $a,c,d,e,f,b$. Then the number of arrangements of $c,d,e,f$ is ${}_4 P_{4}$ case 2. $b,c,d,e,f,a$. Then the number of arrangements of $c,d,e,f$ is ${}_4 P_{4}$. Thus,

$$2 \cdot {}_4 P_{4} = 2 \cdot 4! = 48 \$$

5 ${8 \choose 4,2,1,1} = \frac{8!}{4! 2! 1! 1!}$．If you number all and arrange them, then the number of outcomes is ${}_8 P_{8} = 8!$．But there are 4 $a$'s. 2 $b$'s. They can not be distinguished. So, the number of outcomes is $\frac{8!}{4! 2! 1! 1!}$．