Chapter 7 — Permutations And Combinations

Definition: The Fundamental Principle of Counting (also called the multiplication principle) states that if a task can be performed in a sequence of steps and the first step can be done in m ways, the second step (for each choice of the first) in n ways, then the total number of ways to perform the combined task is m × n. This extends to any number of steps: if there are k steps with m1, m2, ..., mk possible ways respectively, the total number of outcomes is m1 × m2 × ... × mk.

Why it works: Each choice of the first step pairs with every choice of the second step, creating m × n ordered pairs. For k steps you form k-tuples; counting all combinations leads to the product of the counts.

Related idea — Addition principle: If two tasks are mutually exclusive (you must choose either A or B), and A can occur in m ways and B in n ways, then total ways = m + n. This is used when choices are alternatives, not sequential sub-steps.

Connection with permutations and factorials: Arranging n distinct items in order is a sequence of n choices: n × (n-1) × (n-2) × ... × 1 = n! . The multiplication principle is the foundation for permutations P(n, r) = n × (n-1) × ... × (n-r+1), and it underlies combination formulas as well.

How to apply (step-by-step):

• Break the task into independent sequential steps.
• Count the number of ways for each step (m1, m2, ...).
• If steps are sequential and independent, multiply the counts.
• If choices are exclusive alternatives, add the counts.
• Watch for restrictions (no repetition, must be distinct, etc.) and adjust counts for each step accordingly.

Definition: For a non‑negative integer n, the factorial n! is the product of all positive integers from 1 to n:

n! = 1·2·3·…·n, with the convention 0! = 1.

Why 0! = 1? It is defined this way to make formulas (like combinations and the recurrence relation) consistent: n! = n·(n−1)!, so 1! = 1·0! gives 0! = 1. Also, there is exactly one way to arrange zero objects (the empty arrangement).

Basic properties (with short explanations):

• Recurrence: (n+1)! = (n+1)·n! (follows directly from the product definition).
• Factorial ratio: for r ≤ n, n!/(n−r)! = n·(n−1)·…·(n−r+1) (this gives the number of ordered arrangements of r distinct items chosen from n).
• Division by smaller factorial: r! divides n! whenever r ≤ n, because r! is a factor of n!.
• Permutation/Combination links: nPr = n!/(n−r)!, nCr = n!/(r!(n−r)!).
• Multinomial/permutations with repeats: If n objects include groups of identical items of sizes n1, n2, …, nk (sum = n), distinct arrangements = n!/(n1! n2! … nk!).
• Growth: n! grows very fast. Stirling's approximation (useful for large n) is n! ≈ sqrt(2πn) (n/e)^n.
• Trailing zeros: Number of trailing zeros in n! (base 10) = floor(n/5) + floor(n/25) + floor(n/125) + … (counts factors of 5).

Short proofs/intuition: The recurrence (n+1)! = (n+1)n! is immediate from the product form. The factorial ratio formula comes from cancelling (n−r)! from n!. Multinomial formula divides out permutations of identical items because swapping identical items gives the same arrangement.

Remarks: Factorial is defined for nonnegative integers. A continuous extension exists (Gamma function): n! = Γ(n+1) for integer n, but Gamma is beyond the Class 11 syllabus.

Definition: A permutation is an ordered arrangement of objects. When order matters, different orders of the same objects are considered different permutations.

Basic formula (distinct objects, no repetition): For n distinct objects taken r at a time (0 <= r <= n), the number of permutations is

P(n, r) = n! / (n - r)!

Here n! (read “n factorial”) = n × (n − 1) × (n − 2) × ... × 1. The formula comes from counting choices step by step: for the first position there are n choices, for the second (n − 1), and so on, for r positions giving n × (n − 1) × ... × (n − r + 1) which equals n!/(n − r)!.

Important special cases and related results:

• If r = n, P(n, n) = n! (all objects arranged).
• When repetition is allowed (each of the r places can be any of n elements independently), number of arrangements = n^r.
• Circular permutations of n distinct objects (arrangements up to rotation) = (n − 1)!.
• If some objects are identical (multiset), permutations = n! / (n1! n2! ... nk!), where n1, n2, ... are multiplicities.

Why order matters: Consider the 3 letters A, B, C. The arrangements ABC and BAC are different permutations because positions differ. Permutations count such ordered differences.

