Class 11 PCM . Mathematics . Mathematics . Permutations and Combinations

Chapter 6: Permutations And Combinations

Ch 6

Mathematics

Class 11 PCM

Lecture 1

Introduction And Fundamental Principle Of Counting

Reference video · Lecture 1Introduction And Fundamental Principle Of Counting

Fundamental Principle of Counting

Multiplication Principle

If successive events have m1,m2,…,mkm_1, m_2, \ldots, m_k choices respectively, the total number of outcomes is the product of these choice counts.

m1m2⋯mkm_1m_2\cdots m_k
Tree diagram of the six pant-and-shirt combinations.
Tree diagram of the six pant-and-shirt combinations.
Total outcomes for successive choices
N=m1m2⋯mkN=m_1m_2\cdots m_k

Use when every outcome is formed by making one choice at each successive stage.

Apply the multiplication principle

  1. Identify the successive choices or positions needed to form one outcome.
  2. Count the available choices at each stage, adjusting for restrictions such as no repetition.
  3. Multiply the stage counts.
    N=m1m2⋯mkN=m_1m_2\cdots m_k
  4. If the outcomes belong to separate possible cases, count each case and add the totals.
    N=N1+N2+⋯+NrN=N_1+N_2+\cdots+N_r
Worked example

How many four-letter words can be formed from ROSE without repetition?

  1. Find the number of four-letter words formed from the letters of ROSE without repeating a letter.
  2. Fill the first position using any of the four letters.
    44
  3. After each selection, one fewer letter is available for the next position.
    4, 3, 2, 14,\ 3,\ 2,\ 1
  4. Multiply the choices for the four positions.
    4×3×2×1=244\times3\times2\times1=24
Answer: There are 2424 words.
Practice

Four different flags are available. How many signals can be made using two flags, one above the other?

Hint: Choose the upper flag first; the lower flag must be different.
Key step: There are 44 choices for the upper position and 33 remaining choices for the lower position.
Solution: 4×3=124\times3=12 signals.
Practice

How many two-digit even numbers can be formed from 1,2,3,4,51,2,3,4,5 if digits may repeat?

Hint: Choose the units digit first, since it determines whether the number is even.
Key step: The units digit has 22 choices, and the tens digit has 55 choices.
Solution: 2×5=102\times5=10 numbers.
Practice

Five different flags are available. How many signals using at least two flags can be arranged vertically, without repeating flags?

Hint: Count signals of each allowed length separately, then add the counts.
Key step: For lengths two through five, the counts are 5×45\times4, 5×4×35\times4\times3, 5×4×3×25\times4\times3\times2, and 5×4×3×2×15\times4\times3\times2\times1.
Solution: 20+60+120+120=32020+60+120+120=320 signals.
⚠ Common mistake

Do not use the same number of choices at every stage when repetition is forbidden: each selection reduces the remaining choices. If repetition is allowed, the number of choices may stay the same.

Quick recap

  • The Fundamental Principle of Counting multiplies the choices at successive stages.
  • For kk stages with m1,m2,…,mkm_1,m_2,\ldots,m_k choices, the total is m1m2⋯mkm_1m_2\cdots m_k.
  • With no repetition, reduce the available choices after each selection.
  • When repetition is allowed, the choice count can remain the same at each position.
  • Count separate outcome cases individually and add their totals.
Lecture 2

Permutations

Reference video · Lecture 2Permutations

Permutations of Distinct Objects

Permutations without repetition

The number of permutations of nn distinct objects taken rr at a time, where 0<r≤n0<r\le n and no object is repeated, is n(n−1)(n−2)⋯(n−r+1)n(n-1)(n-2)\cdots(n-r+1).

n(n−1)(n−2)⋯(n−r+1)n(n-1)(n-2)\cdots(n-r+1)
Product formula for distinct permutations
n(n−1)(n−2)⋯(n−r+1)n(n-1)(n-2)\cdots(n-r+1)

Use when order matters and objects cannot be reused.

