High School Mathematics Extensions/Supplementary/Basic Counting

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

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)

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:

${\begin{array}{l}1,2,3,4,5,6,7,8,9,10\\7,3,10,4,9,5,1,8,2,6\\2,1,3,4,5,6,7,8,9,10\end{array}}$

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:

$10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1$

Almost 4 million different playlists!

Now we shall introduce the factorial function, which is a compact way of expressing:

$n!=n\times (n-1)\times ...\times 3\times 2\times 1$

Formally defined by:

${\begin{array}{l}0!=1\\n!=n\times (n-1)!\end{array}}$

So in our case:

${\begin{array}{l}10!=10\times 9!=10\times 9\times 8!...\\10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1\end{array}}$

What if we had 30 songs, but still wanted to shuffle just 10 of them? Similar reasoning leads to

$30\times 29\times 28\times 27\times 26\times 25\times 24\times 23\times 22\times 21$

different ways. This is equivalent to:

${\frac {30!}{20!}}={\frac {30!}{(30-10)!}}$

     Be cautious! The factorial function is not distributive over the addition or multiplication.

Generally speaking, the number of permutations of m items out of n (for instance, 10 songs out of 30) is:

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

The idea behind it is that we cancel out all but the first m factors of the n! product:

$30!=\underbrace {30\times 29\times ...\times 22\times 21} _{\text{First 10 factors}}\times \underbrace {20\times ...\times 2\times 1} _{(30-10)!=20!}$

When m equals n we say we are counting the number of permutations of n items:

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

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

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:

$\underbrace {3\times 3} _{\text{2 positions}}=3^{2}$

9 different numbers.

If we were to select m items out of n, with possible repetition, there would be

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

permutations.

1. How many three-digit numbers can be formed with only prime digits, and odd digits may only be repeated twice?

Circular permutation

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

$4!$

there will be some repetitions. We'll be counting each unique arrangement more than once since layouts like

${\begin{array}{l}{\text{A, B, C, D}}\\{\text{D, A, B, C}}\\{\text{C, D, A, B}}\\{\text{B, C, D, A}}\end{array}}$

are considered equivalent. Remember, there is no start in a round table.

     There is no coincidence in having 4 people chairs, and groups of 4 equivalent arrangements.

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):

${\frac {4!}{4}}=3!$

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:

$(4-1)!=3!=6$

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)

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:

${\begin{array}{l}{\text{Joe, Lee, Sue, Violet, Justin}}\\{\text{Lee, Joe, Sue, Justin, Violet}}\end{array}}$

As seen before, there are

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

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

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

ways of choosing 5 students to represent the 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 out of 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.

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

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 sampled is not enough for defining a selection, we need to know how many times each element is selected (i.e. the amount of samples selected of that element). Both approaches are, essentially, the same, as saying an element was selected 0 times is equivalent to saying it was not sampled.

Now suppose we were to select m elements out of n. Instead of thinking the problem as "choosing" from n elements m times, we should think it as "distributing" the m spots available over the n distinct elements (represented as placing m elements in n sets). Again, both interpretations are equivalent, as the number of times an element was chosen is represented by the number of elements in its corresponding set.

To define a selection, we place in every set as many objects as samples we selected from the element the set represented. We can create a string to identify the selection, for instance by representing each object (sample) with a square and set 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 three spots were assigned to the first element, two to the second element, and two to the third element. In other words, the selection consists of three elements of the first kind, two elements of the second kind, and 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, other than the two dashes that are fixed at the beginning and end of the string, the other n - 1 dashes and m squares can be moved without invalidating the string. There are thus 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 characters, in other words, the number of ways to choose m positions out of n - 1 + m:

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

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

${{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

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 out of n elements equals the number of ways of choosing n - m out of n elements since each group of selected elements has a corresponding group of elements that were not selected. 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 none or all of the elements.

${n \choose 0}={n \choose n-0}=1$

• There are n ways of choosing 1 or n - 1 elements.

${n \choose 1}={n \choose {n-1}}=n$

• The difference between

${n \choose m}$

and

${{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}}$

therefore

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

• The difference between

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

and

${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 form 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

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.

In

$(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^{2}b+{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}$

Exercises

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

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

3 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?

4 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?

5 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)?