Usage note: Always check whether repetition is allowed and whether order matters (if not, use combinations). For Class 11 basics, focus first on distinct objects without repetition and the formula P(n, r) = n!/(n−r)!.

What it means: A permutation of n distinct objects is an arrangement (ordering) of all those n objects. When the order matters and every object is used exactly once, the number of different arrangements is called the number of permutations of n distinct objects.

Counting idea (multiplication principle): To form an ordered list of length n using all n distinct items, there are n choices for the first position. After choosing the first, there are (n−1) choices for the second, then (n−2) for the third, and so on until 1 choice for the last. By the multiplication principle the total number of arrangements is

n! = n × (n−1) × (n−2) × ... × 2 × 1.

Basic properties and remarks:

• 0! is defined as 1 (the empty arrangement).
• Recursive relation: n! = n × (n−1)!
• Extension: if you choose and arrange only r positions (r ≤ n) from n distinct objects, the number is P(n,r) = n! / (n−r)! (called r-permutations or permutations of n taken r at a time).
• Related: arrangements around a circle (circular permutations) use (n−1)! because rotating a linear arrangement gives the same circular order.

Why this matters: Permutations count ordered outcomes in many real-life tasks — scheduling, seating, PINs/passwords without repetition, ordering books on a shelf, arranging runners on a podium, etc. Understanding n! and P(n,r) is a foundation for probability and combinatorics.

Definition: A permutation of n distinct objects taken r at a time is an ordered arrangement of r objects chosen from n distinct objects. Here the order of selection matters.

Derivation (using multiplication principle): To form an ordered r‑tuple, we choose an object for the 1st position (n choices), then for the 2nd position (n−1 choices), and so on, until the r‑th position (n−r+1 choices). By the multiplication principle the total number is

n × (n−1) × (n−2) × ... × (n−r+1) = n(n−1)(n−2) ... (n−r+1).

Compact formula: this product equals n!/(n−r)!, so

P(n, r) = nPr = n! / (n−r)!, for 0 ≤ r ≤ n.

Notes and special cases:

• If r = n then nPr = n! (all objects arranged).
• If r = 0 by convention nP0 = 1 (one way to arrange nothing).
• Permutations differ from combinations because order matters. Relation: nCr = nPr / r!.
• If repetition is allowed (each of the r positions may be any of the n objects independently), the count is n^r (this is a different case).

How to use: Identify n (total distinct objects) and r (positions to fill). Check whether order matters and whether repetition is allowed. If order matters and no repetition, use nPr = n!/(n−r)!. If repetition is allowed, use n^r.

What it means
When we arrange n objects in a row but some objects are identical (indistinguishable), many of the n! arrangements counted by treating every object as distinct become identical. We must divide out the overcount produced by permutations of identical objects.

General result
If among n objects there are k types with n1 identical of type 1, n2 identical of type 2, …, nk identical of type k (so n1 + n2 + … + nk = n), then the number of distinct linear arrangements is

Number of permutations = n! / (n1! · n2! · … · nk!).

Why this formula?
Imagine first labeling every object so they are all distinct; that gives n! permutations. For each arrangement, swapping among the n1 identical items of type 1 produces n1! labeled permutations that look identical when labels are removed. The same holds for each identical-type group. Since these swaps are independent, every distinct unlabeled arrangement corresponds to n1!·n2!·…·nk! labeled permutations. Hence divide n! by that product.

Worked idea with positions
Choose positions for objects of type 1 in C(n,n1) ways, then positions for type 2 in C(n-n1,n2) ways, and so on. Multiplying these binomial choices gives n!/(n1!n2!...nk!), which is the same formula.

Notes and common variations
- If no objects repeat (all ni = 1), the formula reduces to n!.
- For circular arrangements one often uses (n-1)!/(n1!·n2!·…·nk!) to account for rotations (but be careful: if the arrangement has rotational symmetry, extra care is needed).
- If you need distinct r-length arrangements chosen from a multiset with limited copies of each type, counting requires casework or generating-function/coefficients methods (this is more advanced).

What are permutations with restrictions? Permutations with restrictions are arrangements of distinct objects (in a line or around a circle) when some conditions (restrictions) are imposed — e.g. certain objects must be together, must not be together, must occupy specified positions, or must alternate. We count arrangements using basic permutation rules plus special techniques: block method, complementary counting, inclusion–exclusion and conditional (stepwise) counting.

Main methods

