In this post, I will discuss some

This blog gives is accompanied by Problem Set 5.1, which extends the ideas further. The problems there and here are probably most suitable for KS5 but could be accessed by some KS4 students. I would recommend going through this blog before attempting the problems there, but it's up to you.

Let's start with a classic problem:

You can make the job easier by listing the numbers 1 to 100 forwards and backwards like this:

**tactics**we can use for solving problems involving**counting**. This is a part of maths called**combinatorics**, which unfortunately is not studied explicitly in the school curriculum, but in places (e.g. listing outcomes of events, series, the binomial expansion, ...). Combinatorics is a fascinating subject that has applications in many other areas of maths, is a part of degree-level maths, and appears in many contest-style problems and 'recreational' maths problems.This blog gives is accompanied by Problem Set 5.1, which extends the ideas further. The problems there and here are probably most suitable for KS5 but could be accessed by some KS4 students. I would recommend going through this blog before attempting the problems there, but it's up to you.

Let's start with a classic problem:

**What is the sum the numbers from 1 to 100?**You will probably have seen this question before, and its solution, so it will be an exercise not a problem for most.You can make the job easier by listing the numbers 1 to 100 forwards and backwards like this:

Now we can see each 'column' sums to 101, and we have 100 of these pairs, so the total for both series is 101 x 100, and then dividing by 2 give the sum for one of the series (=5050).

This exercise is not that interesting in itself, but I am interested in the way it uses kind of

Of relevance to this post about counting, the sum of the counting numbers 1 to n is also the number of ways of choosing 2 items from n+1 items, written:

This exercise is not that interesting in itself, but I am interested in the way it uses kind of

**symmetry**to solve the problem, and in the fact that it is connected to other areas of maths.Of relevance to this post about counting, the sum of the counting numbers 1 to n is also the number of ways of choosing 2 items from n+1 items, written:

I will use the notation n

**C**r in this post (for ease of formatting). To see why the sum of numbers from 1 to n is the same as the number of ways of choosing 2 items from a list of n+1, let's look at an example - here is a list all the possible ways of choosing say 2 items from 4 (4**C**2):You can see there are 6 = 3 + 2 + 1 ways of doing this, and you can see from the way this is set out above that this will generalise to n

**C**r.Now let's use this bit of maths to answer a different looking problem:

Trying some numbers out gives the answers (a) 1 (b) 3 (c) 6, which leads us to conjecture that x + y + z = n has (n-1)

A nice way of explaining this is look at this diagram for (say) x + y + z = 5, which corresponds to the solution 1 + 2 + 2 = 5.

**C**2 solutions. But can you explain why these solutions are linked to ways of choosing 2 items? Try it for yourself before reading on...A nice way of explaining this is look at this diagram for (say) x + y + z = 5, which corresponds to the solution 1 + 2 + 2 = 5.

We can see that the partitioning of the number (in this case 5) corresponds to choosing 2 lines from the 4 central (red) lines, so the number of ways of partitioning 5 is 4

Can we

**C**2.Can we

**extend the problem**further and learn some more? Let's introduce another variable:Instead of listing all the possibilities, we can see immediately from our diagram that the answer is 9

**C**3. Using the formula for n**C**3 we have the solution: (9 x 8 x 7)/(3 x 2 x 1) = 84. We have learned a more efficient way of counting.Can we use this tactic in other problems? Let's try this geometric problem, which I found in the book Introduction to Counting and Probability by David Patrick:

Can you see where we might be able to put the tactics we have just discussed into practice? Try it for yourself...

How did you start? I went for the

How did you start? I went for the

**make it easier**strategy. Starting with a smaller polygon and looking for patterns...Again we see the power of the two tactics we have talked about already in this post -

**combinations**and**symmetry**.While we are looking at diagonals of polygons, consider this problem:

Hint: Each intersection is the crossing of two lines, so each intersection is created through the choice of 4 vertices (why?). This leads to the solution directly - can you see how?

If you like this problem, or just want to find out the answer, have a look at the counting chickens investigation.

If you like this problem, or just want to find out the answer, have a look at the counting chickens investigation.

Time for a set of connected problems, again geometric. Starting with a classic:

Did you find an efficient way of finding all the rectangles?

Here's a beautiful way of solving this problem. Consider the following diagram:

Here's a beautiful way of solving this problem. Consider the following diagram:

Each rectangle can be considered as the area enclosed by 4 lines, two horizontal and two vertical. So each rectangle is produced by choosing 2 horizontal and 2 vertical lines, giving the answer 8

**C**2 x 8**C**2. Again, we have used the ideas discussed earlier in this post.Now have a go at this tricky sounding problem.

