krit.club logo

Combinatorics - The Combination Formula-advanced

Grade 9CBSE

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

A combination is a selection of items from a larger set where the order of selection does not matter. This distinguishes it from a permutation, where order is essential.

•

The notation nCr^nC_r (or (nr)\binom{n}{r}) represents the number of ways to choose rr objects from a total of nn distinct objects.

•

Relationship with Permutations: The number of combinations is related to permutations by the factor of r!r!, expressed as nCr=nPrr!^nC_r = \frac{^nP_r}{r!}.

•

Complementary Combinations: Selecting rr objects is equivalent to 'not selecting' n−rn-r objects, leading to the identity nCr=nCn−r^nC_r = ^nC_{n-r}.

•

Pascal's Rule: An advanced identity stating that nCr+nCr−1=n+1Cr^nC_r + ^nC_{r-1} = ^{n+1}C_r. This is the basis for Pascal's Triangle.

•

Total Selections: The total number of ways to select any number of items (from 00 to nn) from nn distinct items is 2n2^n.

📐Formulae

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

nCr=n(n−1)(n−2)...(n−r+1)r!^nC_r = \frac{n(n-1)(n-2)...(n-r+1)}{r!}

nCr=nCn−r^nC_r = ^nC_{n-r}

nC0=nCn=1^nC_0 = ^nC_n = 1

nC1=n^nC_1 = n

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

💡Examples

Problem 1:

In a class of 1212 students, a group of 44 needs to be selected for a math competition. In how many ways can this selection be made?

Solution:

Here, n=12n = 12 and r=4r = 4. Using the formula nCr=n!r!(n−r)!^nC_r = \frac{n!}{r!(n-r)!}: 12C4=12!4!(12−4)!=12!4!×8!^{12}C_4 = \frac{12!}{4!(12-4)!} = \frac{12!}{4! \times 8!} 12C4=12×11×10×9×8!(4×3×2×1)×8!^{12}C_4 = \frac{12 \times 11 \times 10 \times 9 \times 8!}{ (4 \times 3 \times 2 \times 1) \times 8!} 12C4=12×11×10×924^{12}C_4 = \frac{12 \times 11 \times 10 \times 9}{24} 12C4=11×5×9=495^{12}C_4 = 11 \times 5 \times 9 = 495

Explanation:

Since the order in which the students are picked does not change the composition of the group, we use the combination formula.

Problem 2:

Find the value of nn if nC10=nC15^nC_{10} = ^nC_{15}.

Solution:

We use the property nCx=nCy  ⟹  x=y^nC_x = ^nC_y \implies x = y or x+y=nx + y = n. In this problem, 10≠1510 \neq 15, so we must have: n=10+15n = 10 + 15 n=25n = 25

Explanation:

The complementary combination rule states that choosing rr items is the same as leaving behind n−rn-r items.

Problem 3:

A polygon has 4444 diagonals. Find the number of sides of the polygon.

Solution:

Let the number of vertices (or sides) be nn. The number of lines that can be formed using nn vertices is nC2^nC_2. These lines consist of nn sides and the rest are diagonals. Number of diagonals = nC2−n=44^nC_2 - n = 44 n(n−1)2−n=44\frac{n(n-1)}{2} - n = 44 n2−n−2n2=44\frac{n^2 - n - 2n}{2} = 44 n2−3n=88n^2 - 3n = 88 n2−3n−88=0n^2 - 3n - 88 = 0 (n−11)(n+8)=0(n - 11)(n + 8) = 0 Since nn must be positive, n=11n = 11.

Explanation:

Every pair of vertices forms a line. Subtracting the adjacent pairs (sides) leaves the non-adjacent pairs (diagonals).

The Combination Formula-advanced Class 9 Notes & Examples