• Block method (treat as one object): If k specific objects must be together, treat them as one block. Count permutations of the block plus remaining objects, then multiply by internal permutations of the k objects.
• Complementary counting: Count total permutations without restriction and subtract arrangements that violate the restriction (e.g. 'not together' = total − 'together').
• Inclusion–exclusion: When several (overlapping) forbidden adjacencies or restrictions exist, use inclusion–exclusion: add/subtract counts of arrangements where one or more forbidden conditions hold to avoid double counting.
• Conditional (stepwise) counting / multiplication principle: Place certain types of objects first (or in fixed positions), then count ways to place the rest, multiplying choices at each step.
• Circular permutations: For n distinct objects around a round table use (n−1)! as the base count; apply block method or complementary counting with that base.

Notes: Always decide whether order matters (linear vs circular) and whether rotations/reflections are considered identical (usually rotations identical, reflections distinct unless stated).

Circular permutations deal with arranging objects around a circle where rotations of an arrangement are considered identical. Unlike linear arrangements, a circular arrangement has no fixed starting point — rotating every object one seat clockwise gives the same arrangement.

Key idea: For n distinct objects placed around a circle, the number of different arrangements (up to rotation) is (n−1)!. This is because fixing one object as a reference removes rotational symmetry and the remaining (n−1) objects can be arranged in (n−1)! ways.

Common variants and notes:

• When selecting and arranging r distinct objects from n around a circle: first choose the r objects, then arrange them circularly. The count is C(n,r)·(r−1)! = n! / ((n−r)!·r).
• If reflections are also considered identical (e.g., indistinguishable clockwise and counterclockwise — like a reversible necklace), divide by 2: number = (n−1)!/2 for n>2. (Handle n=1,2 as special cases.)
• When some objects are identical with multiplicities m1, m2, …, mk (sum = n), and only rotations are considered identical, the number of distinct circular arrangements is (n−1)! / (m1! m2! … mk!).
• Special small cases: n=1 gives 1 arrangement; n=2 gives 1 arrangement (since the two can be rotated into each other).

Why (n−1)! intuitively: Fix one object at a position (this breaks rotational symmetry). Now arrange the remaining (n−1) objects in the remaining positions in any order — that gives (n−1)! distinct circular arrangements.

Definition: A combination is a selection of r objects from n distinct objects where the order of selection does not matter. It answers the question “How many different groups (subsets) of size r can be formed from n items?”

Basic idea and derivation: First count ordered selections (permutations) of r distinct items from n: nP r = n*(n-1)*...*(n-r+1) = n!/(n-r)!. Each unordered selection (combination) of size r corresponds to r! different orders, so divide permutations by r!. Thus

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

Conditions: 0 ≤ r ≤ n (by convention C(n,0)=1 and C(n,n)=1). If r > n then C(n,r)=0 in combinatorial use.

When to use combinations vs permutations: Use combinations when order does not matter (committees, drawing lottery numbers). Use permutations when order matters (arranging people in a line, password sequences).

Key properties (short):

• Symmetry: C(n, r) = C(n, n−r).
• Recurrence (Pascal relation): C(n, r) = C(n−1, r−1) + C(n−1, r).
• Relation with permutations: nP r = C(n, r) · r!.
• Special values: C(n, 0) = 1, C(n, 1) = n, C(n, 2) = n(n−1)/2.

Short worked reasoning example: Number of ways to choose 3 students from 5 to form a team: C(5,3)=5!/(3!2!)=10. Order does not matter, so {A,B,C} is same as {B,C,A}.

Definition. For a nonnegative integer n and integer k with 0 ≤ k ≤ n, the binomial coefficient C(n,k) (also written as \(\binom{n}{k}\)) is defined by C(n,k) = n! / (k!(n−k)!). It counts the number of ways to choose k objects from n without order.

Connection with binomial theorem. The coefficients appear in the expansion (1 + x)^n = Σ_{k=0}^n C(n,k) x^k. Many identities follow from comparing coefficients or evaluating this polynomial at special x values.

Fundamental properties (with short combinatorial ideas).

