Permutation & Combination — with Factorial

Permutation and Combination form the foundation of counting principles in algebra and probability. These concepts determine the number of ways in which objects can be arranged or selected. The factorial function lies at the core of both ideas.

I. Factorial Concept

For any positive integer \( n \), the factorial of \( n \), written as \( n! \), is the product of all positive integers from 1 to \( n \):

\[ n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1 \]

\(0! = 1\) (by definition)
\(1! = 1\)
\(n! = n \times (n-1)!\)

Examples:

\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
\(\dfrac{7!}{5!} = 7 \times 6 = 42\)
\(\dfrac{8!}{6!2!} = \dfrac{8 \times 7}{2!} = 28\)

Factorials grow extremely fast; for large values, logarithmic approximations (like Stirling’s formula) are used, though rarely needed in GMAT/GRE-level problems.

II. Permutation (Arrangements)

A permutation is an arrangement of distinct objects in a specific order. Order matters in permutation.

1. General Formula

\[ {}^nP_r = \frac{n!}{(n – r)!} \]

This represents the number of ways to arrange \(r\) objects out of \(n\) total, when order matters.

Examples:

\( {}^5P_2 = \dfrac{5!}{(5-2)!} = \dfrac{120}{6} = 20.\)
Arranging 3 letters from A, B, C, D: \( {}^4P_3 = 24.\)

2. When All Objects Are Used

\[ {}^nP_n = n! \]

Example: The number of ways to arrange 5 people in 5 seats = \(5! = 120.\)

3. Circular Permutations

In a circle, one arrangement can be rotated in multiple ways but considered the same overall pattern.
For \(n\) objects arranged around a circle: \[ \text{Number of circular permutations} = (n-1)! \]
If clockwise and anticlockwise arrangements are identical: \[ \text{Distinct arrangements} = \frac{(n-1)!}{2} \]

Example: Arranging 6 people around a round table = \((6-1)! = 120\).

4. Permutations with Identical Objects

If there are \(n\) total objects where certain objects are identical, divide by factorials of identical counts:

\[ \text{Permutations} = \frac{n!}{p! \, q! \, r! \dots} \]

Example: For the word “BALLOON”: total 7 letters; identical letters — L(2), O(2). Number of distinct arrangements: \[ \frac{7!}{2! \, 2!} = 1260. \]

5. Restricted Arrangements

All vowels together, all consonants together.
Specific positions fixed (e.g., first and last digit fixed).
End-conditions (e.g., number must start with 5).

Example: How many ways can “APPLE” be arranged so that the two Ps are together?
Treat “PP” as one letter: effectively 4 letters (PP, A, L, E). \[ 4! = 24 \text{ arrangements.} \]

6. Special Cases

\( {}^nP_1 = n \)
\( {}^nP_2 = n(n-1) \)
Arranging all digits of a number where repetition not allowed = \(n!\)

III. Combination (Selections)

A combination is a selection of objects where order does not matter. It focuses on choosing groups rather than arranging them.

1. General Formula

\[ {}^nC_r = \frac{n!}{r!(n – r)!} \]

Relation between permutations and combinations: \[ {}^nP_r = {}^nC_r \times r! \]

Examples:

\( {}^5C_2 = \dfrac{5!}{2!3!} = 10.\)
Choosing a team of 3 from 6 candidates = \( {}^6C_3 = 20.\)

2. Properties of Combinations

\({}^nC_r = {}^nC_{n-r}\)
\({}^{n+1}C_r = {}^nC_r + {}^nC_{r-1}\) (Pascal’s Identity)
Sum of all combinations: \[ \sum_{r=0}^{n} {}^nC_r = 2^n \]

3. Selection with Restrictions

At least one element: \[ \text{Total} – {}^nC_0 = 2^n – 1 \]
At least one of each type: Apply complement rule by excluding cases violating condition.
Specific inclusions/exclusions: For example, “at least one woman” = Total selections – selections with zero women.

Example: A committee of 4 is to be formed from 6 men and 4 women such that at least one woman is included.
Total ways = \( {}^{10}C_4 – {}^6C_4 = 210 – 15 = 195.\)

4. Repetition Allowed (Combinations with Repetition)

When selection allows repeating elements (e.g., choosing coins, colors, or digits with repetition):

\[ \text{Number of combinations} = {}^{n + r – 1}C_r \]

