Here we’re going to continue looking at how many different ways there are to order collections of objects, but with certain constraints.

We saw previously that if you have n (distinguishable) objects, you can arrange them in n! ways (n positions for the first object (n-1) for the second, etc, with a single position for the last object).

Now we can ask what is the way of arranging r of n objects. That is, if I give you a deck of cards and ask you to take any five cards and put them in some order, how many possibilities are there in total?

Well, clearly the first card is going to be one of 52 different possibilities (in a 52 card deck). The second card is going to be one of 51 possibilities, etc. So the answer is going to be:

 

52\times 51\times 50\times 49\times 48

 

can we write this in terms of factorials? Let’s multiply and divide this number by 47!:

\frac{52\times 51\times 50\times 49\times 48\times 47!}{47!}

 

But the top is just 52!, so this is given by:

 

\frac{52!}{47!}

 

Where did the 47 come from? It’s just the total cards in the deck minus the number of cards we were choosing. So this is:

 

\frac{52!}{(52-5)!}

 

In general an expression of this form is known as a falling factorial and is denoted:

 

n_k=\frac{n!}{(n-k)!}

 

What if we had asked for all the ways to arrange not 5 cards, but 52 cards in the deck? Well, then both n and k would be 52, so we would have:

 

52_{52}=\frac{52!}{0!}=52!

 

In general n_n=n!.

How many different one-to-one functions are there from the set {a, b, c, d} to the set {1,2,3,4,5,6,7}?

Well let’s call our function f. For instance we might have f(a)=1, f(b)=2, f(c)=3, f(d)=4. How many possible functions of this form are there?

Well, we can see that we are essentially choosing 4 objects from the set of 7 to be the results of f(a), f(b), f(c), f(d). The order is important here, so it is exactly the same as saying how many ways can we draw four cards from a deck of 7. The answer is thus:

 

7_4=\frac{7!}{(7-4)!}=7\times 6\times 5\times 4=840

 

If I were to deal you four cards randomly from a deck of 52, what are the chances that you would get the same cards twice in a row, in the same order?

Well, the first answer is zero because I haven’t told you that I was going to put the first cards back in the deck, but presuming I have put them back, we can ask how many possible draws of four cards there could be. The answer of course is 52_4=6497400. So the chances of getting the same draw twice in a row (given that I am only doing this experiment once) is 1/6497400.

 

 

Bonus material: Graham’s number

So we’ve seen that there is an efficient notation for writing towers of exponents and we’ve defined a few pretty big numbers, but these are minuscule compared to what we’re about to get.

We saw that:

 

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

 

where the tower is 3\uparrow\uparrow 3 high. ie. 3^{27} high. This is a huge huge number!!…but we’re going further. What about:

 

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

 

Where now the tower of 3’s is 3\uparrow\uparrow\uparrow 3 high. We have gone way way beyond the realms of comprehension already. We will name this number G_1. Now let’s see how hyperbolically silly this can go. What if we defined:

 

G_2=3\uparrow\uparrow.....\uparrow\uparrow 3

 

Where the number of \uparrow‘s was G_1. Now we define G_3 in the same way by having G_2 \uparrow‘s…etc. you see where this is going.

OK, So Graham’s number is G_{64} It is an unimaginably, outrageously, ludicrously large number, but it is well defined, and, (only) in theory computable. There are larger numbers discussed in the mathematics literature but this (for some time) was known as the largest number which can in theory be computed and was in a mathematical proof.

Graham’s number is used in an area of mathematics called Ramsey theory which has connections to graph theory (the theory of connected nodes, their structure and their order). One famous result from Ramsey theory, which you can test yourself is that if you are at a party with at least six people, you will always find that there are at least 3 people, all of whom know one another, or you will find at least three people, none of whom know one another.

Graham’s number is the upper bound to a problem in Ramsey theory which is similar to the above. The answer is not known (ie. what is the minimum number of people at a party, for a particular condition to hold), but it is known to be greater than or equal to 13 and less than Graham’s number…you can see that this is a pretty weak bound!!

How clear is this post?