High School Mathematics Extensions/Supplementary/Basic Counting
Supplementary Chapters |
Content |
---|
Basic Counting |
Polynomial Division |
Partial Fractions |
Summation Sign |
Complex Numbers |
Differentiation |
Problems & Projects |
Problem Set |
Solutions |
Exercise Solutions |
Problem Set Solutions |
Ordered selection (Permutation)[edit]
Suppose there are 10 songs in your music collection and you want to shuffle play them all (i.e. the 10 songs would play in a random order). In how many different ways can the collection be played?
This type of problem is called ordered selection (permutation), as we are selecting the songs from the collection in a certain order. For instace, these selections are considered different:
These clearly define different orders or in effect, playlists.
Let's think this step by step. We can pick 10 different songs for the first position (or first song to be played), 9 for the second position (as there is 1 song already picked), 8 for the third (as 2 songs are fixed), and so on and so forth. The total number of ways can be calculated as follows:
Almost 4 million different playlists!
Now we shall introduce the factorial function, which is a compact way of expressing:
Formally defined by:
So in our case:
What if we had 30 songs, but still wanted to shuffle just 10 of them? Similar reasoning leads to
different ways. This is equivalent to:
Generally speaking, the number of permutations of m items out of n (for instance, 10 songs out of 30) is:
The idea behind it is that we cancel out all but the first m factors of the n! product:
When m equals n we say we are counting the number of permutations of n items:
While solving counting problems, we'll generally use the words items or elements (in this case, our songs) and sets (in this case, the collection or playlists).
1. In how many ways can I arrange my bookshelf (7 books) if I own a trilogy and the 3 books have to be always together, in the same order?
2. In how many ways can I arrange my family (6 members) in a line, with the only rule that my parents have to be in adjacent positions?
Permutation with repetition[edit]
How many different two-digit numbers can be formed with only odd prime digits (i.e. 3, 5, or 7)? Numbers 75, 37, 77, 33, are possible solutions.
This is a special case of permutations, the items may be selected more than once. Counting, we see there are 3 possibilities for every position, since digits may be repeated:
9 different numbers.
If we were to select m items out of n, with possible repetition, there would be
permutations.
1. How many three-digit numbers can be formed with only prime digits, and odd digits may only be repeated twice?
Circular permutation[edit]
In how many ways can we sit 4 people (Alice, Bob, Charles, and Donald) at a round table?
This is another special case of permutations, the 4 elements are arranged in a circular order, in which the start and end of an arrangement are undefined.
If we simply count
there will be some repetitions. We'll be counting each unique arrangement more than once since layouts like
are considered equivalent. Remember, there is no start in a round table.
If we arbitrarily numbered the chairs, we could obtain all equivalent arrangements by cycling our whole layout. How many times we would cycle? How many chairs/positions are there? 4.
Dividing our first intent by 4 (i.e. dividing in groups of 4 equivalent dispositions):
6 unique dispositions.
Another way of approaching the problem is to forcibly define an arbitrary starting point for the layout, in other words, to fix one element and permute the other 3 left:
ways to sit four people at a round table.
1. What if there are 7 people, but the table only has 5 chairs?
Unordered selection (Combination)[edit]
Out of the 15 people in the math class, 5 will be chosen to represent the class in a school wide mathematics competition. How many ways are there to choose the 5 students?
This type of problem is called an unordered selection (combination), as the order in which you select the students is not important. For example, these selections are considered equivalent:
As seen before, there are
ways to choose the 5 candidates in ordered selection, but there are 5! ordered selections for each different combination (i.e. the same 5 students). This means we are counting each combination 5! times. Consequently, there are
ways of choosing 5 students to represent the class.
In general, the number of ways to choose m items out of n items is:
We took the formula for permutations of m items out of n, and then divided by m! because each combination was counted as m! ordered selections (m! times).
This formula is denoted by:
Note that is often read as n choose m.
1. Try not to use a calculator and think of the problem with groups of 1 student.
2. Again, no calculator and this time there are 1 million students in the class and we want to form groups of 999,999 students.
Combination with repetition[edit]
In this particular case of combination problems, elements may be selected more than once. That is, groups can include many samples of the same element.
Knowing which elements are picked is not enough for defining a selection, we need to know how many times is an element selected (i.e. the amount of samples selected). Both approaches are, essentially, the same: saying an element was picked 0 times is equivalent to saying it was not picked at all.
Now suppose we were to select m elements out of n. Instead of thinking the problem as "choosing", we should think it as "placing" the m elements inside the n distinct sets. Again, both interpretations are equivalent.
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 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.
Binomial coefficient[edit]
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.
- There is only one way to choose no elements, or to (not) choose them all.
- There are n ways of choosing one element, or (not) choosing n - 1.
- The difference between
- and
- 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
- therefore
- The difference between
- and
- 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, 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
Binomial expansion[edit]
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:
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.
In
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?
Similarly we can work out all the coefficients of the other terms:
And more generally:
Or more compactly using the summation operator:
Exercises[edit]
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)?