Example: Choosing 3 fruits from 5 types with repetition = \( {}^{5+3-1}C_3 = {}^7C_3 = 35.\)

IV. Mixed & Real Exam Patterns

1. Word and Digit Problems

– Rearranging letters of a word (like PROBLEM, BALLOON, MISSISSIPPI).
– Forming numbers from digits with/without repetition.
– Code arrangements (PIN, license plate, passwords).

2. Conditional Arrangements

All vowels together → treat as one unit.
Specific letter fixed → position count reduces by one.
Consecutive or separated arrangements → compute complement cases.

3. Grouping & Distribution

Distributing objects among boxes.
Partitioning people into teams (distinguishable/indistinguishable).
Number of diagonals, handshakes, or pair connections: \[ \text{Number of pairs} = {}^nC_2 = \frac{n(n-1)}{2} \]

4. Example – Circular & Restricted

In how many distinct ways can 5 boys and 5 girls sit alternately around a round table?

\[ (5-1)! \times 5! = 24 \times 120 = 2880. \]

5. Example – Selection with Restriction

From 8 people, 5 are to be chosen such that two specific persons are never together.

\[ {}^8C_5 – {}^6C_4 = 56 – 15 = 41. \]

V. Key Differences

Aspect	Permutation	Combination
Definition	Arrangement of items where order matters	Selection of items where order does not matter
Formula	\( {}^nP_r = \frac{n!}{(n-r)!} \)	\( {}^nC_r = \frac{n!}{r!(n-r)!} \)
Order of Objects	Important	Not important
Example	Arranging 3 books on a shelf	Choosing 3 books to read

Source reference: Based on “GMAT Topics 19 – Permutation & Combination” compiled by Manoj K. Singh. Expanded with complete derivations, logical interpretations, and exam-style examples for conceptual mastery.

Permutation & Combination — Extended Concept

Permutations and Combinations quantify possible arrangements or selections under given conditions. Together they form the foundation of Counting Principles and Probability Theory. In GMAT/GRE applications, they test logic, constraints, and analytical reasoning more than computation.

I. Factorial – Recap & Advanced Notes

The factorial function \(n! = n \times (n-1) \times \dots \times 1\) defines the number of ways to arrange \(n\) unique items. It forms the building block of both permutations and combinations.

Recursive form: \(n! = n \times (n-1)!\)
Ratio property: \(\dfrac{n!}{(n-r)!} = n(n-1)\dots(n-r+1)\)
Zero factorial: \(0! = 1\) (by definition)
Approximation for large n (Stirling’s): \(n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\)

Factorials are used to count arrangements and simplify expressions in combinatorial equations.

II. Permutation — Arrangement with Order

A Permutation represents the number of ordered arrangements possible with a given set of items.

\[ {}^nP_r = \frac{n!}{(n-r)!} \]

1. Conceptual Meaning

Selecting and arranging \(r\) objects out of \(n\) objects — where sequence matters. E.g., arranging 3 students from 10 candidates in order of rank.

2. Special Cases

\( {}^nP_0 = 1\)
\( {}^nP_1 = n\)
\( {}^nP_n = n!\)

3. Word Formation Problems

All letters distinct → \(n!\)
Some letters identical → \(\dfrac{n!}{p!\,q!}\)
Specific conditions (e.g., vowels together, fixed positions) → use grouping & constraints.

Example: How many words can be formed from “SUCCESS”? Total letters = 7 (S×3, C×2). \[ \text{Arrangements} = \frac{7!}{3!2!} = 420. \]

4. Circular Permutations

Linear → \(n!\)
Circular (distinct clockwise rotations considered same): \((n-1)!\)
If clockwise = anticlockwise (necklace, garland): \(\dfrac{(n-1)!}{2}\)

5. Restricted and Conditional Permutations

Vowels together: treat vowels as one unit, arrange internally.
Not together: total – together.
Fixed positions: reduce available places, then arrange remaining.
Repeated digits: divide by identical arrangements.

Example:

Arrange the word “LEADER” such that vowels always occupy even positions.

Vowels: E, A, E (3 vowels) → even positions = 3.
Consonants: L, D, R (3 consonants) → remaining positions = 3.
Vowels arrangement \(= \dfrac{3!}{2!}\), Consonants \(=3!\). Total arrangements = \(\dfrac{3! \times 3!}{2!} = 18.\)

6. Permutation with Repetition

