Algebra 2 - Combinations

Introduction

• A combination is an arrangement of objects taken from $n$ distinct objects without reference to the order. 
• The number of combinations of $n$ objects taken $r$ at a time is expressed as ${}_{n}C_r=\frac{n!}{r!\left(n-r\right)!}$ or $\left(\begin{array}{c}n\\ r\end{array}\right), C\left(n,r\right)$
• For instance, the combination of letters $m, n, x, y$ taken three (3) at a time are $\left\{m, n, x\right\}, \left\{m, n, y\right\}, \left\{m, x, y\right\}, \left\{n, x, y\right\}$.
• Observe that the following arrangement of letters are the same: $\left\{m, n, x\right\}, \left\{x, n, m\right\}, \left\{n, m, x\right\}, \left\{x, m, n\right\}, \left\{n, x, m\right\}, \left\{m, x, n\right\}$. Each of these arrangements simply denotes $\left\{m, n, x\right\}$.
• The notation ${}_{n}C_r$ is read as "Combination $n$ taken $r$".
• In Binomial Theorem, the concept of Combinations is used. To recap, we say that the combination formula $\left(\begin{array}{c}n\\ r\end{array}\right)=\frac{n\left(n-1\right)\left(n-2\right)...\left(n-r+1\right)}{1·2·3...\left(r-1\right)r}$ where both $r and n$ are positive integers and $r\le n$ generates the binomial coefficients in an expansion.

Relationship Between Permutation and Combination

Suppose that we have 9 numbers in code 746395218. If we determine the number of ways to rearrange (permute) any three numbers from it, we compute it as $9·8·7=504$. 

Assume that order is not important and we are only interested in the 3 numbers 759 being selected from the code 746395218. If an order does not matter, we count the permutations $759, 795, 957, 597, 579, 975$ as one combination.

How are the combinations of 9 things taken 3 at a time related to their permutations?

For any one combination consisting of 3 numbers, say 759, there are $3!$ permutations. Hence, we form a relationship that $Number of Combinations=\frac{Number of Permutations}{3!}$

To illustrate, we have: $Number of Combinations=\frac{9·8·7}{3!}=84$

Examples

Example 1. How many combinations are there in 5 distinct things taken 4 at a time?

Solution: Applying the formula gives:

${}_{5}C_4=\frac{5!}{4!\left(5-4\right)!}=\frac{5·4·3·2·1}{\left(4·3·2·1\right)\left(1!\right)}=5$

 

Example 2. A class has 5 boys and 7 girls. In how many ways can the class elect the president, the vice president, the secretary, the treasurer, and the auditor? In how many ways can the class elect 5 members of a certain committee?

Solution 1. The first question is related to permutations since electing the said positions implies distinct filing. 

${}_{12}P_5=\frac{12!}{\left(12-5\right)!}=95,040 ways$

Solution 2. The second question is related to combinations because electing 5 members of a certain committee implies one position only.

${}_{12}C_5=\frac{12!}{5!\left(12-5\right)!}=792 ways$

 

Example 3. In how many ways can a student answer 10 out of 25 questions if he/she is required to answer 5 of the first 9 questions?

Solution:

Since 5 of the 9 questions must be answered, we have $C\left(9,5\right)$ ways.

The student must now answer 5 of the remaining 16 questions, which can be done in $C\left(16,5\right)$ ways.

$C\left(9,5\right)·C\left(16,5\right)=550,368 ways$

 

Example 4. From a group of 9 men and 7 women, six persons are to be selected to form a committee so that at least four men are there on the committee. In how many ways can this be done?

Solution:

We have (4 men and 2 women), (5 men and 1 woman), and (6 men and 0 women).

$C\left(9,4\right)·C\left(7,2\right)+C\left(9,5\right)·C\left(7,1\right)+C\left(9,6\right)·C\left(7,0\right)=3612 ways$

 

Cheat Sheet

• Use the formula $C=\frac{n!}{r!\left(n-r\right)!}$ when order does not matter, and repetition is allowed.
• Use the formula $C=\frac{\left(n+r-1\right)!}{r!\left(n-1\right)!}$ when order is not important, and repetition is not allowed.
• To determine the sum of all possible combinations of $n$ distinct things, always bear in mind the relationship $C\left(n,0\right)+C\left(n,1\right)+C\left(n,2\right)+C\left(n,3\right)+...+C\left(n,n\right)=2^n$
• To determine the number of diagonals that can be drawn in a polygon, we use the formula $C\left(n,2\right)-n$ where $n=number of sides$ and the constant 2 denotes two endpoints of a diagonal.
• To find the number of combinations taking $n$ different elements 1 at a time, 2 at a time, and so on up to $n$ at a time, we use $C=2^n-1$.

Blunder Areas

• Always analyze a problem situation to make sure whether the order of arrangement matters or not. This determines whether the problem is related to combinations or permutations.