Combinations C(n,r)

In mathematics, a combination is a selection of items from a set where the order of selection does not matter. This is in contrast to permutations, where the order of selection is important. For example, if you have a set of three fruits {apple, banana, cherry} and you want to choose two fruits, the combinations are {apple, banana}, {apple, cherry}, and {banana, cherry}. The order in which you pick them doesn't change the selection – picking an apple then a banana is the same combination as picking a banana then an apple.

The number of combinations of choosing 'r' items from a set of 'n' distinct items is denoted by C(n,r), nCr, or C_n,r. It is also sometimes written as C(n,r) or Cⁿ_r.

The Formula for Combinations

The formula to calculate the number of combinations of choosing 'r' items from a set of 'n' distinct items is:

$$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Where:

• 'n' is the total number of distinct items in the set.
• 'r' is the number of items to be chosen from the set.
• '!' denotes the factorial operation. The factorial of a non-negative integer 'k', denoted by k!, is the product of all positive integers less than or equal to k. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. By definition, 0! = 1.

Derivation of the Combination Formula

We can derive the combination formula from the permutation formula. The number of permutations of choosing 'r' items from 'n' items, denoted P(n,r), is given by:

$$P(n, r) = \frac{n!}{(n-r)!}$$

This formula counts arrangements where the order matters. For any set of 'r' chosen items, there are r! ways to arrange them (i.e., r! permutations). Since the order does not matter in combinations, we must divide the number of permutations by r! to get the number of combinations.

Therefore,

$$C(n, r) = \frac{P(n, r)}{r!} = \frac{\frac{n!}{(n-r)!}}{r!} = \frac{n!}{r!(n-r)!}$$

Properties of Combinations

Combinations have several important properties that simplify calculations and problem-solving:

