Counting: Permutations & Combinations

1. The Fundamental Principles

Combinatorics is the study of counting, grouping, and arrangement. In the context of competitive examinations like GATE, the focus is on visualizing the selection process rather than just applying formulas.

Rule of Sum (OR): If task A can be done in \(m\) ways and task B in \(n\) ways, and they are mutually exclusive, then A or B can be done in \(m + n\) ways.
Rule of Product (AND): If task A can be done in \(m\) ways and task B in \(n\) ways independently, then the sequence A followed by B can be done in \(m \times n\) ways.

2. Permutations (P): Order Matters

Permutations are used when the arrangement of items is significant, such as in seating arrangements or word formation.

Standard Linear Permutation

Arranging \(r\) items from a set of \(n\) distinct items:

P(n, r) = \frac{n!}{(n-r)!}

Permutations with Repetition

If you have \(n\) items where \(n_1\) are of type 1, \(n_2\) are of type 2, and so on:

\text{Total Arrangements} = \frac{n!}{n_1! \cdot n_2! \dots n_k!}

Circular Permutations

Arranging \(n\) distinct items around a circle:

Fixed orientation: \((n-1)!\)
No orientation (e.g., beads on a necklace): \(\frac{(n-1)!}{2}\)

3. Combinations (C): Order Irrelevant

Combinations are used when the goal is to select a subset without regard to the sequence of selection.

Basic Selection

C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Combinations with Repetition (Stars and Bars)

Selecting \(r\) items from \(n\) types where repetition is allowed (or distributing \(r\) identical items into \(n\) distinct bins):

\text{Ways} = \binom{n + r - 1}{r}

4. Advanced Concepts for GATE

Inclusion-Exclusion Principle

To find the size of the union of multiple sets:

$$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$$.

Derangements

The number of ways to arrange \(n\) items such that none are in their original position:

D_n = n! \left[ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n \frac{1}{n!} \right]

5. Summary Table

Scenario	Order Matters?	Repetition?	Formula
Permutation	Yes	No	\(P(n, r)\)
Combination	No	No	\(C(n, r)\)
Multiset Permutation	Yes	Yes (Identical)	\(\frac{n!}{n_1!n_2!...}\)
Multiset Selection	No	Yes	\(\binom{n+r-1}{r}\)

6. Tough Example Problems

Problem 1: The Constraints Challenge

How many 5-digit numbers can be formed using digits \(\{0, 1, 2, 3, 4, 5\}\) such that the number is divisible by 3 and repetition is not allowed?

Solution: The sum of digits must be a multiple of 3. We analyze two sets of 5 digits:

Set 1: \(\{1, 2, 3, 4, 5\}\) (Sum = 15). Arrangements: \(5! = 120\).
Set 2: \(\{0, 1, 2, 4, 5\}\) (Sum = 12). Arrangements: \(5! - 4!\) (excluding leading zero) = 96.

Total: \(120 + 96 = 216\).

Problem 2: Stars and Bars with Bounds

Find the number of integer solutions to \(x_1 + x_2 + x_3 = 15\), where \(x_1 \ge 1, x_2 \ge 2, x_3 \ge 0\).

Solution: Normalize variables to \(\ge 0\):

Let \(y_1 = x_1 - 1, y_2 = x_2 - 2, y_3 = x_3\).
Equation: \((y_1 + 1) + (y_2 + 2) + y_3 = 15 \implies y_1 + y_2 + y_3 = 12\).

\binom{3 + 12 - 1}{12} = \binom{14}{2} = 91