Count distinct arrangements

  1. Identify the number of objects and positions to fill.
    n objects,r positionsn\text{ objects},\quad r\text{ positions}
  2. Count the choices for each position, reducing the available objects after each choice.
    n, n−1, n−2, …n,\ n-1,\ n-2,\ \ldots
  3. Multiply the choices.
    n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1)
Worked example

In how many ways can a Chairman and a Vice-Chairman be chosen from 12 people if one person cannot hold both positions?

  1. Choose a Chairman from the 12 people.
    1212
  2. Choose a different person as Vice-Chairman.
    1111
  3. Multiply the choices for the two distinct positions.
    12×11=13212\times11=132
Answer: There are 132132 ways.

Factorial Notation

Factorial rules
n!=n(n−1)!,0!=1n!=n(n-1)!,\qquad 0!=1
Worked example

Evaluate n!r!(n−r)!\frac{n!}{r!(n-r)!} when n=5n=5 and r=2r=2.

  1. Substitute n=5n=5 and r=2r=2 into the expression.
    5!2!(5−2)!=5!2! 3!\frac{5!}{2!(5-2)!}=\frac{5!}{2!\,3!}
  2. Expand the numerator to expose the common factorial.
    5⋅4⋅3!2! 3!\frac{5\cdot4\cdot3!}{2!\,3!}
  3. Cancel 3!3! and simplify.
    5⋅42=10\frac{5\cdot4}{2}=10
Answer: The value is 1010.

The Factorial Formula for Permutations

Factorial formula for permutations

For 0≤r≤n0\le r\le n, the number of permutations of nn distinct objects taken rr at a time is n!(n−r)!\frac{n!}{(n-r)!}.

nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}
Permutations without repetition
nPr=n!(n−r)!,0≤r≤n{}^nP_r=\frac{n!}{(n-r)!},\qquad 0\le r\le n

Use this for arranging rr of nn distinct objects when repetition is not allowed.

Use the permutation formula

  1. Identify the total number of distinct objects and the number selected for arrangement.
    n, rn,\ r
  2. Substitute into the factorial formula.
    nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}
  3. Cancel factorials before multiplying.
    n!(n−r)!=n(n−1)⋯(n−r+1)\frac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)
Worked example

How many three-letter words can be formed from the letters of NUMBER if no letter is repeated?

  1. There are six distinct letters and three positions.
    6P3=6!(6−3)!=6!3!{}^6P_3=\frac{6!}{(6-3)!}=\frac{6!}{3!}
  2. Cancel 3!3! and multiply the remaining factors.
    6⋅5⋅4⋅3!3!=6⋅5⋅4=120\frac{6\cdot5\cdot4\cdot3!}{3!}=6\cdot5\cdot4=120
Answer: There are 120120 words.
⚠ Common mistake

Do not use combinations when roles or order matter: swapping Chairman and Vice-Chairman gives a different arrangement.

Permutations When Repetition Is Allowed

Permutations with repetition

The number of arrangements of nn objects taken rr at a time, when repetition is allowed, is nrn^r.

nrn^r
Permutations with repetition
nrn^r

Use when each position is filled independently and an object may be used more than once.

Count arrangements with repetition

  1. Count the available choices for one position.
    nn
  2. Use the same number of choices for every position.
    n×n×⋯×n⏟r factors\underbrace{n\times n\times\cdots\times n}_{r\text{ factors}}
  3. Write the product as a power.
    nrn^r
Worked example

How many three-letter strings can be formed from the six letters of NUMBER if letters may be repeated?

  1. Each of the three letter positions has six choices.
    6×6×66\times6\times6
  2. Multiply the independent choices.
    63=2166^3=216
Answer: There are 216216 strings.
No Repetition vs Repetition Allowed
PointNo repetitionRepetition allowed
Choices per positionDecrease after each choiceRemain nn for every position
FormulanPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}nrn^r
Three-letter strings from NUMBER6⋅5⋅4=1206\cdot5\cdot4=12063=2166^3=216
Practice

