Counting combinations

The number of ways to select r items from a set of size n where order matters is usually called:

n permute r

think of the puzzles involving tiles, and our explanation of what a factorial, n! is.

n permute r is given by the formula

  n!
------
(n-r)!

if we take a specific case of, say 5 permute 3 we get

   5!
 -----
 (5-3)!

which is

 5 x 4 x 3 x 2 x 1
-----------------
      2 x 1

as you can see the 2s and the 1s cancel so we end up with a kind of partial factorial of n:

5 x 4 x 3 = 60

It’s always good to remember that algebraic formulae involving letters can always be taken back to the numbers, to start with simple easy cases. then when you have worked through some of the specific number examples you truly understand the formula, which is of course true for any number.

We should also know the simplest case such as 4 permute 4

  4!
------
(4-4)!

which is just 4! divided by 0! = 24 / 1 = 24

strange that 0 factorial is defined as 1 , but it is… one way to look at it is because the empty set {} is still a set, and there is actually one way of arranging nothing.

There is another important situation to consider, and that is the question of how many different ways there are of taking r items from a set of size n, if the order in which the items are placed doesn’t matter.

consider the set {a,b,c,d}

if we want to select 2 items from this set, and their order matters then we have

ab
ba
ac
ca
ad
da
bc
cb
bd
db
cd
dc

there are 4 permute 2 , which is 4 x 3 = 12. but if order doesnt matter then you can hopefully see that

ab and ba
ac and ca
ad and da
…

are all equivalent. There are half as many results, 6. Why half ? well in fact there are always

  1
 ---
  r!

as many ways. For n = 5 and r = 3 there would be 3! groups of duplicate cases. We call this formula

n choose r

and it is given by

     n!
 ---------
 (n-r!)r!

which is just n permute r divided by r factorial. n permute r is thus always a bigger number than n choose r, which is apparent if you consider the process, specifying that the order matters will always give you a bigger set of results.

and another little tidbit for you, trying a few examples in the formula shows us that there is a symmetry in the numbers

what about 5 choose 3 ? it is

 5 x 4 x 3 x 2 x 1
--------------------
(2 x 1) x (3 x 2 x 1)

which is 10

but 5 choose 2 works out at

 5 x 4 x 3 x 2 x 1
------------------
(3 x 2 x 1) x (2 x 1)

which is the same number !

so

n choose (n-r) = n choose r (always).

Also notice that n choose n is always one, there’s only one way of taking the complete set…

Here’s code

def fac(a):
    if a==0:
        return 1
    else:
        return (a*fac(a-1))
 
def cho(x,y):
    return (fac(x)/(fac(x-y)*fac(y)))

If you are struggling then take it back to examples involving simpler cases or smaller numbers. This way you build up gently. There is no problem at our current level that cannot be split into smaller, easier problems if you are getting stuck. The mind works best holding bite sized chunks, and thus we need to work with its true nature and keep it simple at first. Then as you grow mathematically the complex stuff suddenly falls into place and “aha!”. Just like getting fit physically, start with walking and build up into running gently. Trying to run before you can walk means you might slip up. That’s also what a teacher has to know since if they show the pupil something too hard it will muddle them and they will lose confidence. None of that here, we have no time limits and can be thorough. Forget being back at school, this is the Cosmic University !