If repetition is allowed: \[ \text{Permutations} = n^r \]

Example: Number of 3-digit numbers formed from digits 1, 2, 3, 4 with repetition = \(4^3 = 64.\)

III. Combination — Selection without Order

A Combination is a selection of objects where the order of selection does not matter.

\[ {}^nC_r = \frac{n!}{r!(n-r)!} \]

1. Relationship with Permutation

\[ {}^nP_r = {}^nC_r \times r! \]

2. Properties

\({}^nC_0 = {}^nC_n = 1\)
\({}^nC_r = {}^nC_{n-r}\)
\(\displaystyle\sum_{r=0}^{n} {}^nC_r = 2^n\)
Pascal’s Identity: \({}^{n+1}C_r = {}^nC_r + {}^nC_{r-1}\)

3. Restricted Combinations

At least one: \(2^n – 1\)
Exactly k: \({}^nC_k\)
At least one woman / one item type: subtract cases with zero of that type.

Example:

From 8 men and 4 women, a committee of 5 must include at least 2 women:

\[ {}^4C_2 {}^8C_3 + {}^4C_3 {}^8C_2 + {}^4C_4 {}^8C_1 = 6\times56 + 4\times28 + 1\times8 = 504. \]

4. Combination with Repetition

When order doesn’t matter but repetition is allowed: \[ {}^{n+r-1}C_r \]

Example: Choosing 3 scoops of ice cream from 5 flavors (flavor repetition allowed): \[ {}^{5+3-1}C_3 = {}^7C_3 = 35. \]

IV. Mixed & Complex Applications

1. Number Formation

From digits 1–9, number of even 4-digit numbers without repetition:

\[ \text{Units (even)} = 4 \text{ choices},\ \text{Thousands} = 8,\ \text{Hundreds} = 7,\ \text{Tens} = 6. \Rightarrow 4\times8\times7\times6 = 1344. \]

2. Team Formation

10 players, choose 6 for a match, captain chosen among them:

\[ {}^{10}C_6 \times 6 = 210 \times 6 = 1260. \]

3. Handshake Formula

Number of handshakes among \(n\) people (each pair shakes hands once): \[ {}^nC_2 = \frac{n(n-1)}{2}. \]

Example: 20 people → \(20\times19/2 = 190\) handshakes.

4. Circular Distribution

Arranging \(n\) identical items among \(r\) distinct people in a circle often uses inclusion-exclusion or cyclic permutation logic: \[ (n-1)!/(2) \text{ for symmetric circles.} \]

5. Parallel Arrangement Example

If 3 boys and 3 girls must sit alternately in a row:

\[ \text{Ways} = 3! \times 3! \times 2 = 72 \] (The ×2 accounts for starting pattern: boy–girl–boy or girl–boy–girl.)

6. Repetition Digits Example

Using digits 1–5, how many 4-digit numbers can be formed where digits may repeat?

\[ 5^4 = 625. \]

V. Smart Techniques & GMAT Logic Patterns

Permutation faster by slots: Fill each position with available options.
Combination faster by complement: At least one = total − none.
Symmetry rule: \( {}^nC_r = {}^nC_{n-r}\) → choose smaller of r or n–r.
Restricted seating: Always subtract “together” cases from “total”.
Overcounting alert: When rotation or reflection possible (necklaces, round tables), divide by repetition factor.
Power-set connection: All subsets of a set with n elements = \(2^n\) (sum of all combinations).
Binary logic: Every element has 2 states (chosen / not chosen) ⇒ \(2^n\).

GMAT Tip:

Many GMAT problems are phrased as “in how many ways can …” but test logic, not formula. Always identify whether order matters first — that single decision chooses between permutation and combination.

VI. Summary Table

Concept	Formula	Key Feature
Factorial	\(n! = n(n-1)\dots1\)	Count of total arrangements
Permutation	\( {}^nP_r = \frac{n!}{(n-r)!} \)	Order matters
Combination	\( {}^nC_r = \frac{n!}{r!(n-r)!} \)	Order doesn’t matter
Permutation with repetition	\( n^r \)	Repetition allowed
Circular permutation	\((n-1)! \text{ or } (n-1)!/2\)	Rotational equivalence

Source reference: Based on “GMAT Topics 19 – Permutation & Combination” compiled by Manoj K. Singh. Extended with advanced reasoning, shortcuts, and GMAT/GRE-style examples for conceptual mastery.