Evaluate 7!−5!7!-5!.

Hint: Evaluate each factorial, then subtract.
Key step: 7!=50407!=5040 and 5!=1205!=120.
Solution: 7!−5!=5040−120=49207!-5!=5040-120=4920.
Practice

If 18!+19!=x10!\frac{1}{8!}+\frac{1}{9!}=\frac{x}{10!}, find xx.

Hint: Multiply both sides by 10!10!.
Key step: x=10!8!+10!9!x=\frac{10!}{8!}+\frac{10!}{9!}.
Solution: x=10⋅9+10=100x=10\cdot9+10=100.
Practice

How many ways can two different positions be assigned to 12 people, with no person holding both positions?

Hint: Choose the first person, then a different person for the second position.
Key step: 12P2=12!10!{}^{12}P_2=\frac{12!}{10!}.
Solution: 12P2=12⋅11=132{}^{12}P_2=12\cdot11=132 ways.

Quick recap

  • A permutation is an ordered arrangement; changing the order gives a different arrangement.
  • Without repetition, successive choices decrease: n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1).
  • Factorial notation means n!=n(n−1)⋯1n!=n(n-1)\cdots1, with 0!=10!=1.
  • For distinct objects, nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!} for 0≤r≤n0\le r\le n.
  • In particular, nPn=n!{}^nP_n=n! and nP0=1{}^nP_0=1.
  • When repetition is allowed, the number of arrangements is nrn^r.
Lecture 3

Permulations When All The Objects Are Not Distinct Objects

Reference video · Lecture 3Permulations When All The Objects Are Not Distinct Objects

Arrangements of Identical Objects

Multiset permutation theorem

If NN objects include repeated groups of sizes p1,p2,…,pkp_1,p_2,\ldots,p_k, with all remaining objects distinct, divide N!N! by the factorial of each repeated-group size.

N!p1!p2!⋯pk!\frac{N!}{p_1!p_2!\cdots p_k!}
Arrangements with Repeated Objects
N!p1!p2!⋯pk!\frac{N!}{p_1!p_2!\cdots p_k!}

Use when arranging all objects, with identical objects indistinguishable.

Count Arrangements with Repeated Objects

  1. Count the total number of objects, including repetitions.
    NN
  2. Record the size of each identical group.
    p1,p2,…,pkp_1,p_2,\ldots,p_k
  3. Apply the multiset permutation formula and simplify.
    N!p1!p2!⋯pk!\frac{N!}{p_1!p_2!\cdots p_k!}
Worked example

How many different arrangements of the letters of ALLAHABAD are possible?

  1. ALLAHABAD has 9 letters: 4 As, 2 Ls, and 3 other distinct letters.
    9!4! 2!\frac{9!}{4!\,2!}
  2. Divide by the permutations within each repeated group.
    9!4! 2!=7560\frac{9!}{4!\,2!}=7560
Answer: There are 7,5607,560 arrangements.
Other Repeated-Object Examples
ObjectsRepeated countsNumber of arrangements
INSTITUTEII occurs 2 times; TT occurs 3 times9!2!3!=30,240\frac{9!}{2!3!}=30,240
4 red, 3 yellow, and 2 green discsCounts are 4, 3, and 29!4!3!2!=1,260\frac{9!}{4!3!2!}=1,260
⚠ Common mistake

Do not count identical objects as distinct in the final answer. Divide by p!p! for every group of pp identical objects.

Arrangements of Distinct Objects Taken Part at a Time

Definition

Permutation — A permutation is an arrangement in which the order of the selected objects matters.

Permutations of Distinct Objects

The number of ways to arrange rr objects chosen from nn distinct objects, without repetition, is nPr{}^nP_r.

n!(n−r)!\frac{n!}{(n-r)!}
Permutations Taken rr at a Time
nPr=n!(n−r)!=n(n−1)⋯(n−r+1){}^nP_r=\frac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)

