krit.club logo

Combinatorics - Combinations: When Order Does NOT Matter-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 pool where the order of selection does not matter. This distinguishes it from permutations, where order is critical.

•

The notation for combinations is nCr^nC_r or (nr)\binom{n}{r}, which represents selecting rr items from nn distinct objects.

•

Relationship with Permutations: A combination can be thought of as a permutation where the internal arrangement of the selected items is ignored. Thus, nPr=nCr×r!^nP_r = ^nC_r \times r!.

•

Complementary Combinations: Selecting rr items from nn is equivalent to leaving behind n−rn-r items. Therefore, nCr=nCn−r^nC_r = ^nC_{n-r}.

•

Restricted Combinations: If kk particular items must always be included in the selection of rr items from nn, the number of ways is n−kCr−k^{n-k}C_{r-k}. If kk particular items must always be excluded, the number of ways is n−kCr^{n-k}C_r.

•

Geometric Applications: To form a line, we need to select 22 points (nC2^nC_2). To form a triangle, we need to select 33 non-collinear points (nC3^nC_3).

📐Formulae

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

nCr=nPrr!^nC_r = \frac{^nP_r}{r!}

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

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

nC0=1,nCn=1,nC1=n^nC_0 = 1, \quad ^nC_n = 1, \quad ^nC_1 = n

💡Examples

Problem 1:

A committee of 55 members is to be formed from 66 gentlemen and 44 ladies. In how many ways can this be done if the committee must contain at least 33 ladies?

Solution:

We need to select 55 members with the condition of at least 33 ladies. There are two possible cases: Case 1: 33 ladies and 22 gentlemen. Ways = 4C3×6C2=4×15=60^4C_3 \times ^6C_2 = 4 \times 15 = 60. Case 2: 44 ladies and 11 gentleman. Ways = 4C4×6C1=1×6=6^4C_4 \times ^6C_1 = 1 \times 6 = 6. Total ways = 60+6=6660 + 6 = 66.

Explanation:

Since the condition is 'at least 3', we sum the combinations for exactly 3 ladies and exactly 4 ladies (the maximum available).

Problem 2:

In how many ways can a cricket team of 1111 players be chosen out of 1515 players if one particular player is always chosen and another particular player is always excluded?

Solution:

Total players n=15n = 15. We need to choose r=11r = 11.

  1. One player is always included: We now need to choose 11−1=1011 - 1 = 10 more players from the remaining 15−1=1415 - 1 = 14 players.
  2. One player is always excluded: We must choose our 1010 players from 14−1=1314 - 1 = 13 available players. Number of ways = 13C10^{13}C_{10}. Using nCr=nCn−r^nC_r = ^nC_{n-r}: 13C10=13C13−10=13C3^{13}C_{10} = ^{13}C_{13-10} = ^{13}C_3 13C3=13×12×113×2×1=13×2×11=286^{13}C_3 = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 13 \times 2 \times 11 = 286

Explanation:

When an item is included, both nn and rr decrease. When an item is excluded, only nn decreases.

Problem 3:

There are 1010 points in a plane, out of which 44 points are collinear. How many triangles can be formed using these points?

Solution:

To form a triangle, we need to select 33 points from the 1010 points. Total ways to select 33 points = 10C3^{10}C_3. However, 33 points selected from the 44 collinear points will not form a triangle. Ways to select 33 points from collinear points = 4C3^4C_3. Number of triangles = 10C3−4C3^{10}C_3 - ^4C_3 10C3=10×9×83×2×1=120^{10}C_3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120 4C3=4C1=4^4C_3 = ^4C_1 = 4 Total triangles = 120−4=116120 - 4 = 116.

Explanation:

We subtract the combinations of points that lie on the same straight line because they result in a degenerate triangle (a line segment).