When you start to do maths puzzles for fun (it's not as lame as it seems trust me), you will come across a style of question all to do with choices. These come in many shapes and forms, like How many ways are there of putting socks and shoes on a centipede? or How many ways are there of seating a group of 7 people around a 10-chair, round table?.
These come under the field of Mathematics known as Combinatorics. Wolfram Mathematica describes it as the field of maths that studies enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties.
Combinatorics problems are fun because they require out of the box thinking. It requires you to be able to look at unusual and unfamiliar problems, and see the spine of mathematical structure within them. The methods we use to solve them are all fairly intuitive, and many different methods can be used to solve the same problem. It helps, however, to have some basic tools in your mathematical box.
We will work with 5 puppies, a podium, and the question:
1. How many ways are there of ranking the puppies in order of cuteness?
Well, lets first consider number 1.
There are 5 ways of choosing number 1, out of the 5 puppies.
From there, there will only be 4 puppies left to be chosen for 2nd
From there, there will only be 3 puppies left to be chosen for 3rd.
Visualising this as a tree diagram with all the possible combinations branching from each way of choosing the first, then second, then third, you can see that the number of ways of choosing 1st 2nd and 3rd is 5x4x3x1
_5_ _4_ _3_ _2_ _1_
This is also known as 5!
Lets ask a different question:
2. How many ways are there of choosing and ranking the top 3 puppies ?
Where to start? We now only care about the top 3, so we can discard the 2x1 at the end. So, we have 5x4x3 options that we care about.
Lets try one more
3. How many ways are there of choosing the top 3 puppies?
How is this question different from the one above?
Well, this answer will be smaller: the podium of puppies A-E
1= A, 2=B, 3=C
is the same as
1=C, 2=A, 3=B.
So, looking again at the previous questions, I can see that each solution to question 3 will have a number of equivalent solutions in 2, which are just the same numbers but rearranged. In question one, we saw that the number of ways of re-arranging n objects is n!. So, each solution in q3 must have 3! corresponding solutions in q2.
Therefore, the number of solutions = (5x4x3)/(3x2x1)=(5x4x3x2x1)/(2x1)(3x2x1)=5!/(3!2!)=10
What you have just seen is what I would consider the building blocks of combinatorics:
n!= the number of ways of rearranging a set of n objects.
n!/(n-r)!= the number of ways of choosing r objects from n objects, when order matters.
n!/(n-r)!(r)! = the number of ways of choosing r objects from n objects when the order does not matter.
Of course you should be able know how to derive these yourself, once you have seen them once, it get easier to recognise when they are needed.
The key to combinatorics is to be careful about how you divide things into cases. If you look track of what you are counting, or double count, you will end up very confused very quickly. In any question, no matter the method you choose, stick to it and be vigilant.
I will come back with more fun questions, but I thought this might be a nice intro to get your brains working.
PS Good luck to everyone doing the BMO!