Use when selecting and arranging rr distinct objects from nn, without repetition.

Count Ordered Selections

  1. Check that order matters and repetition is not allowed.
  2. Identify the number of available objects and positions.
    n,rn,r
  3. Evaluate the permutation formula.
    nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}
Worked example

How many four-digit numbers can be formed from digits 1 to 9 if no digit is repeated?

  1. A four-digit number uses four of the nine distinct digits, and order matters.
    9P4{}^9P_4
  2. Count the ordered selections without repetition.
    9P4=9!5!=9×8×7×6=3024{}^9P_4=\frac{9!}{5!}=9\times8\times7\times6=3024
Answer: There are 3,0243,024 numbers.

Restrictions on the First Digit

Definition

Leading-Zero Restriction — A numeral cannot begin with 00; arrangements with zero in the first position must be excluded.

Count Numerals When Zero Is Available

  1. Count all ordered selections of the required length.
    nPr{}^nP_r
  2. Count arrangements with zero fixed in the first position.
    n−1Pr−1{}^{n-1}P_{r-1}
  3. Subtract the invalid arrangements.
    nPr−n−1Pr−1{}^nP_r-{}^{n-1}P_{r-1}
Worked example

How many numbers between 100 and 1,000 can be formed from 0,1,2,3,4,50,1,2,3,4,5 without repetition?

  1. Numbers between 100 and 1,000 have three digits. Count all arrangements from the six available digits.
    6P3{}^6P_3
  2. Subtract arrangements starting with zero; the remaining two places use two of the other five digits.
    5P2{}^5P_2
  3. Subtract the invalid arrangements from the total.
    6P3−5P2=6×5×4−5×4=100{}^6P_3-{}^5P_2=6\times5\times4-5\times4=100
Answer: There are 100100 numbers.
⚠ Common mistake

Do not count a zero-leading arrangement as a valid multi-digit number; it represents a number with fewer digits.

Arrangements with Objects Together

Treating a Group as One Object

When specified objects must stay together, treat the group as one object, arrange the resulting objects, then multiply by the arrangements within the group.

Specified Objects Together
(n−k+1)! k!(n-k+1)!\,k!

For nn distinct objects, if kk must be together, treat the group as one object.

Count Arrangements with a Required Group

  1. Replace the required group with one block.
    n−k+1n-k+1
  2. Arrange the block and remaining objects.
    (n−k+1)!(n-k+1)!
  3. Multiply by the arrangements within the block.
    k!k!
Worked example

How many arrangements of DAUGHTER have (i) all vowels together and (ii) the vowels not all together?

  1. DAUGHTER has eight distinct letters, including three vowels. Treat the vowels as one block, leaving six objects to arrange.
    6!6!
  2. The three vowels can also be arranged within their block.
    3!3!
  3. Multiply the block arrangements by the internal arrangements.
    6!×3!=43206!\times3!=4320
  4. For arrangements where the vowels are not all together, subtract this count from all arrangements.
    8!−4320=360008!-4320=36000
Answer: (i) 4,3204,320; (ii) 36,00036,000.
Complement Counting

To count arrangements where a condition does not hold, subtract the arrangements satisfying that condition from the total. Here, RR is the required count, TT is the total, and EE is the excluded count.

R=T−ER=T-E
INDEPENDENCE: Arrangement Counts
ConditionCount
No restriction12!3!4!2!=1,663,200\frac{12!}{3!4!2!}=1,663,200
Begins with P11!3!4!2!=138,600\frac{11!}{3!4!2!}=138,600
All vowels together (four Es and one I)8!3!2!×5!4!=16,800\frac{8!}{3!2!}\times\frac{5!}{4!}=16,800
Vowels not all together1,663,200−16,800=1,646,4001,663,200-16,800=1,646,400
Begins with I and ends with P10!3!4!2!=12,600\frac{10!}{3!4!2!}=12,600

Equations Involving Permutations

