A Penchant for Permutations

Refresher

Two weeks back, we started a new series on Counting Principles. In Down for the Count we looked the the basic multiplication and addition principles of counting. In Arranging and Choosing we introduced the ideas of permutations and combinations. In this post, we will consider circular permutations and permutations with restrictions.

Circular Permutations

When we introduced permutations, even though we did not mention it explicitly, the implicit understanding was that we were arranging the objects in a row. In fact, this is not necessarily the case. However, if we are able to call one position the ‘first’ position and another the ‘second’, etc., then what we have, in effect, is a row of positions since we can place the positions in a row according to their ‘number’.

Now, if we arrange the positions in a circle, what we lose is the ability to name a position as genuinely ‘first’. As the legendary round table of Arthur asserted, there is no ‘first’ in such a seating arrangement. Since there is no head, there is no primacy given to any particular position. We are only left with the relative positions and can say, “Person A is seated to the right of person B” or “Person B is seated to the left of person A.”

Now suppose there are 5 distinct objects that need to be permuted and placed in a circle. Two of the permutations are ABCDE and BCDEA. These are shown below

Since no position is a ‘starting’ positions or ‘first’ position, the two linear permutations above represent the same circular permutation, with A→B→C→D→E→A, being the progression if we went clockwise around the circle. We can easily see that the permutations CDEAB, DEABC, and EABCD represent the same circular permutation. Hence, there are 5 linear permutations that represent the same circular permutation. This simply represents having 5 options for the top position.

If we generalize this to n objects, we can see that we will have n linear permutations that represent the same circular permutation. Now, n objects can be permuted in n! ways, as we saw in the previous post. This means that n objects can be permuted in a circle in

We can extend this further to permuting r out of n objects. We know that r out of n objects can be permuted in ⁿP_r ways. However, for each set of r objects, there will be r linear permutations that represent the same circular permutation. This means that r out of n objects can be permuted in

Permutations of Non-Distinct Objects

Now suppose we do not have distinct objects. Rather, there are some objects that are identical. Let us consider a small set to get started. Now, instead of 5 distinct objects, let us consider 5 objects, 2 of which are identical. Hence, we could consider the set to be A, A, B, C, D. Note that the two ‘A’s are identical. Hence, it is impossible to distinguish between them. However, for the sake of this illustration, let us use subscripts to indicate patterns. So the two ‘A’s are A₁ and A₂.

Now, it is clear that the patterns A₁A₂BCD and A₂A₁BCD will be indistinguishable since both will appear as AABCD. In other words, there are 2 patterns that are indistinguishable from each other. In a similar way, BA₁CA₂D and BA₂CA₁D will appear as BACAD. What this means is that, no matter where we place the two ‘A’s, there will be two permutations that will be indistinguishable from each other.

What happens if there are 3 identical objects (e.g. AAABC)? Well, we can see that the patterns A₁A₂A₃BC, A₁A₃A₂BC, A₂A₁A₃BC, A₂A₃A₁BC, A₃A₁A₂BC, and A₃A₂A₁BC will all appear as AAABC. Hence, there are 6 permutations that will be indistinguishable.

We can see that, if there are p objects that are identical, then there will be p! permutations that will be indistinguishable, all of which represent permutations in which the identical objects occupy the same positions in the pattern. Hence, if there are n objects, p of which are identical, they can be permuted in

We can extend this to multiple kinds of identical objects. Suppose we have n objects with p₁ of one kind, p₂ of a second kind, etc. up to p_k of a k^th kind. Then the number of permutations will be

Let’s apply this. Let’s say I have 50 tiles, 4 of which are blue, 5 of which are red, and 10 of which are green, all others being distinct. Then then number of permutations will be

That’s 2.91… septendecillion permutations! I bet you learned a new word here!

Permutations with Restrictions

We can also consider a different kind of permutation in which we have some restrictions. For example, suppose we have 5 distinct objects (e.g. A, B, C, D, and E), which have to be arranged such that two of them, say A and B, have to be adjacent to each other. To find the number of permutations, we consider the group formed by A and B to be a distinct group, say X. Then, we have 4 distinct objects, C, D, E and X, which need to be permuted. This can obviously be done in 4! = 24 ways. However, the objects A and B can be permuted among themselves in 2! = 2 ways. For example, the permutation CXDE can be CABDE or CBADE. Hence, the total number of permutations is 4! × 2! = 24 × 2 = 48.

We can generalize this. Suppose we have n distinct objects, p of which need to be placed in a group and arranged among themselves. Hence, there are n – p distinct objects which have no restrictions. Then the number of distinct objects will be n – p + 1, including the group with p objects, which can be permuted in (n – p +1)! ways. However, the p objects can be permuted among themselves in p! ways. Hence, the total number of permutations will be (n – p + 1)! × p!.

Let’s consider an example. Suppose there is a group of 20 people, 5 of whom must be seated together. Then then number of permutations will be

Of course, we can extend this further. Suppose there are n distinct objects that need to be arranged such that a group of p₁ objects need to be together, another group of p₂ objects need to be together, and so on till a group of p_k objects need to be together. Note that each group will count as 1 object. Hence, the effective number of objects, including distinct objects and groups, which need to be permuted will be

Hence, the number of permutations, including the permutations within the groups, will be

Let’s try this out. Suppose there are 50 seats in a bus and 50 passengers. Among the passengers are a family of 5, a couple, and a group of 11 friends. If the groups have to sit together, the number of permutations will be

That’s 98.99… quindecillion permutations!

Looking Ahead

In this post we have looked art some different kinds of permutations, where the objects are arranged in a circle or where some of the objects are identical or where some distinct objects need to be kept together. Of course, there are cases where we may need to ensure some objects are not placed together, as in the case of rivals or bitter enemies. This is a much more complex situation than simply keeping a group together. So we will look into that in a post much later. However, in the next post, we will turn our attention to combinations and look at what are known as combinatorial arguments, which will help us to derive identities using the binomial coefficients solely through logical argumentation rather than through algebraic manipulation. Auf wiedersehen!