Combination – Explanation & Examples

There are many interesting scenarios in which we are required to find the possible arrangements of a given set of objects. For example, in how many ways can we select a team from a given set of players? Or how many triangles can be formed by joining the vertices of an octagon?  The theory of combinations helps us in answering such questions

Combinations refer to the possible arrangements of a set of given objects when changing the order of selection of the objects is not treated as a distinct arrangement.

After reading this article, you should understand:

1. Combination Formula and its derivation
2. Difference between permutation and combination
3. How to solve problems related to combinations

It is advisable to refresh the following concepts to understand the material discussed in this article.

1. Factorial
2. Counting Principle
3. Permutation

What Is a Combination

Combinations refer to the number of possible ways in which elements/objects can be arranged while the order of arrangements does not matter. In smaller sets of objects, one can form the combinations easily while in the case of large sets, we use the formula to calculate the total number of combinations. Suppose you go to an ice-cream shop and want to order three scoops of ice cream.

The available flavors at the shop are Vanilla, Orange, Chocolate, and Strawberry. In this example, the order does not matter, i.e., the ice cream with Vanilla, Orange, and Chocolate scoop is the same as the ice cream with Orange, Vanilla, and Chocolate scoop. So, $\textrm{VOC= OVC= CVO=VCO}$ and we only take one of these combinations, and the rest are ignored as they are all the same.

Let us take the initials of all flavors and form all possible combinations. $\textrm{VOC, VOS, VCS, and OCS}$ are four possible combinations in this scenario. Let us take another example of a triangle with vertices $XYZ$.

By re-arranging the vertices we get a total of six numbers of possible ways to name the triangle.

So, $\textrm{XYZ, XZY, YXZ, YZX, ZYX, and ZYX}$ are the six possible names of a triangle with vertices$ XYZ$ but it does not change the fact that it is still the same triangle. So if we have to calculate possible triangles combination out of $3$ vertices we will only get one triangle. This is in contrast to the case of permutations where we would have gotten $6$ possible triangles. When arranging the objects in a specific order is immaterial or insignificant then combinations are used instead of permutations

How to Calculate Combinations

To calculate combinations, we rely on the factorial operation and the fundamental counting principle. We briefly describe both these concepts below:

Factorial

A factorial (denoted by ‘ ! ‘) is defined as the product of all positive integers that are less than or equal to a given positive integer. For instance$3! = 3 \times 2 \times 1 =6$ and $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. We also define $0! = 1! = 1$.

Factorial Rule

The factorial of any integer $n$ can be calculated from the factorial of the previous integer, i.e., $n-1$. The factorial rule states that

$n! = n \times (n-1)!$

Fundamental Counting Principle

The fundamental counting principle states that if one event can occur in $A$ different ways and a second event can occur in $B$ different ways then the total number of ways in which both events can occur is $A \times B$.

For example, in a restaurant, if you can order three different types of deserts, four different main courses, and two different appetizers then the total number of possible meal combinations that you can order is $3 \times 4 \times 2 = 24$.

Using factorial and the fundamental counting principle, we can derive a formula for combinations as described below

Combinations Formula

The possible combinations of $n$ different objects taken $r \leq n$ at time is given as

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

Derivation

Suppose that we have $n$ distinct digits for a code taken $r$ at a time.

The first digit place can be filled from $n$ distinct digits: $n$ ways

The second-place digit can be filled with $(n-1)$ distinct digits: $(n-1)$ ways

The third-place digit can be filled with $(n-2)$ distinct digits: $(n-2)$ ways

The rth place can be filled with $(n-(r-1))$ distinct digits: $(n-(r-1))$ ways.

The completion of all $r$ places from $n$ distinct digits creates an ordered subset of $r$ elements. These $r$ elements can be re-arranged in $r!$ ways.  

Hence the total number of arrangements in which order does not matter can be given as

$C(n,r) = \frac{n \times n-1 \times n-2  \times \cdots \times n-(r-1)}{r!}$

