High School Mathematics Extensions/Supplementary/Basic Counting

From Wikibooks, open books for an open world
< High School Mathematics Extensions‎ | Supplementary
Jump to: navigation, search
High School Mathematics Extensions/Supplementary
Basic Counting Polynomial Division

Ordered selection (Permutation)[edit]

Suppose there are twenty songs in your music collection. The computer is asked to randomly select ten songs and play them in the order they are selected, how many ways are there to select the ten songs? This type of problem is called ordered selection (permutation) counting, as the order in which the things are selected is important. For example, these selections are considered different:

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

There are twenty ways to choose the first song since there are twenty songs, there are nineteen ways to choose the second song since there are nineteen songs left, eighteen ways to choose the third song, and so forth. The total number of ways can be calculated as follows:

20 \times 19 \times 18 \times 17 \times 16 \times 15 \times 14 \times 13 \times 12 \times 11

or denoted more compactly:

\frac {20!} {10!}

Here we use the factorial function, defined by

0! = 1
n! = n \times (n-1)!

In other words,

n! = 1 \times 2 \times 3 \times ... \times n

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


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

When m equals n we are talking about the number of permutations of n items:

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

Permutation with repetition[edit]

How many different three-digit numbers can be formed with only odd prime digits (3, 5, 7)?

This is a special case of permutations, where items may be selected more than once. If we were to select m items out of n, for every selection, we would have n possibilities. Since there are m selections, we may calculate all the arrangements as a product of m factors n, that is:

\underbrace{n \times n \times n ... \times n}_{\text{m times}} = n^{m}

There are

3^{3} = 27

different three-digit numbers with only odd primes digits.

Circular permutation[edit]

In how many ways can we sit four people at a round table?

This is another special case of permutations, the n elements are arranged in a circular order, in which the start and end of the arrangement are undefined. Selections like

  • \text{A, B, C, D, E}
  • \text{E, A, B, C, D}
  • \text{D, E, A, B, C}
  • \text{C, D, E, A, B}
  • \text{B, C, D, E, A}

are considered equivalent.

This kind of problem is solved by forcibly defining a start point for the selection, in other words, fixing one element (the first one) and permute the other n - 1 left:

(n - 1)!

There are

(4 - 1)! = 3! = 6

ways to sit four people at a round table.

Unordered selection (Combination)[edit]

Out of the fifteen 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 (combination) problem, the order in which you select the students is not important. For example, these selections are considered equivalent:

\text{Joe, Lee, Sue, Violet, Justin}
\text{Lee, Joe, Sue, Justin, Violet}

There are


ways to choose the five candidates in ordered selection, but there are 5! permutations of the same five candidates for each different group. That is, 5! different permutations represent the same combination. This means we are counting each combination 5! times. Consequently, there are

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

ways of choosing five students to represent your class.

In general, the number of ways to choose m items out of n items is:

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

We took the formula for permutations of m items from n, and then divided by m! because each combination was counted as m! ordered selections (m! times). This formula is denoted by:

{n \choose m} = \frac{n!}{(n-m)! \times m!}

Note that {n \choose m} is often read as n choose m.

Combination with repetition[edit]

In this particular case of combination problems, elements may be selected more than once. Groups can include many samples of the same element.

In order to solve this kind of situations, we should define each possible selection, not by the elements selected, but the amount of samples selected from each. Both definitions are, essentially, the same. Suppose m elements out of n are to be chosen. We create n sets representing each available element, and m objects representing each sample (item, selected element) of the resulting selection. Then we place on every set as many objects as samples we selected from the element the set represented. The final step is to concatenate a string to identify the selection, for instance, representing each object (sample) with a square and set (element which the sample makes reference to) boundaries with a dash:

-\underbrace{{\blacksquare}{\blacksquare}{\blacksquare}}_{\text{First set/element}}-\underbrace{{\blacksquare}{\blacksquare}}_{\text{Second set/element}}-\underbrace{{\blacksquare}{\blacksquare}}_{\text{Third set/element}}-

This means we chose three samples from the first set (first element), two from the second set (second element), two from the third set (third element). In other words, the selection consists of three elements of the first kind, two elements of the second kind, two elements of the third kind. The string could represent a random group of five letters formed, solely, with letters A, B, C:

\text{A, A, A, B, B, C, C}

The concatenated strings consist of m squares, and n + 1 dashes. For example, the following represents three elements selected out of five:

-\underbrace{{\blacksquare}{\blacksquare}}_{\text{First set/element}}-\underbrace{}_{\text{Second set/element}}-\underbrace{{\blacksquare}}_{\text{Third set/element}}-\underbrace{}_{\text{Forth set/element}}-\underbrace{}_{\text{Fifth set/element}}-

