HSE Basic counting

Counting

Ordered Selection

Suppose there are 20 songs in your mp3 collection. The computer is asked to randomly selected 10 songs and play them in the order they are selected, how many ways are there to select the 10 songs? This type of problems is called ordered selection counting, as the order in which the things are selected is important. E.g. if one selection is

1, 2, 3, 4, 5, 6, 7, 8, 9 and 10

then

2, 1, 3, 4, 5, 6, 7, 8, 9 and 10

is considered a different selection.

There are 20 ways to choose the first song since there are 20 songs, then there are 19 ways to choose the second song and 18 ways to choose the third song ... and so on. Therefore the total number of ways can be calculated by considering the following product:

20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11

or denoted more compactly:

$\frac{20!}{10!}$

Here we use the factorial function, defined by $0!=1$ and $n!=(n-1)!\times n$. (In other words, $n!=1\times 2\times 3\times ...\times n$)

In general, the number of ordered selections of m items out of n items is:

$\frac{n!}{(n-m)!}$

The idea is that we cancel off all but the first m factors of the n! product.

Unordered Selection

Out of the 15 people in your mathematics class, five will be chosen to represent the class in a school wide mathematics competition. How many ways are there to choose the five students? This problem is called an unordered selection problem, i.e. the order in which you select the students is not important. E.g. if one selection is

Joe, Lee, Sue, Britney, Justin

another selection is

Lee, Joe, Sue, Justin, Britney

the two selections are considered equivalent.

There are

$\frac{15!}{10!}$

ways to choose the 5 candidates in ordered selection, but there are 5! permutations of the same five candidates. (That is, 5! different permutations are actually the same combination). Therefore there are

$\frac{15!}{10!5!}$

ways of choosing 5 students to represent your class.

In general, to choose (unordered selection) m candidates from n, there are

$\frac{n!}{m!(n-m)!}=(\genfrac{}{}{0ex}{}{n}{m})$

ways. We took the formula for ordered selections of m candidates from n, and then divided by m! because each unordered selection was counted as m! ordered selections.

Note: $(\genfrac{}{}{0ex}{}{n}{m})$ is read "n choose m".

Examples

Example 1 How many different ways can the letters of the word BOOK be arranged?

Solution 1 4! ways if the letters are all distinct. Since O is repeated twice, there are 2! permutations. Therefore there are 4!/2! = 12 ways.

Example 2 How many ways are there to choose 5 diamonds from a deck of cards?

Solution 2 There are 13 diamonds in the deck. So there are $(\genfrac{}{}{0ex}{}{13}{5})$ ways.

$(\genfrac{}{}{0ex}{}{13}{5})=\frac{13!}{8!5!}=\frac{13\times 12\times 11\times 10\times 9}{120}=1287$

Binomial expansion

The binomial expansion deals with the expansion of following expression

$(a+b{)}^n$

Take n = 3 for example, we shall try to expand the expression manually we get

$(a+b{)}^3$	$=(aa+ab+ba+bb)(a+b)$
	$=aaa+aab+aba+abb+baa+bab+bba+bbb$

We deliberately did not simplify the expression at any point during the expansion, we didn't even use the well known (a + b)² = a² + 2ab + b². As you can see, the final expanded form has 8 terms. They are all the possible terms of powers of a and b with three factors!

Since there are 3 factors in each term and all the possibles terms are in the expanded expression. How many terms are there with only one b? The answer should be $(\genfrac{}{}{0ex}{}{3}{1})$, i.e. from 3 possible positions, choose 1 for b. Similarly we can work out all the coefficient of like-terms. So

$(a+b{)}^3$

$=(\genfrac{}{}{0ex}{}{3}{0})a^3+(\genfrac{}{}{0ex}{}{3}{1})a^{2}b+(\genfrac{}{}{0ex}{}{3}{2})a{b}^2+(\genfrac{}{}{0ex}{}{3}{3})b^3$

And more generally

$(a+b{)}^n$

$=(\genfrac{}{}{0ex}{}{n}{0})a^n+(\genfrac{}{}{0ex}{}{n}{1})a^{n-1}b+(\genfrac{}{}{0ex}{}{n}{2})a^{n-2}{b}^2+...(\genfrac{}{}{0ex}{}{n}{n-1})a{b}^{n-1}+(\genfrac{}{}{0ex}{}{n}{n})b^n$

or more compactly using the summation sign (otherwise known as sigma notation)

$(a+b{)}^n$

$=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})a^{n-i}{b}^i$