Fundamental Principle of Counting

Multiplication Principle

If an event can occur in mm different ways, and following it, another event can occur in nn different ways, then the total number of occurrence of the events in the given order is m×nm \times n.

Addition Principle

If an event can occur in mm different ways and another event can occur in nn different ways (independent of the first), then either of the two events can occur in m+nm + n ways.

Factorial Notation

The notation n!n! represents the product of first nn natural numbers. n!=1×2×3×⋯×(n−1)×nn! = 1 \times 2 \times 3 \times \dots \times (n-1) \times n

  • 0!=10! = 1
  • 1!=11! = 1
  • n!=n×(n−1)!n! = n \times (n-1)!

Permutations

A permutation is an arrangement in a definite order of a number of objects taken some or all at a time.

Formula

The number of permutations of nn different objects taken rr at a time is: nPr=n!(n−r)!,0≤r≤n^nP_r = \frac{n!}{(n-r)!}, \quad 0 \le r \le n

Special Cases of Permutations

Permutations of all objects

Number of permutations of nn distinct objects: n!n!

Permutations when repetition is allowed

If repetition is allowed and objects are taken r at a time from n objects: nrn^r

Permutations of Objects with Repetition

If out of nn objects:

  • pp objects are identical of one kind
  • qq objects are identical of another kind

Then total permutations: n!p!q!\frac{n!}{p!q!}

Circular Permutations

Objects arranged in a circle

Number of circular permutations of nn distinct objects: (n−1)!(n-1)!

Necklace or garland (clockwise and anticlockwise same)

(n−1)!2\frac{(n-1)!}{2}

Combinations

A combination is a selection of items from a collection, such that the order of selection does not matter.

Formula

The number of combinations of nn different objects taken rr at a time is: nCr=n!r!(n−r)!,0≤r≤n^nC_r = \frac{n!}{r!(n-r)!}, \quad 0 \le r \le n

Important Properties

  1. nCr=nCn−r^nC_r = ^nC_{n-r}
  2. nCx=nCy  ⟹  x=y or x+y=n^nC_x = ^nC_y \implies x=y \text{ or } x+y=n
  3. nCr+nCr−1=n+1Cr^nC_r + ^nC_{r-1} = ^{n+1}C_r (Pascal's Identity)
  4. nC0=nCn=1^nC_0 = ^nC_n = 1

Relation Between Permutation and Combination

nPr=nCr⋅r!^nP_r = ^nC_r \cdot r!

Common Mistakes

  1. Confusing permutation and combination.
  2. Forgetting to divide by factorial in combinations.
  3. Using n!n! instead of (n−1)!(n-1)! in circular permutations.
  4. Ignoring identical objects.
  5. Writing nCr^nC_r instead of nPr^nP_r (and vice versa).

Permutations and Combinations

Example 1

Evaluate 7!5!\frac{7!}{5!}.

Solution: 7×6×5!5!=7×6=42\frac{7 \times 6 \times 5!}{5!} = 7 \times 6 = 42.

Example 2

If nC8=nC2^nC_8 = ^nC_2, find nC2^nC_2.

Solution: Given nC8=nC2  ⟹  n=8+2=10^nC_8 = ^nC_2 \implies n = 8+2 = 10. Now nC2=10C2=10×92=45^nC_2 = ^{10}C_2 = \frac{10 \times 9}{2} = 45.

Example 3

How many 3-digit numbers can be formed from the digits 1, 2, 3, 4, 5 assuming repetition of digits is allowed?

Solution: Each of the 3 places can be filled in 5 ways. Total = 5×5×5=1255 \times 5 \times 5 = 125.

Example 4

How many words can be formed from the letters of the word 'ROSE' if no letter is repeated?

Solution: Number of letters = 4. Required permutations 4P4=4!=24^4P_4 = 4! = 24.

Example 5

Find the number of arrangements of the letters of the word 'INDEPENDENCE'.

Solution: Total letters = 12. Repetitions: N (3 times), D (2 times), E (4 times). Arrangements = 12!3!2!4!=1663200\frac{12!}{3! 2! 4!} = 1663200.

Example 6

In how many ways can a team of 3 boys and 3 girls be selected from 5 boys and 4 girls?

Solution: Select 3 boys from 5: 5C3=10^5C_3 = 10. Select 3 girls from 4: 4C3=4^4C_3 = 4. Total ways = 10×4=4010 \times 4 = 40.

Example 7

Find rr if 5×4Pr=6×5Pr−15 \times ^4P_r = 6 \times ^5P_{r-1}.

Solution: 5×4!(4−r)!=6×5!(5−(r−1))!5 \times \frac{4!}{(4-r)!} = 6 \times \frac{5!}{(5-(r-1))!}. Solving gives r=3r = 3 or r=8r=8 (rejected as r≤4r \le 4). Ans: r=3r=3.

Example 8

In how many ways can 5 distinct books be arranged on a shelf?

Solution: 5P5=5!=120^5P_5 = 5! = 120.

Example 9

How many chords can be drawn through 21 points on a circle?

Solution: A chord connects 2 points. 21C2=21×202=210^{21}C_2 = \frac{21 \times 20}{2} = 210.

Example 10

Find the number of diagonals of a decagon (10-sided polygon).

Solution: Formula: 10C2−10^{10}C_2 - 10 (Subtract sides from total connections). 45−10=3545 - 10 = 35.

Example 11

A bag contains 5 black and 6 red balls. Determine the number of ways in which 2 black and 3 red balls can be selected.

Solution: 5C2×6C3=10×20=200^5C_2 \times ^6C_3 = 10 \times 20 = 200.

Example 12

In how many ways can 5 people sit around a round table?

Solution: Circular permutation: (n−1)!=(5−1)!=4!=24(n-1)! = (5-1)! = 4! = 24.

Example 13

How many numbers between 100 and 1000 can be formed with digits 0, 1, 2, 3, 4, 5 if no digit is repeated?

Solution: 3-digit numbers. Hundreds place cannot be 0 (5 options). Tens (5 options). Units (4 options). Total = 5×5×4=1005 \times 5 \times 4 = 100.

Example 14

Evaluate 15C8+15C9−16C9^{15}C_8 + ^{15}C_9 - ^{16}C_9.

Solution: Use Pascal's Identity: 15C8+15C9=16C9^{15}C_8 + ^{15}C_9 = ^{16}C_9. So, 16C9−16C9=0^{16}C_9 - ^{16}C_9 = 0.

Example 15

In how many ways can 4 letters be posted in 3 letter boxes?

Solution: Each letter has 3 options. Total ways = 3×3×3×3=34=813 \times 3 \times 3 \times 3 = 3^4 = 81.

Questions and Answers (Board Exam)

Q1. State the Fundamental Principle of Counting.

Answer: If an event can occur in mm different ways and another event can occur in nn different ways, then the total number of occurrences of the events in the given order is m×nm \times n.

Q2. What is the value of 0!0!?

Answer: 0!=10! = 1.

Q3. Define Permutation.

Answer: A permutation is an arrangement in a definite order of a number of objects taken some or all at a time.

Q4. Write the formula for combinations of nn distinct objects taken rr at a time.

Answer: nCr=n!r!(n−r)!^nC_r = \frac{n!}{r!(n-r)!}.

Q5. What is the relationship between nPr^nP_r and nCr^nC_r?

Answer: nPr=r!×nCr^nP_r = r! \times ^nC_r.