This section is going to be a pretty diverse one, but is going to give you a very powerful set of tools for solving diverse problems in the real world.

You will be able to calculate the probability of two people in a given sized room having the same birthday, you will be able to calculate the combinatorics of all sorts of permutations and combinations, and you’ll learn about how to approximate many functions by polynomial expressions – this is an incredibly powerful technique and is used throughout the sciences.

Combinatorics

Combinatorics is the study of the different ways to rearrange objects given certain constraints. A question might be:

If a teacher is randomly picking two different students out per class for a year to get them to explain an answer on the board , what is the likelihood that you will be picked exactly five times?

How about the number of times Jodhi is likely to be called in a given game of Thunee?

Combinatorics often deals with big numbers, because the number of ways of rearranging a given set of objects can grow far faster than exponentially with the number of objects (you’ll see in a bit about a really really really big number in the world of combinatorics, called Graham’s number).

We have a special notation which we often use in the world of combinatorics called the factorial. The factorial is denoted by an exclamation mark, and is sometimes called shriek (because that’s what you do when you see what the answer is). It is very simply defined for the natural numbers as:

 

n!=n(n-1)(n-2)....(2)(1)

 

Though for 0! it is defined to be 1. This may sound strange at first, but when we think of where factorial is used, it makes sense.

n! is the number of different ways that n objects can be arranged (ordered).

How many ways can we order n objects? Let’s start with just 2: objects a and b can be ordered as ab and ba. With 3 objects we have abc, acb, bac, bca, cab, cba, ie. 6 combinations. With 4 objects we can start to see a pattern. The first object a can go in four possible positions. Having chosen these positions there are then 3 possible positions for b, then there are two left for c and finally there will only be a single place for each of these that you can put d. So, there are 4\times 3\times2 \times1 possible ways of ordering 4 objects. This reasoning leads to the general statement that to order n objects there are:

 

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

 

ways. Which is how we defined n factorial. 4!=4\times3\times 2\times 1=24. How many ways are there of ordering 0 objects? Well there is one way, and it is to simply have no objects, so we define 0! to be 1. To ask how many ways are there of order 3.5 objects is clearly absurd and so 3.5! will be meaningless. We  can see also that n!=n\times (n-1)!. For r<n:

 

\frac{n!}{r!}=\frac{n(n-1)(n-2)(n-3)....(r+1)r!}{r!}=n(n-1)(n-2)(n-3)....(r+1)

 

so \frac{6!}{4!}=6\times 5=30. It is also true that as n tends to \infty:

 

n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n

 

This formula is known as Stirling’s approximation and can be very useful when dealing with factorials of large numbers.
Factorials get large very very quickly: 10!=3628800. This is how many ways there are of ordering ten objects, which doesn’t sound like a very big thing but you can see that there are over 3 million ways to do it.

 

1000!\sim 4.023872600770938*10^{2567}

 

Which is quite a big number, I think you’ll agree.

This gives us a perfect opportunity now to use our inductive skills and prove a formula. For every positive integer n:

 

\frac{d^n x^n}{dx^n}=n!

 

This says that if we take the derivative of x^n , n times the answer will be n!. There are three steps to an inductive proof.

1) Prove the base case. The base case states that:

 

\frac{dx}{dx}=1

 

which is clearly true.

2) Assume that the statement holds true for some n\ge 1:

 

\frac{d^n x^n}{dx^n}=n!

 

3) Use this statement to prove that it holds true for n+1. We are looking to find what:

 

\frac{d^{(n+1)} x^{(n+1)}}{dx^{(n+1)}}

 

is equal to. Well we can write this as:

 

\frac{d^n}{dx^n}\left(\frac{d x^{(n+1)}}{dx}\right)=\frac{d^n}{dx^n}\left({(n+1)}x^n\right)=(n+1)\frac{d^nx^n}{dx^n}

 

But we are assuming already that \frac{d^n x^n}{dx^n}=n! so we can substitute this in here:

 

\frac{d^{(n+1)} x^{(n+1)}}{dx^{(n+1)}}=(n+1)n!=(n+1)!

 

which is what we wanted to prove. Hence, by the Principle of Mathematical Induction, the statement is true for every positive integer n.

 

One-to-one functions and permutations

 

It seems that talking about the rearrangement of n objects has little to do with functions, but in fact it fits in as a specific case of a particular type of function. If we have a function f(x) with domain D(f) and range R(f), then the function is said to be one-to-one if for every value x in the domain, there is a single value f(x) in the range, and for every value f(x) in the range, there is a single value x in the domain. This statement is the same as saying that for x_1,x_2\in D(f), if x_1\ne x_2 then f(x_1)\ne f(x_2).

A permutation is a one-to-one function whose domain and range are the same. Let’s say we have a function on the domain [0,1] given by f(x)=1-x. It is clear that the range of this function is also [0,1] and that each value is mapped to a unique value in the range. This is a permutation of the real numbers in the region from 0 to 1.

 

We can talk about functions either on a continuous set of numbers like [0,1] or {\mathbb{R}}, or we can talk about them on discrete collections. The function f(x) on the domain \{0,1,2\} given by f(0)=1, f(1)=2, f(2)=0, is a one-to-one function where the domain and range are equal and thus this is a permutation. Permutations are generally easier to visualise on discrete sets of objects, or numbers, as we can really think of them as being rearrangements (or shufflings) of the original set. You get out what you put in to the function, just in a different order. We can write the above function as:

 

f=\left(\begin{array}{ccc} 0 & 1 & 2 \\ 1 & 2 & 0 \\\end{array}\right)

 

We’ve already stated above that the number of ways of rearranging n objects is n! and so we have that the number of different permutations on a set of size n is n!, precisely because the two questions are the same.

 

Bonus material: Really big numbers

While we’re on the subject of factorials, it might be fun to talk about how to describe really REALLY big numbers. It turns out that there is a handy notational convention called Knuth’s Up Arrow Notation which works as follows.

We’ll come up with a new notation for an exponent, and simply label it using an arrow pointing up:

 

4\uparrow 3=4^3=64

 

We can include multiple arrow and they work like this:

 

4\uparrow\uparrow3=4^{\left(4^4\right)}=4^{256}

 

where you see we have a tower of 4‘s 3 high. How about another arrow:

 

4\uparrow\uparrow\uparrow 3=4\uparrow\uparrow(4\uparrow\uparrow 4)

 

where here we have 3 brackets worth of double up arrows. This could be written as:

 

4\uparrow\uparrow\uparrow 3=4\uparrow\uparrow(4^{4^{4^4}})

 

This is a tower of 4‘s which itself is 4^{4^{4^4}}\sim 4^{10^{154}} high. We can’t even think about what that might be like.

In fact for what we are going to look at we will be interested in:

 

3\uparrow\uparrow\uparrow 3=3^{3^{.^{.^.3}}}

 

where the tower is 3^{3^3}=7625597484987 3s high. This is already huge but we are going to get far far larger in what’s to come, numbers which make this look small:

 

3\uparrow\uparrow\uparrow\uparrow 3=3\uparrow\uparrow\uparrow (3\uparrow\uparrow\uparrow 3)

 

How clear is this post?