Solve for an Unknown in a Permutation Equation

  1. Expand each permutation using the factorial formula.
    nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}
  2. Cancel only factors known to be nonzero under the stated restrictions.
  3. Solve the resulting equation and keep only values in the allowed range.
    n≥rn\ge r
Worked example

Find nn if nP5=42 nP3{}^nP_5=42\,{}^nP_3 and n>4n>4.

  1. Expand and cancel common nonzero factors, using n>4n>4.
    nP5=42 nP3  ⟹  (n−3)(n−4)=42{}^nP_5=42\,{}^nP_3\;\Longrightarrow\;(n-3)(n-4)=42
  2. Solve the quadratic and reject the negative value.
    n2−7n−30=0  ⟹  (n−10)(n+3)=0  ⟹  n=10n^2-7n-30=0\;\Longrightarrow\;(n-10)(n+3)=0\;\Longrightarrow\;n=10
Answer: n=10n=10.

Other Permutation Equations

  • Example: If nP4n−1P4=53\frac{{}^nP_4}{{}^{n-1}P_4}=\frac{5}{3} with n>4n>4, cancellation gives 3n=5(n−4)3n=5(n-4), so n=10n=10.
  • Check the range: For 5Pr=6 5Pr−1{}^5P_r=6\,{}^5P_{r-1}, the ratio is 6−r6-r. The equation would give r=0r=0, which is outside the valid range 1≤r≤51\le r\le5; therefore, there is no admissible solution.
Practice

How many arrangements can be made from the letters of BALLOON?

Hint: Identify the repeated letters before applying the multiset formula.
Key step: 7!2!2!\frac{7!}{2!2!}
Solution: The letters LL and OO each occur twice, so 7!2!2!=1,260\frac{7!}{2!2!}=1,260.
Practice

How many three-digit numbers can be formed from 0,1,2,3,4,5,60,1,2,3,4,5,6 without repeating a digit?

Hint: Count all three-place arrangements, then subtract those with zero first.
Key step: 7P3−6P2{}^7P_3-{}^6P_2
Solution: 7P3−6P2=210−30=180{}^7P_3-{}^6P_2=210-30=180 numbers.
Practice

Find rr if 8Pr=6 8Pr−1{}^8P_r=6\,{}^8P_{r-1}, where 1≤r≤81\le r\le8.

Hint: Use the ratio nPr/nPr−1=n−r+1{}^nP_r/{}^nP_{r-1}=n-r+1.
Key step: 8−r+1=68-r+1=6
Solution: 9−r=69-r=6, so r=3r=3.

Quick recap

  • For NN objects with repeated groups, the number of distinct arrangements is N!p1!p2!⋯pk!\frac{N!}{p_1!p_2!\cdots p_k!}.
  • For ordered selections of rr distinct objects from nn, use nPr=n!(n−r)!{}^nP_r=\frac{n!}{(n-r)!}.
  • When zero is available for a numeral, subtract arrangements with zero in the first position.
  • For a required group to stay together, treat it as one block and multiply by the arrangements inside the block.
  • Use total arrangements minus excluded arrangements to count the complement of a condition.
  • For permutation equations, expand, cancel only nonzero factors, then check the allowed range.
Lecture 4

Combinations

Reference video · Lecture 4Combinations

Meaning and Formula for Combinations

Definition

Combination — A combination is a selection of objects in which changing their order does not create a new selection.

  • Order: Choosing players XX and YY gives the same team as choosing YY and XX.
  • Notation: The number of ways to choose rr objects from nn distinct objects is nCr{}^{n}C_r, also written as (nr)\binom{n}{r}.
  • Examples: A handshake is a pair of people; a chord joining points is determined by a pair of points.
Three distinct pairs: XY, YZ, and ZX.
Three distinct pairs: XYXY, YZYZ, and ZXZX.
Examples of selections
SelectionNumber of combinations
Choose 2 from X,Y,ZX,Y,Z3C2=3{}^{3}C_2=3: XYXY, YZYZ, ZXZX
Handshakes among 12 people12C2{}^{12}C_2
Chords joining 7 points on a circle7C2{}^{7}C_2
Permutation–combination relationship