No answer here, but a big hint: Use the strategy

**draw a picture**to see how this problem is strongly connected to the rectangle problem we have just solvedLet's look at some more problems that involve these tactics, this time from the world of numbers:

Try it for yourself before reading on...

Working systematically, we have the numbers 1 to 9 (so there are 9 increasing 1-digit numbers), then 12 to 19, then 23 to 29, and so on. You can see that the number of strictly increasing 2-digit numbers is 8 + 7 + ... + 2 + 1 = 9

Carrying this on systematically, we will have increasing 3-digit numbers 8

Working systematically, we have the numbers 1 to 9 (so there are 9 increasing 1-digit numbers), then 12 to 19, then 23 to 29, and so on. You can see that the number of strictly increasing 2-digit numbers is 8 + 7 + ... + 2 + 1 = 9

**C**2. Extending this to 3-digit numbers, starting with 1, we have 123 to 129, then 134 to 139 and so on giving 7 + 6 + ... = 8**C**2.Carrying this on systematically, we will have increasing 3-digit numbers 8

**C**2 + 7**C**2 + ... + 3**C**2 + 2**C**2. What is this sum? It turns out that summing n**C**2 numbers gives (n+1)**C**3, so this sum is 9**C**3. You should convince yourself that this valuable result is true, perhaps with some examples, or perhaps by looking at Pascal's triangle:So our final answer for this problem is 9

Let's reflect on this result. We discovered and used this important result (which generalises), which we will use again.

**C**1 + 9**C**2 + 9**C**3.Let's reflect on this result. We discovered and used this important result (which generalises), which we will use again.

But could we have done this a better way? Consider all the 3-digit numbers again. Considering numbers without zeroes and with distinct digits (why?), there are 9 x 8 x 7 possible 3-digit numbers. For each choice of 3 digits (there are 3! possible numbers for each choice of 3 digits), only one of them is strictly increasing, so we have 9 x 8 x 7 / 3! increasing 3-digit numbers as required. The result for 2-digits is similar and we could have arrived at the result sooner, but never mind. Maybe we can use this idea another time...

OK, here's another number-based problem. This one is a bit more tricky, but don't let me put you off...!

If you're anything like me, on reading this problem you are filled with a sense of feeling lost - where do I start? It's not like any problem we have seen before, apart from that it involves some counting, so combinations might appear somewhere.

OK. Deep breath. Let's think back to the last problem we solved above involving increasing numbers. In our reflection, we saw that we could have considered each combination of digits. Will this approach work here? Let's consider any 4 digits: How many ways are there of choosing 4 distinct digits? And how many of these are snakelike?

Well, there are 9

Let's now consider the numbers containing a zero. The choice of one of the numbers is fixed to be 0, so we have 9

Not too bad after all. We are learning all the time. And even if you didn't think of doing it this way, you might do next time!

**Making it easier**might work - what would the problem be like for 3-digits? Will this help us solve the 4-digit problem? I'm not sure it will, but try and see. It will give us a feeling of the sort of problem we are dealing with anyway... Try it for yourself before reading on.OK. Deep breath. Let's think back to the last problem we solved above involving increasing numbers. In our reflection, we saw that we could have considered each combination of digits. Will this approach work here? Let's consider any 4 digits: How many ways are there of choosing 4 distinct digits? And how many of these are snakelike?

Well, there are 9

**C**4 different ways of choosing 4 distinct digits from 1 to 9 (let's ignore zeroes for now as they give some integers <1000 so are a bit different). Given a set of 4 distinct digits, how many orderings are snakelike? WLOG, let's look at 1234. The snakelike integers are 1324, 1423, 2314, 2413 and 3412. So there are 5 snakelike integers for each set of 4 digits, giving a total of 9C4 x 5.Let's now consider the numbers containing a zero. The choice of one of the numbers is fixed to be 0, so we have 9

**C**3 ways of getting a number containing a 0. Let's suppose this number is 0123, then we have 3 snakelike integers: 1203, 1302 and 2301, so we have 9**C**3 x 3 snakelike integers containing a 0, plus 9C4 x 5 integers without a zero.Not too bad after all. We are learning all the time. And even if you didn't think of doing it this way, you might do next time!

Let's reflect on all this: we have used a limited number techniques -

Now try and use these techniques and strategies to solve these two interesting AMC10 problems (solutions to follow later), from the combinatorics problem set:

**combinations**and**symmetry**- to solve these problems, along with a few strategies:**make it easier,****draw a picture**and**work systematically.**Now try and use these techniques and strategies to solve these two interesting AMC10 problems (solutions to follow later), from the combinatorics problem set: