## 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\xb72\xb73...\left(r-1\right)r}$ where both $randn$ 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\xb78\xb77=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 $NumberofCombinations=\frac{NumberofPermutations}{3!}$

To illustrate, we have: $NumberofCombinations=\frac{9\xb78\xb77}{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\xb74\xb73\xb72\xb71}{\left(4\xb73\xb72\xb71\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,040ways$

*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)!}=792ways$

**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)\xb7C\left(16,5\right)=550,368ways$

**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)\xb7C\left(7,2\right)+C\left(9,5\right)\xb7C\left(7,1\right)+C\left(9,6\right)\xb7C\left(7,0\right)=3612ways$

## 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 now 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=numberofsides$ 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.

- Keith Madrilejos
- 10 Comments
- 57 Likes