Permutation and Combination

Arrangements and selections

Practice →

Permutation and Combination are fundamental concepts in counting problems. Permutation deals with arrangements where order matters, while Combination deals with selections where order doesn't matter. These concepts are essential for solving problems involving arrangements, selections, and probability calculations.

Key Formulas

nPr = n! / (n-r)! (Permutation of n items taken r at a time)\text{nPr = n! / (n-r)! (Permutation of n items taken r at a time)}
nCr = n! / [r! x (n-r)!] (Combination of n items taken r at a time)\text{nCr = n! / [r! x (n-r)!] (Combination of n items taken r at a time)}
nCr = nC(n-r) (Symmetry property)\text{nCr = nC(n-r) (Symmetry property)}
nPr = nCr x r! (Relationship between permutation and combination)\text{nPr = nCr x r! (Relationship between permutation and combination)}
nC0 + nC1 + nC2 + ... + nCn = 2^n (Sum of all combinations)\text{nC0 + nC1 + nC2 + ... + nCn = 2\textasciicircum{}n (Sum of all combinations)}
Circular permutation of n distinct objects = (n-1)!\text{Circular permutation of n distinct objects = (n-1)!}
Circular permutation when clockwise and anticlockwise are same = (n-1)!/2\text{Circular permutation when clockwise and anticlockwise are same = (n-1)!/2}
Number of ways to arrange n items with p identical of one type, q of another = n! / (p! x q!)\text{Number of ways to arrange n items with p identical of one type, q of another = n! / (p! x q!)}
nCr = n-1Cr-1 + n-1Cr (Pascal’s Identity)\text{nCr = n-1Cr-1 + n-1Cr (Pascal's Identity)}

Key Concepts

Fundamental Principle of Counting

Multiplication Principle: If one operation can be performed in 'm' ways and another in 'n' ways independently, then both operations together can be performed in m x n ways. Addition Principle: If two operations are mutually exclusive (either one OR the other), the total ways = m + n ways. Always determine whether to multiply (AND) or add (OR) based on the problem structure.

Permutations - Order Matters

Use permutations when the arrangement or order of selection is important. For example: forming numbers, arranging people in a line, assigning distinct positions, creating codes with different arrangements. Key scenarios: linear arrangements (nPr), circular arrangements ((n-1)!), arrangements with repetition (n^r), and arrangements with identical items (accounting for duplicates by dividing by factorial of identical counts).

Combinations - Order Doesn't Matter

Use combinations when only the selection matters, not the order. For example: forming committees, selecting team members, choosing items from a menu, drawing cards from a deck. The formula nCr automatically accounts for the fact that different arrangements of the same items should be counted as one. Always verify whether the problem involves selection only (combination) or arrangement (permutation).

Special Cases and Constraints

Conditional arrangements: When certain items must or must not be together, use the gap method or treat restricted items as a single unit. At least/at most problems: Often easier to calculate using complement - subtract unwanted cases from total. Derangements: Ways to arrange n items so none appears in its original position. Distributing identical items into distinct groups: Use 'stars and bars' method.

Circular and Restricted Arrangements

Circular arrangements have (n-1)! ways because rotations of the same arrangement are considered identical. For arrangements where clockwise and anticlockwise are the same (like necklace beads), divide by 2: (n-1)!/2. When arranging with restrictions (certain people not sitting together), first arrange unrestricted items, then place restricted items in the gaps formed.

Grouping and Distribution Problems

Dividing n distinct items into groups of sizes a, b, c... where groups are identical in size: divide by the factorial of identical group counts to avoid overcounting. Distribution into distinct boxes: Multiply combinations for each box. When distributing identical items into distinct boxes with no restrictions: use (n+r-1)C(r-1) where n=items, r=boxes.

Solved Examples

Problem 1:

In how many ways can 5 people be seated around a circular table?

Solution:

Step 1: Identify this as a circular permutation problem.
Step 2: For circular arrangements, rotations are considered the same arrangement.
Step 3: Fix one person's position to break the rotational symmetry.
Step 4: Arrange the remaining 4 people in 4! = 24 ways.
Step 5: Alternatively, use formula (n-1)! = (5-1)! = 4! = 24.
Answer: 24 ways

Problem 2:

A committee of 4 members is to be formed from 8 men and 6 women. In how many ways can this be done if the committee must have at least 2 women?

Solution:

Step 1: Calculate total people = 8 + 6 = 14.
Step 2: 'At least 2 women' means 2 women, 3 women, or 4 women.
Step 3: Case 1 (2W, 2M): 6C2 x 8C2 = 15 x 28 = 420
Step 4: Case 2 (3W, 1M): 6C3 x 8C1 = 20 x 8 = 160
Step 5: Case 3 (4W, 0M): 6C4 x 8C0 = 15 x 1 = 15
Step 6: Total = 420 + 160 + 15 = 595
Answer: 595 ways

Problem 3:

How many 4-letter words can be formed from the letters of 'BANANA'?

Solution:

Step 1: Letters in BANANA: B(1), A(3), N(2) - total 6 letters.
Step 2: We need 4-letter words. Cases based on letter repetition:
Step 3: Case 1 - All 4 letters different: Choose from {B, A, N} = only 3 distinct, need 4 different - impossible (0 ways).
Step 4: Case 2 - One letter repeats twice: Choose which letter repeats (A or N), choose 2 more from remaining.
Step 5: For AA: select 2 from {B, N} in 2C2 = 1 way, arrange 4!/(2!) = 12 ways. Total = 1 x 12 = 12
Step 6: For NN: select 2 from {B, A} in 2C2 = 1 way, arrange 4!/(2!) = 12 ways. Total = 1 x 12 = 12
Step 7: Case 3 - One letter repeats thrice (AAA): Select 1 from {B, N} in 2C1 = 2 ways, arrange 4!/(3!) = 4 ways. Total = 2 x 4 = 8
Step 8: Total words = 12 + 12 + 8 = 32
Answer: 32 words

Problem 4:

In how many ways can 6 identical balls be distributed into 4 distinct boxes such that no box is empty?

Solution:

Step 1: This is distributing identical items into distinct boxes with constraint.
Step 2: Since no box can be empty, give 1 ball to each box first.
Step 3: Remaining balls = 6 - 4 = 2 balls to distribute freely.
Step 4: Use stars and bars: distribute 2 identical balls into 4 distinct boxes.
Step 5: Formula: (n+r-1)C(r-1) where n=balls, r=boxes.
Step 6: (2+4-1)C(4-1) = 5C3 = 10
Alternative: List partitions of 6 into 4 positive parts: (3,1,1,1), (2,2,1,1) and their permutations.
Step 7: For (3,1,1,1): 4 ways (choose which box gets 3).
Step 8: For (2,2,1,1): 4C2 = 6 ways (choose which 2 boxes get 2 each).
Step 9: Total = 4 + 6 = 10
Answer: 10 ways

Tips & Tricks

  • Always first determine if the problem is about permutation (order matters) or combination (order doesn't matter).
  • For circular arrangements, remember the formula is (n-1)!, not n!. When clockwise/anticlockwise are same, use (n-1)!/2.
  • Use the complement method for 'at least' or 'at most' problems - subtract unwanted cases from total cases.
  • When dealing with identical items, divide by the factorial of the count of each identical item type to account for indistinguishable arrangements.
  • Treat items that must stay together as a single unit, arrange the units, then arrange within the unit.
  • For 'not together' problems, first arrange the other items, then place the restricted items in the gaps formed.
  • Remember: nCr = nC(n-r). Use this to simplify calculations when r is large (e.g., 20C18 = 20C2 = 190).

Ready to practice?

Test your understanding with questions and get instant feedback.

Start Exercise →