Each selection of rr objects can be arranged in r!r! orders. Thus, permutations count each combination r!r! times.

nPr=nCr r!{}^nP_r={}^nC_r\,r!
Number of combinations
nCr=n!r!(n−r)!{}^nC_r=\frac{n!}{r!(n-r)!}

Use to select rr objects from nn distinct objects when order is irrelevant; valid for 0≤r≤n0\le r\le n.

★ Remember
  • Boundary values: nC0=1{}^{n}C_0=1 and nCn=1{}^{n}C_n=1; there is one way to select nothing or everything.
  • Factorial: 0!=10!=1 and n!=n(n−1)!n!=n(n-1)!.
  • Symmetry: nCa=nCb{}^{n}C_a={}^{n}C_b when a=ba=b or a+b=na+b=n.

Find a combination count

  1. Identify the total number of distinct objects, nn, and the number selected, rr.
    0≤r≤n0\le r\le n
  2. Check that order does not matter, then use the combination formula.
    nCr=n!r!(n−r)!{}^nC_r=\frac{n!}{r!(n-r)!}
  3. Cancel factorials before multiplying.
    n!(n−r)!=n(n−1)⋯(n−r+1)\frac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)
Worked example

If nC9=nC8{}^{n}C_9={}^{n}C_8, find nC17{}^{n}C_{17}.

  1. Use the combination formula and cancel the common factorial.
    n!9!(n−9)!=n!8!(n−8)!\frac{n!}{9!(n-9)!}=\frac{n!}{8!(n-8)!}
  2. Compare the two combination counts by taking their ratio.
    nC9nC8=n−89=1\frac{{}^nC_9}{{}^nC_8}=\frac{n-8}{9}=1
  3. Solve for nn, then evaluate the requested coefficient.
    n−8=9  ⟹  n=17;17C17=1n-8=9\implies n=17;\qquad {}^{17}C_{17}=1
Answer: n=17n=17, so nC17=17C17=1{}^{n}C_{17}={}^{17}C_{17}=1.

Symmetry and Pascal’s Identity

Symmetry property

Selecting rr objects is equivalent to rejecting the remaining n−rn-r objects, so the counts are equal.

nCr=nCn−r{}^nC_r={}^nC_{n-r}
Pascal’s identity

The sum of two adjacent combination counts from row nn equals the corresponding count in row n+1n+1.

nCr+nCr−1=n+1Cr{}^nC_r+{}^nC_{r-1}={}^{n+1}C_r
Worked example

Evaluate 8C3+8C2{}^{8}C_3+{}^{8}C_2 using Pascal’s identity.

  1. Apply Pascal’s identity to combine the adjacent counts.
    8C3+8C2=9C3{}^8C_3+{}^8C_2={}^9C_3
  2. Evaluate the resulting combination.
    9C3=9!3!6!=84{}^9C_3=\frac{9!}{3!6!}=84
Answer: 8484.

Selection with Conditions

Counting strategy

  • Independent group choices: Multiply the counts, such as choosing a fixed number of men and women.
  • Disjoint cases: Add the counts for each possible composition of the selection.
  • Restrictions: Translate “at least” into all permitted cases, or subtract forbidden cases from the total.
Committee and team counts
SituationCalculationCount
Committee of 3 from 2 men and 3 women5C3{}^{5}C_31010
Committee with 1 man and 2 women2C1×3C2{}^{2}C_1\times{}^{3}C_266
5-member team from 7 boys, no girls7C5{}^{7}C_52121
5-member team from 4 girls and 7 boys, at least one of each7C14C4+7C24C3+7C34C2+7C44C1{}^{7}C_1{}^{4}C_4+{}^{7}C_2{}^{4}C_3+{}^{7}C_3{}^{4}C_2+{}^{7}C_4{}^{4}C_1441441
5-member team from 4 girls and 7 boys, at least 3 girls4C37C2+4C47C1{}^{4}C_3{}^{7}C_2+{}^{4}C_4{}^{7}C_19191
Worked example