• Symmetry: C(n,k) = C(n,n−k). (Choosing k to include is same as choosing n−k to exclude.)
• Edge values: C(n,0) = C(n,n) = 1.
• Pascal's identity: C(n,k) = C(n−1,k) + C(n−1,k−1). (Split choices by whether a particular element is chosen.)
• Sum of row: Σ_{k=0}^n C(n,k) = 2^n. (Set x = 1 in the binomial theorem.)
• Alternating sum: Σ_{k=0}^n (−1)^k C(n,k) = 0 for n ≥ 1. (Set x = −1 in the binomial theorem.)
• Hockey-stick identity: Σ_{i=r}^n C(i,r) = C(n+1,r+1). (Combinatorial: count subsets with largest element specified.)
• Vandermonde's identity: For nonnegative m,n and integer r, Σ_{k} C(m,k) C(n,r−k) = C(m+n,r). (Choose r items from two groups of sizes m and n.)
• Multiplicative relation: k·C(n,k) = n·C(n−1,k−1). (Choose a k-subset and mark one of its elements vs. choose the marked element first.)

Other useful facts. C(n,k) are integers (obvious from the counting definition). For fixed n, C(n,k) is unimodal in k and reaches its maximum at k = floor(n/2) or ceil(n/2). For n large, central coefficients C(2n,n) grow approximately like 4^n / (sqrt(pi n)).

Short algebraic proofs (examples). Pascal: use factorial formula or expand (1+x)^n = (1+x)(1+x)^{n−1} and compare coefficients. Vandermonde: (1+x)^{m+n} = (1+x)^m(1+x)^n and compare coefficient of x^r.

Where they appear in probability and counting. Binomial coefficients give probabilities in binomial distributions: P(k successes in n independent trials) = C(n,k) p^k (1−p)^{n−k}. They also count shortest lattice paths in a grid: number of shortest paths from (0,0) to (m,n) with steps (1,0) and (0,1) is C(m+n,m).

Definitions
A combination is a selection of r objects from n distinct objects where order does not matter. A permutation is an arrangement of r objects chosen from n distinct objects where order does matter.

Basic formulas
If n and r are integers with 0 ≤ r ≤ n, then

• Number of combinations: C(n, r) = nCr = n! / (r! (n - r)!)
• Number of permutations (r-permutations): P(n, r) = nPr = n! / (n - r)!

Relation between permutations and combinations
To form a permutation of r items from n, you can first choose which r items (combination) and then arrange those r chosen items in all possible orders. For each choice of r items there are r! distinct orders. Therefore

P(n, r) = C(n, r) × r!.

Equivalently,

C(n, r) = P(n, r) / r!.

Why it works (intuitive explanation)
Each combination is an unordered subset of size r. If you fix one such subset, all possible orderings of its r elements produce r! different permutations. Since combinations partition the set of permutations into groups of size r!, multiplying the number of combinations by r! gives the number of permutations.

Edge and special cases

• If r = 0 then C(n, 0) = 1 and P(n, 0) = 1 (empty selection/arrangement).
• If r = n then C(n, n) = 1 and P(n, n) = n!.
• The ratio P(n, r) / C(n, r) is always r! (depends only on r, not on n).

When to use which
Use combinations when the order of selected objects is irrelevant (e.g., forming a committee). Use permutations when order matters (e.g., assigning seats or ranks).

What is complementary counting?

Complementary counting is a strategy that counts the number of outcomes we want by counting the complement (the outcomes we do not want) and subtracting from the total number of possible outcomes. It is based on the identity:

|S| = |A| + |A^c| or equivalently |A| = |S| − |A^c|

Here S is the universal set of all possible outcomes and A is the event of interest. This method is especially useful when the complement is easier to count.

Basic inclusion ideas (Inclusion–Exclusion principle)

When counting the size of a union of sets we must correct for overcounting. For two sets A and B:

|A ∪ B| = |A| + |B| − |A ∩ B|

Reason: elements in A ∩ B were counted twice in |A| + |B|, so we subtract them once.

For three sets A, B and C:

|A ∪ B ∪ C| = |A| + |B| + |C| − (|A ∩ B| + |B ∩ C| + |C ∩ A|) + |A ∩ B ∩ C|

Reason: pairwise intersections were subtracted too many times, so we add back the triple intersection. The pattern generalizes: for n sets, use alternating sums of intersections of 1, 2, 3, ... sets.

When to combine both ideas

Often a counting problem that asks for "at least one" or "not containing a property" can be solved by either direct inclusion–exclusion or simply by complementary counting: count total outcomes and subtract those with none of the desired properties. For problems with several properties, combine complementary counting with inclusion–exclusion to count the complement efficiently.

