1.1 Basic Cases and Circular Permutations
In the last lecture we considered the basic concepts of permutations and combinations. Let’s consider a couple of examples further to ease the process of understanding these.
Ex -1
Find the number of permutations of the word ‘TRIANGLE’. How many of these permutations start with ‘T’ and end with ‘E’?
Solution:
We are dealing with a word of 8 different letters. So let’s visualise the process of counting the number of arrangements (permutations) of the letters of this word. Consider that we have to create a word out of the letters of the given word – ‘TRIANGLE’. The first letter can be chosen in 8 ways, AND the next letter can be chosen in 7 ways, AND the next to next letter can be chosen in 6 ways and so on.
Thus the total number of such permutations – \(8\times 7\times 6\times …3\times 2\times 1 = 8! = 40320\).
Consider that we now need to find the number of such permutations or words that start with ‘T’ and end with ‘E’. Let’s fix these 2 letters, so we have a word with blanks in the form of ‘T_ _ _ _ _ _ E’. These 6 blanks need to be filled by us with the remaining 6 letters, and hence there can be \(6!=720\) ways of creating words that start with ‘T’ and end with ‘E’.
Now, let’s consider the number of words among the \(40320\) possible combinations, that have the vowels always together. In this 8 lettered word, we have 3 vowels – ‘A’,’E’,’I’. So let’s consider this entire block {‘A’,’E’,’I’} as one letter for now. We thus have 5 +1=6 different letters to permute and we have seen that they can be permuted in \(6!=720\) ways. But for each of these permutations, this block can have \(3!=6\) different permutations. Thus the total number of such words = \(6!\times 3! = 4320\). Observe that this denotes the total number of words where the vowels are always together, thus the number of words where the vowels are never all together = \(40320-4320 = 36000\).
Ex -2
Consider the permutations of the word ‘TEETH’.
Ideally, before we go onto this, let’s consider the permutations of the word ‘EEE’. The number of permutations for this is exactly 1, since all the letters are identical. Now, for the word ‘EEA’, what can be the number of permutations?
It’s 3, either the ‘A’ will be at the end, middle or start.
So for ‘EEE’, it is \(\frac{3!}{3!} =1\).
For ‘EEA’, it is \(\frac{3!}{2!}=3\). Note that we first assume that all letters are distinct, thus the \(3!\) in the numerator, and then we make the adjustment for identical letters by dividing this number.
Thus, we can say the total number of ways to arrange the letters of the word ‘TEETH’ is \(\frac{5!}{2!\times 2!}\), since we have identical letters in sets of 2 each.
Consider the case where there are \(n\) persons seated across a circular table. How many such arrangements are possible?
Let’s make this a bit simpler and assume that there are 4 different persons seated in a circle. Let the initial ordering be {A,B,CD}. Now we make a circular shift to get the next seating arrangement/order.
{A,B,C,D} -> {D,A,B,C} -> {C,D,A,B} -> {B,C,D,A}.
We thus see that for each circular arrangement there can be an equivalent linear arrangement. Thus, let’s assume the number of circular permutations to be \(x\), and generalise the number of persons to be \(n\). We thus have \(nx=n! \Rightarrow x=(n-1)!\). Thus the number of permutations for \(n\) distinct elements in a circuclar fashion is \((n-1)!\).
1.2 Division into Groups
Let’s consider the fact that we have \(n\) identical things and we’d need to divide them into \(r\) groups.
Lets consider there are \(r-1\) blocks, so that, there will be \(r\) spaces to be filled (including the left of the left most block and right of the right most block). Now, \(n\) identical things should be filled in these spaces. There are \(n+r-1\) things in that line now, which can be arranged in \((n+r-1)!\) ways.
But, we should avoid the arrangements between the \(n\) things and \(r-1\) blocks, since they are identical. So finally we have \(\frac{(n+r-1)!}{n!(r-1)!}=\text{ }^{n+r-1}C_{r-1}\).
In case these \(n\) things are not identical, we’d need to account for their permutations as well, and hence in the above computation we shouldn’t be dividing the expression by \(n!\), thus the total number of ways in that case would be \(n!\times ^{n+r-1}C_{r-1}\).
Test Your Concepts:
1. Show that \(^nC_r=\text{ }^nC_{n-r}\)
2. How does the above expression for computing the number of ways to divide \(n\) identical elements into \(r\) groups change if blank groups are not admissible? (Hint : First we allot 1 element to each group and then repeat the above solution for the remaining elements.)
Let’s take a look at a different scenario now and correlate it with the above problem that we solved.
Consider the following equation, where \(x_i \in \mathbb{Z}^+\bigcup\{ 0\}\)
\(x_1+x_2+x_3+x_4=20\)
We need to find out the number of positive integral solutions to this equation. Let’s try to draw an analogy with the following case: ‘What are the number of ways to divide 20 identical elements into 4 groups?’ Note that each tuple \(\{x_1,x_2,x_3,x_4\}\) such that \(\sum\limits_{i=1}^{i=4}x_i=20\) denotes one such way to divide 20 identical elements into 4 groups. The first group contains \(x_1\) elements, the second \(x_2\) elements and so on. In this regard, we have a mapping between each such arrangement into groups with each solution tuple of the above equation.
Thus, the total number of integral solutions for \(\sum\limits_{i=1}^{i=r}x_i=n\) with \(x_i \in \mathbb{Z}^+\bigcup\{ 0\}\) is essentially the number of ways to divide \(n\) identical things into \(r\) groups. What happens if \(x_i>0\) for all \(i\)?