A group has 4 girls and 7 boys. How many 5-member teams contain at least 3 girls?

  1. At least 3 girls allows either 3 girls and 2 boys or 4 girls and 1 boy.
    (3,2) or (4,1)(3,2)\text{ or }(4,1)
  2. Multiply choices within each group and add the disjoint cases.
    4C37C2+4C47C1=4⋅21+1⋅7=91{}^4C_3{}^7C_2+{}^4C_4{}^7C_1=4\cdot21+1\cdot7=91
Answer: 9191 teams.
Four-card selections from a 52-card deck
ConditionCalculationCount
Any 4 cards52C4{}^{52}C_4270725270725
All 4 from the same suit4×13C44\times{}^{13}C_428602860
One card from each suit(13C1)4({}^{13}C_1)^42856128561
All are face cards12C4{}^{12}C_4495495
2 red and 2 black26C2×26C2{}^{26}C_2\times{}^{26}C_2105625105625
All the same colour2×26C42\times{}^{26}C_42990029900

Choose First, Then Arrange

Definition

Selection followed by arrangement — When a task first selects objects and then orders them, multiply the number of selections by the number of arrangements of each selected set.

Worked example

How many 5-letter arrangements can be formed from INVOLUTE using 3 vowels and 2 consonants?

  1. In INVOLUTE there are 4 vowels and 4 consonants; choose 3 vowels and 2 consonants.
    4C3×4C2=4×6=24{}^4C_3\times{}^4C_2=4\times6=24
  2. Arrange the 5 chosen distinct letters in each selection.
    24×5!=24×120=288024\times5!=24\times120=2880
Answer: 28802880 arrangements.

Permutations and Repeated Objects

Counting principles and permutation formulas

  • Fundamental counting principle: If one event has mm choices and a following event has nn choices, the ordered pair of events has mnmn outcomes.
  • Factorial: n!=1⋅2⋅3⋯nn!=1\cdot2\cdot3\cdots n, with 0!=10!=1.
  • No repetition: Permuting rr of nn distinct objects uses nPr=n!(n−r)!{}^{n}P_r=\frac{n!}{(n-r)!}, where 0≤r≤n0\le r\le n.
  • Repetition allowed: Forming a sequence of length rr from nn choices, with repetition allowed, gives nrn^r arrangements.
  • Repeated objects: If nn objects include groups of identical objects of sizes p1,p2,…,pkp_1,p_2,\ldots,p_k, the distinct arrangements are n!p1!p2!⋯pk!\frac{n!}{p_1!p_2!\cdots p_k!}.
Worked example

How many distinct words can be made from AGAIN, and what is the 50th in dictionary order?

  1. AGAIN has 5 letters, with A repeated twice.
    5!2!=60\frac{5!}{2!}=60
  2. In dictionary order, 24 words start with A, followed by 12 starting with G and 12 starting with I.
    4!=24;4!2!=124!=24;\qquad \frac{4!}{2!}=12
  3. The first 48 words are exhausted; among words beginning with N, the 49th is NAAGI and the next is NAAIG.
    48+1=49;48+2=5048+1=49;\qquad 48+2=50
Answer: 6060 words; the 50th word is NAAIG.
Worked example

How many numbers greater than 10000001000000 can be formed using the digits 1,2,0,2,4,2,41,2,0,2,4,2,4 once each?

  1. Arrange all 7 digits, accounting for three 2s and two 4s.
    7!3!2!=420\frac{7!}{3!2!}=420
  2. Subtract arrangements that begin with 0; after fixing 0, arrange the remaining digits.
    6!3!2!=60\frac{6!}{3!2!}=60
  3. All remaining arrangements are valid 7-digit numbers greater than 10000001000000.
    420−60=360420-60=360
Answer: 360360 numbers.
Worked example