Step-by-step approach

1. Identify the universal set S and compute |S| (total number of outcomes).
2. Identify the event A you want (or its complement A^c). Decide whether it is easier to count A or A^c.
3. If counting unions of overlapping properties, use inclusion–exclusion to correct for overcounting.
4. Apply the formulas and simplify.

Common pitfall: forgetting to subtract intersections (overcount) or to add back higher-order intersections when using inclusion–exclusion.

What it means
Combinations with repetition count the number of ways to choose r items from n distinct types when repetitions are allowed and order does not matter. Equivalently, we count multisets of size r drawn from an n-element set.

Counting idea (Stars and Bars)
Represent the r chosen items as r identical stars. To separate them into n types place n−1 dividers (bars) between stars. Any arrangement of r stars and n−1 bars corresponds to a solution of x1 + x2 + ... + xn = r with xi ≥ 0, where xi is the number of chosen items of type i. The number of distinct arrangements (order of bars and stars matters only combinatorially) is the number of ways to choose positions for either the stars or the bars among r + n − 1 places, giving the formula below.

Derivation (short)
If we have r stars and n−1 bars, total symbols = r + n − 1. Choose r positions for stars (or n−1 for bars): number = C(r + n − 1, r) = C(r + n − 1, n − 1).

Common special cases

• If each type must be chosen at least once (xi ≥ 1) and r ≥ n, set yi = xi − 1 (yi ≥ 0) and sum yi = r − n, giving C((r − n) + n − 1, r − n) = C(r − 1, r − n) = C(r − 1, n − 1).
• If there is an upper bound (xi ≤ k) on each type, use inclusion–exclusion or generating functions; a uniform cap k leads to an inclusion–exclusion sum (see formulas below).
• A generating-function viewpoint: the coefficient of x^r in (1 + x + x^2 + ...)^n = (1/(1 − x))^n equals C(r + n − 1, r).

When to use
Use combinations with repetition when you choose a collection of items where: (1) order does not matter, (2) items of the same type are indistinguishable, and (3) you may choose the same type multiple times.

Quick intuition
Think of distributing r identical objects into n distinct boxes (boxes = types). Each distribution corresponds to one multiset and is counted by stars-and-bars.

Overview: Permutations and combinations count ways of arranging or selecting objects. Key decision: does order matter? If yes → permutations; if no → combinations. Use factorials, multiplication principle, complementary counting and inclusion–exclusion for constraints.

Common problem types and how to approach them

• Linear arrangements of distinct objects: Arrange n distinct objects in a row: n! ways. For r positions from n distinct objects: P(n,r)=n!/(n−r)!.
• Circular arrangements: Arrange n distinct persons around a round table (rotations considered same): (n−1)! ways. If reflections also identical (necklace): (n−1)!/2.
• Arrangements with identical objects: When objects repeat (e.g., letters of a word), number of distinct permutations = n!/(n1! n2! ... nk!), where ni are multiplicities.
• Selections (combinations): Choose r from n without order: C(n,r)=n!/(r!(n−r)!). Use when committees, teams, or unordered groups are formed.
• Combinations with repetition (multisets): Number of ways to choose r items from n types with repetition allowed = C(n+r−1,r) (stars and bars interpretation).
• Distributions: Distinct objects to distinct boxes: use P or C depending on whether box ordering or counts matter; identical objects to distinct boxes: stars and bars; identical objects to identical boxes: harder — reduce by cases.
• Arrangements with restrictions: (a) objects that must be together → treat block as single item and multiply by internal arrangements; (b) objects that must be separated → use complementary counting or place gaps; (c) at least/at most constraints → sum appropriate combinations or use complementary counting.
• Use of complementary counting: When counting direct arrangements is hard, count total minus forbidden arrangements.
• Inclusion–exclusion principle: For overlapping forbidden properties use |A ∪ B ∪ C| = Σ|Ai| − Σ|Ai∩Aj| + Σ|Ai∩Aj∩Ak| − ...
• Multinomial situations: When dividing n distinct objects into groups of sizes n1, n2, ..., nk: number = n!/(n1! n2! ... nk!).

Strategy checklist: (1) Identify whether order matters; (2) Check for identical items or repetition allowed; (3) Reduce constraints by blocks, gaps, complementary counting, or inclusion–exclusion; (4) Apply correct formula; (5) Consider symmetry (circular, reflections) to reduce count.