Note that two dashes are fixed, and the other n - 1 are positioned along the string forming n sets of samples. There are n - 1 + m movable characters among n - 1 + m positions. The number of possible strings equals the number of ways to position m squares among n - 1 + m, in other words, the number of ways to choose m positions out of n - 1 + m:

{{n - 1 + m} \choose {m}}

Analogously, we could talk about positioning the n - 1 dashes among the n - 1 + m:

{{n - 1 + m} \choose {n - 1}}

Since every string exclusively determines one selection or group, clearly the number of strings is equivalent to the number of groups or selections possible.

If we were to pack three fruits for long journey, and you only got bananas, apples, oranges, peaches, and kiwis, there would be

{{5 - 1 + 3} \choose {3}} = {{5 - 1 + 3} \choose {5 - 1}} = 35

possible groups to pack.

Binomial coefficient[edit]

The binomial coefficient

{n \choose m}

expresses the number of unordered groups that can be formed by choosing m elements from a set containing n.

These are some basic and useful properties:

  • The number of ways of choosing m elements out of n equals the number of ways of not choosing the remaining n - m out of the n elements. A group of selected elements defines another group of non selected elements.
{n \choose m} = {n \choose {n - m}}

  • There is only one way to choose no elements, or to not choose them all.
{n \choose 0} = {n \choose n} = 1

  • There are n ways of choosing one element, or not choosing n - 1.
{n \choose 1} = {n \choose {n - 1}} = n

  • The difference between
{n \choose m}
{{n + 1} \choose m}
is that in the first formula we are not counting the groups which include the element added in the second formula. The amount of groups size m which include a particular element from a set with n + 1 elements is
{{(n + 1) - 1} \choose {m - 1}} = {n \choose {m - 1}}
{{n + 1} \choose m} = {n \choose m} + {n \choose {m - 1}}

  • The difference between
{n \choose {m + 1}}
{n \choose m}
is that in the first formula we are counting groups with one more element than the ones in the second formula. Every group size m needs one "missing" element of the n - m remaining in order to grow to size m - 1.
{n \choose m} \times (n - m)
However, we must observe that we are counting every group size m + 1 many times, m + 1 times indeed. This is because the "missing" element can be any of the m + 1 elements in the resulting group, in other words, m + 1 groups size m (when associated with the right element) will formed the same group size m + 1. How many groups size m can we formed by removing an element from a group size m + 1?
{{m + 1} \choose 1} = m + 1
This suggests
{n \choose {m + 1}} = {n \choose m} \times \frac{n - m}{m + 1}

Binomial expansion[edit]

The binomial expansion describes the algebraic expansion of following expression:

(a + b)^n

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

(a + b)^2 = (a+b)(a+b) = aa + ab + ba + bb

Take n = 3:

(a + b)^3 = (a+b)(a+b)(a+b) = aaa + aab + aba + abb + baa + bab + bba + bbb

We deliberately did not simplify the expression at any point during the expansion. As you can see, the final expanded form has four and eight terms, respectively. These terms are all the possible combinations of a and b in products of two and three factors, respectively.

The number of factors equals the number of binomials (a + b) in the first product, which in turn equals n.


(a + b)^n

there are n factors in each term. How many terms are there with only one b? In other words, in how many ways can I place one b among n different positions? Or even better, in how many ways can I pick one position (to place a b) out of n?

{n \choose 1}

Similarly we can work out all the coefficients of the other terms:

(a + b)^3 = {3 \choose 0}a^3 + {3 \choose 1}a^2b + {3 \choose 2}ab^2 + {3 \choose 3}b^3

And more generally:

(a + b)^n = {n \choose 0}a^n + {n \choose 1}a^{n-1}b + {n \choose 2}a^{n-2}b^2 + ... {n \choose n-1}ab^{n-1} +  {n \choose n}b^n

Or more compactly using the summation operator:

(a + b)^n = \sum_{i = 0}^n {n \choose i}a^{n-i}b^i


Exercise 1[edit]

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

Exercise 2[edit]

How many ways are there to choose five diamonds from a deck of cards?

Exercise 3[edit]

Joey wants to make himself a sandwich. He will use ham, cheese, salami, tomato, and lettuce but does not like the ham and the salami to be touching each other. He always puts the lettuce on top. In how many ways can Joey arrange the ingredients of his sandwich?

Exercise 4[edit]

Rachel wants to buy an ice-cream cup. She picks three different flavours from a total of ten but does not like mixing chocolate with vanilla. How many different ice-cream cups can Rachel order?

Exercise 5[edit]

Joey is still hungry and wants to eat another sandwich. He can use ham, cheese, salami, tomato, and lettuce (there is no need to use them all). He does not want the ham and the salami to be in the same sandwich. How many different sandwiches can Joey make (the order of the ingredients inside the sandwich does not matter)?

Solutions to exercises