Multiplying and dividing the above expression by $(n-r)!$ and utilizing the factorial rule, we get

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

It is interesting to note that if we put $r=n$ in the above formula, we get

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

Hence, if we take the entire set of available objects, we get only one possible arrangement if the order of selection does not matter.

Difference Between Combination and Permutation

People often confuse combinations and permutations. Permutation takes sequences and order arrangement very seriously while on the other hand combination totally ignores it. For permutation Apple, Banana and Lemon are different from Banana, Lemon, and Apple and for combination Apple, Banana and Lemon is equal to Banana, Lemon, and Apple.  Let us take an example to understand how combination and permutation are done on a single problem.

Example:

We want to build a computer password of five digits, the Total number of digits to choose from lies between $0-7$ (no repetition of the digits is allowed). Let us solve the problem using permutation. So we have eight available digits to choose from so for our first digit we have eight possible options. Let’s say we choose $0$ as our first digit. Now next digit for the password can be selected from seven possible numbers. Suppose we selected $1$ as the next digit for the password so, now the third digit can be selected from six available numbers.

Keeping up the same process and we end up with the password $01234$. We had eight options for the first digit, seven for the second, six for the third, five for the fourth, and four options for the fifth digit. So, total number of possible arrangements would be $8 \times 7 \times 6 \times 5 \times 4 = 6720$.

In the case of combinations, the order is not important, so $01234$ is the same as $10234$ or $43210$. Since there are $5$ digits in our password so there would be $5!$ such re-arrangements that result in the same combination. Therefore, to evaluate the total number of combinations, we divide the total permutations, i.e., $6720$ by $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ to get $6720 /5 = 56$ combinations.

So, we can conclude that

Examples

Let us see a number of examples to get a firm grasp on the concept of combinations

Example 1: Evaluate $C(16,13)$

Solution:

We know that

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

$C(16,13)= \frac{16!}{13! (16-13)!)}$

 $= \frac{16\times15\times14\times13!}{13!\times3!}$

 $= \frac{3360}{6}$

$= 560$

Example 2: Find the value of $n$ and $k$ for given data

1. $C(n,14) = \frac{16 \times 15}{2!}$
2. $C(n,k) = 15$ and $P(n,k) = 30$

Solution:

1)

$\frac{n!}{14!(n-14)!} =  \frac{16\times 15}{2!}$

Multiplying and dividing by 14! On R.H.S

$\frac{n!}{20!(n-14)!} = \frac{16\times15\times14!}{14!\times2!}$

$\frac{n!}{20!(n-14)!} = \frac{16!}{14! (16-14)!}$

$C(n,14) = C(16,14)$

So, $ n= 16$

2)

$C(n,k) = 15$

$\frac{n!}{k!(n-k)!}=15$

$n! = (15 \times k!)(n-k)!$     (A)

$P(n,k) = 30$

$\frac{n!}{(n-k)!}=30$

$n! = 30\times(n-k)!$            (B)

Solving equation (A) and (B) we get

$(15\times k!)(n-k)! = 30\times (n-k)!$

            $15\times k!    = 30$

             $k!  =  2$

we can write 2 as $2!=2\times1 $

              $k! = 2!$

Hence $k=2$  and putting this value in equation (B)

$n!   = 30\times (n-2)!$

$n(n-1)(n-2)! = 30\times(n-2)!$

$n\times(n-1)    = 6 \times 5$

So, $n= 6$

Example 3:  James, Taylor, Steve, and Chris are four soccer players and we want to build a team consisting of three players. In how many ways this team can be formed?    

Solution:

We take initials of each name as $J, T, S, and C$

We know that order of arrangement is not important in combination related problems

So team can be built as $JTS, JTC, JSC$ and $TSC$. Here $JTS= STJ = TJS$ so we do not include such arrangements while calculating combination numerical.

So,

 $C(4,3) = \frac{4!}{3! (4-3)!)}$

$C(4,3) = \frac{4\times3!}{3!}$

$C(4,3) = 4 $

