High School Mathematics Extensions/Supplementary/Basic Counting
All supplementary chapters contain materials that are part of the standard high school mathematics curriculum, therefore the material is only provided for completeness and should mostly serve as revision.
Ordered selection (Permutation)
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:
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:
or denoted more compactly:
Here we use the factorial function, defined by
In other words,
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:
Permutation with repetition
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:
different three-digit numbers with only odd primes digits.
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
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:
ways to sit four people at a round table.
Unordered selection (Combination)
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:
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
ways of choosing five students to represent your class.
In general, the number of ways to choose m items out of n items is:
Note that is often read as n choose m.
Combination with repetition
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:
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:
The concatenated strings consist of m squares, and n + 1 dashes. For example, the following represents three elements selected out of five:
Note that two dashes are fixed, and the other n - 1 are positioned in 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:
Analogously, we could talk about positioning the n - 1 dashes among the n - 1 + m:
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
possible groups to pack.
The binomial expansion describes the algebraic expansion of following expression:
Take n = 2 for example, we shall try to expand the expression manually, we get
Take n = 3:
Take n = 4:
We deliberately did not simplify the expression at any point during the expansion. As you can see, the final expanded form has four, eight, sixteen terms, respectively. They are all the possible products of a and b with two, three, four factors, respectively.
The number of factors equals the number of binomials (a + b) in the first product, which in turn equals n.
there are n factors in each term and all the possibles terms in the expanded expression. 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?
Similarly we can work out all the coefficients of the other terms:
And more generally:
Or more compactly using the summation operator:
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
notchoosing the remaining n - m out of the n elements. A group of selected elements defines another group of non selected elements.
- There is only one way to choose no elements, or to
notchoose them all.
- There are n ways of choosing one element, or
notchoosing n - 1.
- The difference between
- 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
- The difference between
- 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.
- 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 size m + 1, 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?
- This suggests
How many different ways can the letters of the word BOOK be arranged?
How many ways are there to choose five diamonds from a deck of cards?
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?
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?
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)?