In how many ways can 5 girls and 3 boys sit in a row so that no two boys are together?

  1. Arrange the 5 girls first.
    5!5!
  2. There are 6 gaps around the girls; choose and arrange 3 boys in these gaps.
    6P3=6!3!{}^6P_3=\frac{6!}{3!}
  3. Multiply the independent arrangements.
    5!×6P3=120×120=144005!\times{}^6P_3=120\times120=14400
Answer: 1440014400 ways.
⚠ Common mistake

Do not distinguish ABAB from BABA in a combination. Multiply counts for independent group choices, but add counts for mutually exclusive cases; when arranging a selected group, account for the order separately.

Practice

How many ways can 4 points be selected from 9 distinct points?

Hint: Order does not matter; use the combination formula.
Key step: 9C4=9!4!5!{}^{9}C_4=\frac{9!}{4!5!}.
Solution: Use 9C4=9!4!5!=126{}^{9}C_4=\frac{9!}{4!5!}=126. Therefore, there are 126126 ways.
Practice

How many committees with 2 men and 2 women can be formed from 5 men and 6 women?

Hint: Choose independently from each group, then multiply.
Key step: 5C2×6C2{}^{5}C_2\times{}^{6}C_2.
Solution: 5C2×6C2=10×15=150{}^{5}C_2\times{}^{6}C_2=10\times15=150. There are 150150 committees.
Practice

Evaluate 10C6{}^{10}C_6 using the symmetry property.

Hint: Replace it with the coefficient having the smaller lower index.
Key step: 10C6=10C4{}^{10}C_6={}^{10}C_4.
Solution: 10C6=10C4=10!4!6!=210{}^{10}C_6={}^{10}C_4=\frac{10!}{4!6!}=210.

Quick recap

  • A combination selects objects without regard to their order.
  • nCr=n!r!(n−r)!{}^{n}C_r=\frac{n!}{r!(n-r)!} for 0≤r≤n0\le r\le n; nC0=nCn=1{}^{n}C_0={}^{n}C_n=1.
  • nCr=nCn−r{}^{n}C_r={}^{n}C_{n-r} and nCr+nCr−1=n+1Cr{}^{n}C_r+{}^{n}C_{r-1}={}^{n+1}C_r.
  • For independent choices multiply; for separate allowed cases add.
  • If each selection is then arranged, multiply by the arrangements of its selected objects.
  • Repeated identical objects reduce distinct arrangements by dividing by the factorials of their repetition counts.

Formula sheet

Total outcomes for successive choices
N=m1m2⋯mkN=m_1m_2\cdots m_k
Product formula for distinct permutations
n(n−1)(n−2)⋯(n−r+1)n(n-1)(n-2)\cdots(n-r+1)
Factorial rules
n!=n(n−1)!,0!=1n!=n(n-1)!,\qquad 0!=1
Permutations without repetition
nPr=n!(n−r)!,0≤r≤n{}^nP_r=\frac{n!}{(n-r)!},\qquad 0\le r\le n
Permutations with repetition
nrn^r
Arrangements with Repeated Objects
N!p1!p2!⋯pk!\frac{N!}{p_1!p_2!\cdots p_k!}
Permutations Taken rr at a Time
nPr=n!(n−r)!=n(n−1)⋯(n−r+1){}^nP_r=\frac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)
Specified Objects Together
(n−k+1)! k!(n-k+1)!\,k!
Number of combinations
nCr=n!r!(n−r)!{}^nC_r=\frac{n!}{r!(n-r)!}

Mathematics — ALL CHAPTERS

1

Sets

View

2

Relations And Functions

View

3

Trigonometric Functions

View

4

Complex Numbers And Quadratic Equations

View

5

Linear  Inequalities

View

6

Permutations And Combinations

View

7

Binomial Theorem

View

8

Sequences And Series

View

9

Straight Lines

View

10

Conic Sections

View

11

Introduction To Three Dimensional Geometry

View

12

Limits And Derivatives

View

13

Statistics    

View

14

Probability

View