1. Symmetry Property: $C(n, r) = C(n, n-r)$

   This property means that choosing 'r' items from 'n' is the same as choosing to leave out 'n-r' items from 'n'.

   Example: If you have 10 students and you want to form a committee of 3, the number of ways is $C(10, 3)$. This is the same as choosing 7 students to *not* be on the committee, which is $C(10, 7)$. $$C(10, 3) = \frac{10!}{3!(10-3)!} = \frac{10!}{3!7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 10 \times 3 \times 4 = 120$$ $$C(10, 7) = \frac{10!}{7!(10-7)!} = \frac{10!}{7!3!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$$

   Memory Trick: Think of it as selecting a team (r) or selecting those who are NOT on the team (n-r). The outcome is the same number of team formations.
2. Base Cases:
   • $C(n, 0) = 1$: There is only one way to choose 0 items from 'n' items (which is to choose none of them).
   • $C(n, n) = 1$: There is only one way to choose 'n' items from 'n' items (which is to choose all of them).
   • $C(n, 1) = n$: There are 'n' ways to choose 1 item from 'n' items.
   • $C(n, n-1) = n$: There are 'n' ways to choose 'n-1' items from 'n' items (which is equivalent to choosing which 1 item to leave out, using the symmetry property $C(n, n-1) = C(n, n-(n-1)) = C(n, 1) = n$).
3. Pascal's Identity: $C(n, r) = C(n-1, r-1) + C(n-1, r)$

   This identity is crucial for understanding Pascal's Triangle and can be used for recursive calculations. It states that the number of ways to choose 'r' items from 'n' is the sum of:

   • The number of ways to choose 'r-1' items from the first 'n-1' items (assuming a specific item is included in the selection).
   • The number of ways to choose 'r' items from the first 'n-1' items (assuming that specific item is *not* included in the selection).

   Example: $C(5, 3) = C(4, 2) + C(4, 3)$ $$C(5, 3) = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10$$ $$C(4, 2) = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$$ $$C(4, 3) = \frac{4!}{3!1!} = \frac{4}{1} = 4$$ $$C(4, 2) + C(4, 3) = 6 + 4 = 10$$

   Pascal's Triangle Connection: Each number in Pascal's Triangle is the sum of the two numbers directly above it. The entries in the n-th row (starting with n=0) are $C(n, 0), C(n, 1), C(n, 2), \dots, C(n, n)$. Pascal's Identity $C(n, r) = C(n-1, r-1) + C(n-1, r)$ directly reflects this summing property.
4. Condition for Validity: For $C(n, r)$ to be defined, we must have $n \ge 0$, $r \ge 0$, and $n \ge r$. If $r > n$, then $C(n, r) = 0$.

Applications of Combinations

Combinations are fundamental to probability and statistics, and they appear in various real-world scenarios.

1. Forming Committees or Teams

This is a classic application. If you need to select a group of people for a committee, and the roles within the committee are not specified (or are identical), then it's a combination problem.

Example: A school needs to select 5 students from a class of 30 to represent them at a debate competition. How many different groups of 5 students can be selected?

Here, n = 30 (total students) and r = 5 (students to be selected). The order in which students are selected does not matter.

$$C(30, 5) = \frac{30!}{5!(30-5)!} = \frac{30!}{5!25!} = \frac{30 \times 29 \times 28 \times 27 \times 26}{5 \times 4 \times 3 \times 2 \times 1}$$ $$C(30, 5) = \frac{30}{5 \times 3 \times 2} \times \frac{28}{4} \times 29 \times 27 \times 26 = 1 \times 7 \times 29 \times 27 \times 26 = 142,506$$

So, there are 142,506 different groups of 5 students that can be selected.

2. Probability Calculations

Combinations are frequently used to calculate probabilities, especially in scenarios involving random selections.

Example: A bag contains 7 red balls and 5 blue balls. If 3 balls are drawn at random, what is the probability that all 3 are red?

Total number of balls = 7 + 5 = 12. We are drawing 3 balls. The total number of ways to choose 3 balls from 12 is $C(12, 3)$. $$C(12, 3) = \frac{12!}{3!9!} = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = 2 \times 11 \times 10 = 220$$ The number of ways to choose 3 red balls from the 7 red balls is $C(7, 3)$. $$C(7, 3) = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 7 \times 5 = 35$$ The probability of drawing 3 red balls is the ratio of favorable outcomes to the total possible outcomes: $$P(\text{3 red balls}) = \frac{\text{Number of ways to choose 3 red balls}}{\text{Total number of ways to choose 3 balls}} = \frac{C(7, 3)}{C(12, 3)} = \frac{35}{220}$$ Simplifying the fraction: $\frac{35}{220} = \frac{7 \times 5}{44 \times 5} = \frac{7}{44}$.

3. Card Games

In card games like Poker or Bridge, the hand dealt is a combination because the order in which you receive your cards doesn't matter.

Example: In a standard deck of 52 cards, how many different 5-card hands can be dealt?

Here, n = 52 and r = 5.

$$C(52, 5) = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} = \frac{52 \times 51 \times 50 \times 49 \times 48}{5 \times 4 \times 3 \times 2 \times 1}$$ $$C(52, 5) = \frac{52}{4 \times 2} \times \frac{51}{3} \times \frac{50}{5} \times 49 \times 48 = (13 \times 17 \times 10 \times 49 \times 48) = 2,598,960$$

There are 2,598,960 possible 5-card hands.

4. Geometric Problems

Combinations can be used to count the number of lines or triangles that can be formed from a set of points.

Example: How many distinct lines can be formed by joining 10 points in a plane, no three of which are collinear?

To form a line, we need to choose any 2 distinct points. Since the order of choosing the points doesn't matter (the line AB is the same as line BA), this is a combination problem.

Here, n = 10 (total points) and r = 2 (points needed for a line).

$$C(10, 2) = \frac{10!}{2!(10-2)!} = \frac{10!}{2!8!} = \frac{10 \times 9}{2 \times 1} = 45$$

Thus, 45 distinct lines can be formed.

Similarly, to form a triangle, we need to choose 3 non-collinear points. If we have 'n' points, no three collinear, the number of triangles is $C(n, 3)$.

Key Differences: Permutations vs. Combinations

It is crucial to distinguish between permutations and combinations. The fundamental difference lies in whether the order of selection matters.

Solving Combination Problems: A Step-by-Step Approach

Follow these steps to effectively solve combination problems:

1. Identify 'n' and 'r':
   • 'n' is the total number of distinct items available.
   • 'r' is the number of items you need to select.
2. Determine if Order Matters:
   • If the order of selection *does not* matter, it's a combination problem.
   • If the order of selection *does* matter, it's a permutation problem.
3. Apply the Correct Formula:
   • For combinations: $C(n, r) = \frac{n!}{r!(n-r)!}$
   • For permutations: $P(n, r) = \frac{n!}{(n-r)!}$
4. Simplify and Calculate:
   • Factorials can become very large, so look for opportunities to cancel terms. For example, instead of calculating $10!$ and $7!$ separately, write $10!$ as $10 \times 9 \times 8 \times 7!$ to cancel out $7!$.
   • $C(n, r) = \frac{n \times (n-1) \times \dots \times (n-r+1)}{r \times (r-1) \times \dots \times 1}$
5. Check for Special Cases or Constraints:
   • Are there any restrictions on certain items being selected or not selected?
   • Do you need to select items from different groups? (This might involve multiplying combinations from each group).
   • Are there identical items? (This leads to problems involving combinations with repetition, which is a more advanced topic).

Common Pitfalls and How to Avoid Them

Pitfall 1: Confusing Permutations and Combinations.
* Avoidance: Always ask the "order matters" question. Use keywords: "arrange," "order," "sequence" (suggest permutation); "select," "choose," "group," "hand" (suggest combination).

Pitfall 2: Calculation Errors with Factorials.
* Avoidance: Use the simplified formula $C(n, r) = \frac{n \times (n-1) \times \dots \times (n-r+1)}{r!}$ and cancel terms. For example, $C(10, 3) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1}$. Do not calculate $10!$ and $7!$ separately unless absolutely necessary.

Pitfall 3: Misinterpreting the Question.
* Avoidance: Read the question carefully. Identify exactly what is being asked for. Draw a diagram or list possibilities for simpler cases to ensure understanding.

Pitfall 4: Forgetting the Symmetry Property.
* Avoidance: Remember $C(n, r) = C(n, n-r)$. If 'r' is large (e.g., $C(20, 18)$), calculate $C(20, 2)$ instead, as it's much simpler. $C(20, 18) = C(20, 2) = \frac{20 \times 19}{2 \times 1} = 190$.

By understanding the formula, its properties, and practicing with various examples, you will gain confidence in solving combination problems for your exams.