Example 4: A Science club in a school consists of$ 18$ girls and $10$ boys. In how many ways a team of $5$ girls and $3$ boys can be formed?  

Solution:

The number of combinations of $7$ girls out of $18$ can be written as $C(18,7)$

Similarly the number of combinations of $3$ boys out of $10$ can be written as   $C(10,3)$

We want to find in how many ways they can for a team. We can do it by simply multiplying the both combination

            $C(18,7) \times C(10, 3) = [\frac{18!}{7!(18-5)!}][\frac{10!}{3!(10-3)!}]$

                                                         $= [\frac{18!}{7!(13)!}][\frac{10!}{3!(7)!}]$

                                                         $= (204) (120)$

                                                        $ = 244804$.

Example 5: A safe is to be locked with a four-digit password. The digits must contain numbers from $0-7$.

1. How many different password options you will have if no order arrangement is followed? ( Combination Problem)
2. How many different password options you will have if the required arrangement is to be followed? ( Permutation Problem)

   Solution:

1)

In this first case the order does not matter and we have to choose four digits out of 8.

 $C(8, 4) = \frac{8!}{4! (8-4)!)}$

$C(8, 4) = \frac{8!}{4!\times4!}$

$C(8, 4) = \frac{40320}{576}$

$C(8, 4) = 70\,$ ways

2)

Here the order of selection matters and hence we use the formula for permutation, i.e.,

$P(8,4) = \frac{8!}{(8-4)!)}$

$P(8,4) = \frac{8!}{4!}$

$P(8,4) = \frac{40320}{24}$

$P(8,4) = 1680$ ways

Example 6: A soccer team consisting of $11$ players is to be formed from a pool of $15$ players

1. In how many ways the team can be selected?
2. In how many ways the team can be selected if the Captain of the team is to be included in every team?

Solution:

1)

Total number of ways in which $11$ players can be selected from a pool of $15$ players can be calculated as:

$C(15, 11) = \frac{15!}{11! (15-11)!)}$

$C(15, 11) = \frac{15!}{11! 4!}$

$C(15, 11) = \frac{15\times14\times13\times12\times11!}{11! 4!}$

$C(15, 11) = \frac{32760}{24}$

$C(15, 11)=  1365 \,$ ways

2)

If Captain is to be included in every team selection then we have to select $10$ players from a pool of $14$ players:

$C(14,10) = \frac{14!}{10! (14-10)!)}$

$C(14,10) = \frac{14!}{10! 4!}$

$C(14,10) = \frac{14 \times 13 \times 12 \times 11 \times10!}{10! 4!}$

$C(14,10) = \frac{24024}{24}$

$C(14,10) =  1001 \,$ways

The Complementary Combination

The rule of complementary combination is helpful in reducing the complexity of calculations of many combainations problems. Complementary combination states that the number of $n$ objects taken $k$ at a time is equal to number of combination of $n$ objects taken $(n-k)$ at a time, i.e.,

$C(n,k) =C(n,n-k)$

Proof:

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

$C(n, n-k)= \frac{n!}{(n-k)!(n-n+k)!}$

$C(n,n-k) = \frac{n!}{(n-k)!k!} = C(n.k)$

Example 7: Show that $C(14,12) =C(14,14-12)$

Solution:

First calculating left hand side

$C(14,12) = \frac{14!}{12!(14-12)!)}$

$C(14,12)= \frac{14 \times 13 \times 12!}{12!2!}$

$C(14,12)= \frac{14 \times 13}{2}$

$C(14,12) = 91$

Now calculating the right hand side

$C(14,14-12)= \frac{14!}{(14-12)!{(14-(14-12)})!}$

$C(14,14-12)= \frac{14!}{(14-12)!{(14-14+12})!}$

$C(14,14-12)= \frac{14!}{(14-12)!{12}!}$

$C(14,14-12) = 91$

Practice Questions:

1. How many triangles can be formed by joining the vertices of a
   1. Quadruple
   2. Octagon
   3. Decagon
2. How many Diagonals can be formed by joining the vertices of a
   1. Quadruple
   2. Octagon
   3. Decagon
