Permutations and Circular Permutations

Hello everyone! In this post, we will explore permutations and circular permutations. I will be providing example problems with various solutions to approach them! I hope you all enjoy!

We will first start by learning the definition of a permutation.

Permutations:

Let S = {a1, …, an} be a set with n elements. If we arrange the elements of S in order, we get a permutation of S. More generally, if we select r elements from S and arrange them in order, we get an r permutation of S. We’ll use P (n, r) or nPr to denote the number of r- permutations of a set with n elements.

Theorem> P(n, r) = n(n-1)... (n-r+1) = n(n-1)...(n-r+1) [(n-r)(n-r-1)...2*1]/ [(n-r)(n-r-1)...2*1]= n!(n- r)!

        (We are choosing r elements out of n in order. First we have n elements to choose from, then we have n- 1 elements to choose from after choosing element, and after choosing another element, we would have n- 2 elements to select from. If we have to choose a total of r elements, we would end up with the left side of the equation by the multiplication principle.)

Example 1> How many ways can we arrange 5 couples in a row, if the people in each couple are together?

Answer: 5! 2^5 ( 5! Is the number of ways of arranging each of the couples and 2^5 accounts for arranging the people in each couple)

Example 2> Find the number of ways to arrange 6 adults and 4 children in a row if the children must be together.

Solution A> We can consider the 4 children as a single entity and consider each of the adults as a single entity. So in total, we have 7 entities. We would arrange the 7 entities in 7! Ways and within the entity of 4 children, we can arrange the 4 children in 4! ways. By the multiplication principle, the total number of ways would be 7! 4!

Solution B> First, consider the way of lining 6 adults first; this would be 6!. Afterwards, we would be able to place the 4 children in 7 spots (very left, very right, and in between each of the adults would be a total of 7 possible spots). Again, the 4 children can be lined up in 4! ways and by the multiplication principle, the total number of ways would be 6! 74!.

Circular Permutations.

In how many ways can we select r people from a set of n people and arrange them in a circle if all rotations of a given arrangement are considered the same? We can answer this question using the concept of circular permutations. We will denote this case by Q (n, r), the number of circular r- permutations of n objects.

Theorem> Q(n, r) = nPr ( Idea of proof:  P(n, r) = r Q(n, r) since each circular r- permutation corresponds to r regular permutations)

Special Case: Q( n, n)= (n - 1)!

Since Q(n, n) = P (n, n)* n= n!*n= ( n - 1)!

Example 1> Find the number of ways to arrange 6 adults and 4 children in a circle if the children must be together?

Answer: 6! * 4! (6!: number of ways to arrange 7 entities in a circle, 4!: ways of arranging the 4 children).

Example 2> Find the number of ways to arrange 7 people in a circle, if Carol and Tom cannot be together.

Answer: 6! - 5!*2 (6!: Total ways to arrange people, 5!*2: Number of cases in which Carol and Tom sit together)

Example 3> Find the number of ways to seat 5 men and 5 women in a circle, if the men and women alternate?

Solution 1> 4! (ways of seating men) * 5! (ways of seating the women in the gaps)

Solution 2> First seat a women, then there are 4! Ways to seat the other women. Then, the number of ways to seat the men in 5 fixed seats is 5!. Thus with the multiplication principle, the total number of ways to seat the people: 5! * 4!

Solution 3> 5! (pair men and women together) * 4! (arrange 5 entities into a circle).

This is all for today! Please feel free to contact me or comment below if you have any questions :)