1.1 Introduction
Combinatorics, in a way, deals with the art of counting, and thus, a lot of problems in this regard will be dealing with counting the number of arrangements of a particular sequence. As trivial as it may sound, this branch of mathematics has been widely used in various fields like economics, physics and the like. In particular probability theory is one of those Areas where combinatorics has been widely used and still being used extensively in all the new developing areas of mathematics.
Broadly speaking, there are 2 defining principles which guide the mathematics of counting. These two principles are – the AND principle and the OR principle. Let’s consider an example for understanding please 2 principles. Let’s say we have 10 balls in a box all of different colours. In how many ways can we choose two balls from the box? There are 10 different balls, we will choose one after the other. Thus the first ball can be chosen in 10 different ways. Basically what this means is, we have 10 different options for choosing the first ball. Now assuming that we have Chosen One ball and and you are not putting it back in the box, we’re left with 9 different options to choose the second ball. So what we have is, 10 options to choose the first ball AND 9 different options to choose the second. And hence this gives us a total of of 90 different combinations of a set of of two different balls. This means that there can be 90 different choices to choose a set of two different balls.
Now consider that we need to fulfill a particular aim and we need to calculate the number of ways in which we can fulfill this aim. Consider the simple example where you have to choose a leader of a team. There are 10 boys and 2 girls in the team. In this case the leader can either be a boy or a girl. Here I am to choose a leader, and this is my aim. So we see that the leader can be a boy – in which case we can choose the leader in 10 different ways. OR what we see is that the leader can be a girl – in which case we can choose the leader in 2 different ways. Does the total number of ways in which we can choose a leader happens to be 10 + 2 = 12.
1.2 Permutations and Combinations
Each of these arrangements that we are discussing is called a permutation. In the first example, each pair of balls that we choose is a permutation. In the second case, each possible leader that we can choose is a permutation. Note that we’re delaing with the number of ways that we can choose – or the number of choices that we have at our end. In the end, we’re choosing only one couple of balls; we’re choosing only one leader of the team. But before making the choice, we’re interested to know how many different choices do we have.
Consider the first example of the number of balls. Let’s say we have balls on 8 different colours. So, there are at least 3 balls of the same colour. We assume that balls of the same colour are identical. As an aside, let’s consider a case where there are 10 balls of the same colour (and hence identical). In how many ways can we choose 2 balls? It’d ideally be \(10\times 9 = 90\), but let’s not forget that we’re talking of different choices over here. In case of identical balls, we won’t be able to distinguish whether the first and last ball was chosen, or the second and fifth ball was chosen, or the ninth and tenth balls were chosen. Since all the balls are identical, all these choices would appear to be identical as well. Thus the number of ways in which we can choose 2 balls from a set of identical balls is 1.
What if we were choosing \(k\) balls from a set of 10 identical balls? Since we’ll not be able to distinguish a set of \(k\) balls from another set of \(k\) balls, we can conclude that the number of ways of choosing a set of \(k\) balls is still 1. And hence generalising this, we can conclude that the number of ways we can choose \(k\) elements from a set of \(m\) identical elements is always 1.
Let’s go back to the old example that we were considering. We have 10 balls of 8 different colours. For simplicity, let’s assume that there are 3 balls of the same colour (Red), and 7 balls, each of different colours. Let’s look at the possibility where we want to explore the number of ways in which we can choose 2 balls of different colours.
To put things into perspective, we have an aim – choose 2 balls of different colours. We have the following 2 cases –
a) a Red ball is chosen (similar to the case where the leader in our second example is a girl)
OR
b) a Red ball is not chosen (similar to the case where the leader in our second example is a boy)
Thus, to compute the total number of choices that we have, let’s look at the number of choices for a)
We’ve already said that a Red ball can be chosen in any one way. From the 7 different balls, we can choose a ball in 7 different ways – thus the total number of ways = Total number of ways to choose a red ball AND total number of ways to choose a ball of different colour = \(1\times 7=7\).
For b) we look at a similar argument like we looked at the first case – we can choose 2 different balls from 7 different balls in \(7\times 6 = 42\) ways.
And hence we can say that the total number of such choices = \(42+7=49\).
Test Your Concepts:
Without delving into Combinatorics Arguments, could you figure out a serious flaw in the arguments above?
Now analyse this case with a smaller number of balls – 3.
Let’s say we have 3 different balls – A,B,C. We need to choose any 2 of them – the number of ways we can do that is as discussed above – \(3\times 2=6\). Can we jot down our choices? Let’s see;
(A,B), (B,C), (C,A)
We could come up with only 3 choices. However, we just saw that the first ball can be chosen in 3 ways and the second ball in 2 ways – thus the total number of ways has to be 6. This is where the concepts of Permutations and Combinations come up.
3 – is the number of choices that we have to select any 2 balls out of 3 iff the ordering in these choices is irrelevant. In other words (A,B) is the same as (B,A). These choices are called Combinations.
6 – same as above, but here the ordering does matter. So \((A,B) \ne (B,A)\). These choices are called Permutations.
For the example of choosing 2 balls of the same colour, we have considered ‘Permutations’ for b) and Combinations for a), and that’s the serious flaw in our computation. Thus if we consider the number of choices where ordering does matter (Permutations) the total number of ways = 7+7 (for a, note that we had implicitly assumed that the red ball would always come first and then the ball with the different colour) and 49 (for b) = 56.
Just for the sake of completeness – here are the formulae for Permutations and Combinations for choosing \(r\) distinct elements from a set of \(n\) distinct elements.
Permutations : \(^nP_r = \frac{n!}{(n-r)!}\)
Combinations : \(^nC_r=\frac{n!}{r!(n-r)!}=\frac{^nP_r}{r!}\)
We have already defined the factorial notation in our earlier articles – \(n!=n\times (n-1)\times (n-2)…3\times 2\times 1\).