3. Prove that $C(19,18) + C(19,17) = C(20,18)$
4. In how many ways a committee of 6 boys and 4 girls can be chosen from 12 boys and 6 girls? In how many ways the committee will be formed if a particular boy and girl has to be included in each committee?
5. If $C(n,12) =C(n,16) $ calculate the value of $n$?

Answer Key

1)

We know that the triangle has $3$ vertices so for given amount of vertices we have to select $3$ to form a triangle.

A quadruple has $4$ sides so, the number of possible triangles is

$C(4,3) = \frac{4!}{3! (4-3)!)}$

$C(4,3) = \frac{4!}{3!\times1}$

$C(4,3) = 4$ ways

An Octagon has $8$ sides so we can calculate

$C(8,3) = \frac{8!}{3! (8-3)!)}$

$C(8,3) = \frac{8!}{3!\times5!}$

$C(8,3) = 56$ ways

A Decagon has $10$ sides, so we can calculate

$C(10,3) = \frac{10!}{3! (10-3)!)}$

$C(10,3) = \frac{10!}{3!\times7!}

$C(10,3) = 120$ ways

2)

We know a diagonal is a line segment when two points are joined together.

A quadruple has four sides and we know a line segment is formed by joining two points or vertices so,

Total number of line segments:      $C(4,2) = \frac{4!}{2! (4-2)!)}$

$C(4,2) = \frac{4!}{2!\times2!}$

$C(4,2) = 6$

But these six segments include the line segments of all the sides which are not considered diagonals so by subtracting the sides from the total number of line segments we will get the total number of diagonals

Total number of diagonals $= 6-4 =2$

For Octagon we have $8$ sides

Total number of line segments:           $C(8,2) = \frac{8!}{2! (8-2)!)}$

$C(8,2) = \frac{8!}{2!\times6!}$

$C(8,2) = 28$

Total number of diagonals $= 28-8 =20$

For Decagon we have $10$ sides

Total number of line segments:           $C(10,2)= \frac{10!}{2! (10-2)!)}$

$C(10,2) = \frac{10!}{2!\times8!}$

$C(10,2) = 45$

Total number of diagonals $= 45-10 =35$

3)

Prove that $C(19,18) +C(10,17) = C(20,18)$

First Calculating the Left hand side

$ L.H.S = [\frac{19!}{18! (19-18)!}]+[\frac{19!}{17! (19-17)!}]$

          $= [\frac{19 \times 18!}{18!}]+[\frac{19 \times 18 \times 17!}{17! (2)!}]$

          $= (19)+(171)$

          $= 190$

$R.H.S =C(20,18)= \frac{20!}{18!(20-18)!)}$

 $ = \frac{20 \times 19 \times18!}{18! \times 2!}$

$= \frac{20 \times 19}{2}$

$ = 190$.

 So, L.H.S = R.H.S

4)

A committee consisting of $6$ boys and $4$ girls can be calculated as

$C(12,6) \times C(6,4) = [\frac{12!}{6! (12-6)!}][\frac{6!}{4! (6-4)!}]$

$= [\frac{12!}{6!\times 6!}][\frac{6!}{4! (2)!}]$

$= (924)(15)$

 $= 13860 \,$ ways

If a particular boy and a girl is included in each committee then we can calculate as

$C(11,5) \times C(5,3) = [\frac{11!}{5! (11-5)!}][\frac{5!}{3! (5-4)!}]$

 $= [\frac{11!}{5! 6!}][\frac{5!}{3! (2)!}]$

$= (462)(10)$

 $= 4620\, $ ways

5)

By the relation of complimentary combintions

$C(n,k) =C(n,n-k)$

So,

$C(n,12) = C(n,n-12)$

And we have been given that $C(n, 12) = C(n,16)$

So,

$C(n,n-12)= C(n,16)$

So we have same indices and base and we can calculate value of n as

$n-12=16$

$n=16+12$

$n= 28$

Previous Lesson | Main Page | Next Lesson