Permutation: Detailed Explanation

Table of Contents
1. Fundamental Principles of Counting
2. Factorial
3. Permutation
4. Properties and Important Results on Permutations
5. Division into Groups (Partitions and Multinomial Coefficients)
6. Circular Permutation
7. Examples with Stepwise Solutions
8. Notes on Notation and Common Mistakes
View more

This chapter explains permutations and related counting techniques clearly and step-by-step. It begins with the basic principles of counting, defines factorial and permutation, lists important results and formulae used repeatedly in problems, and then covers special topics such as division into groups and circular permutations. Worked examples illustrate the methods used in school examinations and competitive tests.

Fundamental Principles of Counting

Multiplication Principle

If a task can be completed by performing two successive operations so that the first operation can be done in m ways and for each choice of the first, the second can be done in n ways, then the combined task can be done in m × n ways. This principle extends to any finite sequence of operations: if there are m₁, m₂, ..., m_k ways for the 1st, 2nd, ..., k-th operations respectively, then the total number of ways is m₁ × m₂ × ... × m_k.

Addition Principle

If a task can be completed by doing one of two mutually exclusive operations, the first in m ways and the second in n ways, then the task can be done in m + n ways. This extends to any finite number of mutually exclusive choices.

Factorial

For any natural number n, the factorial of n, written n!, is defined by the product

n! = n × (n - 1) × (n - 2) × ... × 3 × 2 × 1.

By convention, 0! = 1 and therefore 1! = 1.

Permutation

Each different arrangement (ordering) of some or all of a collection of objects is called a permutation.

The number of ways of arranging n distinct objects in order, taking r at a time (where 0 ≤ r ≤ n), is denoted by P(n, r) or ⁿP_r. The formula is

P(n, r) = n × (n - 1) × ... × (n - r + 1) = n! / (n - r)!

Properties and Important Results on Permutations

1. Permutations with repetition allowed: The number of arrangements of r positions where each position may be filled independently by any of n distinct objects (repetition allowed) is n^r.
2. All at a time (no repetition): The number of permutations of n different things taken all at a time is P(n, n) = n!
3. Permutations with identical objects: If among n objects, p are identical of one kind, q identical of a second kind, r identical of a third kind, and the rest are all different, then the number of distinct permutations is n! / (p! q! r!).
4. General case with several alike: If among n objects there are groups of identical objects of sizes p₁, p₂, ..., p_k with p₁ + p₂ + ... + p_k = n, then the number of distinct permutations is n! / (p₁! p₂! ... p_k!).
5. Including or excluding a particular object (taken r at a time): The number of permutations of n different things taken r at a time in which a particular specified object must be included equals P(n - 1, r - 1). The number of permutations in which that particular object is excluded equals P(n - 1, r).
6. Specified objects always together (all at a time): If m specified objects must always occur together in the arrangement of all n objects, treat these m objects as a single block. The number of such permutations is m! × (n - m + 1)!
7. Specified objects never together (all at a time): The number of permutations of n different objects (all at a time) in which a specified set of m objects never come together is n! - m! × (n - m + 1)!

Division into Groups (Partitions and Multinomial Coefficients)

Two groups of sizes m and n

The number of ways in which (m + n) distinct objects can be divided into two groups containing m and n objects respectively is the binomial coefficient

(m + n)! / (m! n!)

Three groups of sizes m, n and p

The number of ways to divide (m + n + p) distinct objects into three groups of sizes m, n, p respectively is the multinomial coefficient

(m + n + p)! / (m! n! p!)

Equal groups of size n

If we divide 2n distinct objects into two groups each of size n, then

• If the two groups are distinguishable (labels matter), the number is (2n)! / (n!)².
• If the two groups are not distinguishable (labels do not matter), the number is (2n)! / [2! (n!)²].

Similarly, for mn distinct objects divided equally into m groups each of size n:

• If the groups are labelled (order or identity of groups matters), the number of divisions is (mn)! / (n!)^m.
• If the groups are unlabelled (no distinction among groups), divide further by m!, giving (mn)! / [(n!)^m m!].

Distributing n distinct objects into r distinct groups with none empty

The number of ways of assigning n distinct objects to r distinct groups so that no group is empty is given by inclusion-exclusion:

rⁿ - C(r,1)(r - 1)ⁿ + C(r,2)(r - 2)ⁿ - ... + (-1)^r-1 C(r, r - 1)1ⁿ

This counts functions from an n-set to an r-set that are surjective (every group receives at least one object).

Circular Permutation

In a circular permutation the arrangements are considered equivalent under rotation. We usually fix a reference position or treat rotations as identical to avoid counting identical rotations multiple times.

1. n distinct objects around a round table (rotations distinct): If rotations are considered different (for example, if chairs are numbered), the number is n!
2. n distinct objects around a round table (rotations not distinct): If only relative order matters (rotations considered identical), the number is (n - 1)!
3. Rotations and reflections identical: If both rotations and mirror images are considered the same (i.e., clockwise and anti-clockwise orders are not distinguished), the number is (n - 1)! / 2 for n > 2.
4. r people chosen from n and arranged on a circle: The number of circular arrangements (rotations distinct) is P(n, r) / r. If clockwise and anticlockwise are considered the same, divide further by 2 to get P(n, r) / (2r).

Examples with Stepwise Solutions

Example 1

Find the number of different 4-letter arrangements (words) that can be formed from the letters A, B, C, D, E if repetition is not allowed.

Sol.

There are 5 distinct letters and we need ordered arrangements of 4 letters.

Use the formula for permutations without repetition: P(5, 4) = 5! / (5 - 4)!.

Compute P(5, 4) = 5 × 4 × 3 × 2 = 120.

Therefore, 120 different 4-letter arrangements are possible.

Example 2

How many distinct words (arrangements) can be formed using all letters of the word BALLOON?

Sol.

Count letters: B, A, L, L, O, O, N → total n = 7 letters.

Identical letters: two L's and two O's. All other letters are distinct.

Number of distinct permutations = 7! / (2! × 2!).

Compute numerator and denominator to find the value (arithmetic simplification optional here).

Example 3

In how many ways can 5 persons be seated around a round table?

Sol.

For seating around a round table where rotations are considered identical, use (n - 1)! for n distinct persons.

Here n = 5, so number of distinct seatings = (5 - 1)! = 4! = 24.

Example 4

From 8 students, a committee of 3 is to be chosen and a president is to be appointed from the committee. How many ways are possible?

Sol.

First choose the 3 committee members in C(8, 3) ways.

For each chosen committee, choose a president from the 3 members in 3 ways.

Total number = C(8, 3) × 3.

Compute value if required: C(8, 3) = 56, so total = 56 × 3 = 168.

Notes on Notation and Common Mistakes

• P(n, r) denotes permutations: order matters. C(n, r) denotes combinations: order does not matter.
• Remember that factorial grows rapidly; simplify algebraically using factorial cancellations where possible (for example, n! / (n - r)! instead of expanding both factorials fully).
• When objects are identical, divide by factorials for each type of identical objects to avoid overcounting.
• For circular arrangements, always check whether rotations (and reflections) are considered identical before applying a formula.

Summary

The basic counting principles-addition and multiplication-combined with factorials and permutation formulae allow you to count ordered arrangements efficiently. Special cases to remember are permutations with repetition, permutations with identical objects, block arrangements (objects together or apart), division into labelled or unlabelled groups, and circular permutations. Practice problems that mix these ideas will build fluency.