5.1: Counting

Most of us think that counting is as easy as 1, 2, 3... When counting objects, one needs to be careful to not count an object more than once or miss an object. In this section, we will explore some ideas behind counting.

The Multiplication Principle

If a process can be broken down into two steps, performed in order, with m ways of completing the first step and n ways of completing the second step after the first step is completed, then there are (m)(n) ways of completing the process.

Example \(\PageIndex{1}\):

Suppose that pizza can be ordered in 3 sizes, 2 crust choices, 4 choices of toppings, and 2 choices of cheese toppings. How many different ways can a pizza be ordered?

Solution

To determine the number of possibilities, we will use the multiplication principle. Let \(S = \) pizza size, \(C =\) crust choice, \(T =\) topping choice, and \(Ch =\) cheese choice.

Since we need to choose one choice from each category, we can write that we need to choose size, and crust, and topping, and cheese.

Let's use the multiplication principle:

\[\begin{align} \text{Ways} &= (S)(C)(T)(Ch) \nonumber \\[5pt] &= (3)(2)(4)(2) \nonumber \\[5pt] &= 48 \nonumber\end{align} \nonumber\]

What if there was only one choice for cheese? How would this affect the calculation?

Example \(\PageIndex{2}\):

Count the number of possible outcomes when:

1. A coin tossed four times.
2. A standard die is rolled five times.

Permutation

Definition: Permutation

A permutation is an ordered arrangement of objects.

The number of permutations of \(n\) distinct objects, taken all together, is \(n!\), where

\[n!= n(n-1)(n-2).....1 \label{perm}\].

Note that \(0!=1\).

Example \(\PageIndex{3}\)

Miss James wants to seat 30 of her students in a row for a class picture. How many different seating arrangements are there? 17 of Miss James' students are girls and 13 are boys. In how many different ways can she seat 17 girls together on the left, then the 13 boys together on the right?

Solution

Let's start with the girls. There are 17 of them, and so, when seating the first girl in the row, there are 17 choices. The next spot will have 16 choices left, then 15, and so on. Thus, the number of choices for seating the girls can be written \(17!\).

For the boys, by the same reasoning, there are \(13!\) ways to seat them on the right.

Now let's apply the multiplication principle: we need to seat the girls and the boys at the same time. For each permutation we might pick for the girls, we need to apply each different case for the boys as a distinct possibility. So, our result is \((17!)(13!)\). This means there are \(2.215 \cdot 10^{24}\) different ways to seat these students with girls on the left and boys on the right!

Permutations

The number of permutations of \(r \) objects picked from \(n\) objects, where \(0 \leq r \leq n\), is

\[_nP_r = \displaystyle \frac{n!}{(n-r)!}.\label{pick}\]

When reading this out loud, we say "n Pick r" - when we pick something, like a team for sports or favorite desserts, the order matters.

Example \(\PageIndex{4}\):

Using the digits 1,3,5,7, and 9, with no repetitions of digits, how many three–digit numbers can be made?

Solution

We have \(n = 5\) objects, and we want to pick \(r = 3\) of them. So via Equation \ref{pick}:

\[ \begin{align} _nP_r &= \displaystyle \frac{5!}{(5-3)!} \nonumber\\[5pt] &= \displaystyle \frac{5!}{2!} \nonumber \\[5pt] &= \displaystyle \dfrac{(5)(4)(3)(2)(1)}{(2)(1)} \nonumber \\[5pt] &= (5)(4)(3) \nonumber \\[5pt] &= 60 \nonumber \end{align} \nonumber \]

Combination

The following is defined already in 3.3 Finite Difference Calculus.

 Combinations

The number of combinations of \(r \) objects chosen from \(n\) objects, where \(0 \leq r \leq n\), is

\[_nC_r = \displaystyle \dfrac{n!}{(n-r)! r!} \label{combo}\]

\(_nC_r \) is also denoted as \( \displaystyle n \choose r\). When reading this out loud, we say "n Choose r" - when we choose objects, like candies out of a bag or clothes from a closet, the order doesn't matter.

Example \(\PageIndex{5}\):

Evaluate \(_6C_2\), and \(_4C_4\).

Solution

Let's try \(_6C_2\), or \(\displaystyle 6 \choose 2\):

\(_nC_r = \displaystyle \frac{6!}{(6-2)!2!}\)

\(_nC_r = \displaystyle \frac{6!}{(4)!2!}\)

\(_nC_r = \displaystyle \frac{(6)(5)(4)(3)(2)}{(4)(3)(2)(2)}\)

\(_nC_r = \displaystyle \frac{(6)(5)}{(2)}\)

\(_nC_r = \displaystyle \frac{30}{2}\)

\(_nC_r = 15\)

Now let's tackle \(\displaystyle 4 \choose 4\):

\(_nC_r = \displaystyle \frac{4!}{(4-4)!4!}\)

\(_nC_r = \displaystyle \frac{4!}{0!4!}\)

The result of \(0!\) is \(1\).

\(_nC_r = \displaystyle \frac{4!}{4!}\)

\(_nC_r = 1\)

This makes sense: there is only one way to choose four things from a group of four things. You choose all of them, and that is the only option.

Example \(\PageIndex{6}\):

How many 5-member committees are possible if we are choosing members from a group of 30 people?

Let's see: we have 30 people to choose from, so \(n = 30\). We want to choose 5 members, so \(r = 5\). Lastly, we don't care about the order in which we choose, so we use \(_nC_r\):

\(\displaystyle 30 \choose 5\)\( = \displaystyle \frac{30!}{(30-5)!5!}\)

\(\displaystyle 30 \choose 5\)\( = \displaystyle \frac{30!}{25!5!}\)

\(\displaystyle 30 \choose 5\)\( = \displaystyle \frac{(30)(29)(28)(27)(26)}{5!}\)

\(\displaystyle 30 \choose 5\)\( = \displaystyle \frac{(30)(29)(28)(27)(26)}{120}\)

\(\displaystyle 30 \choose 5\)\( = 142 506\)

Example \(\PageIndex{7}\):

1. In how many ways can 3 men and 3 women sit in a row, if no two men and no two women are next to each other?
2. In how many ways can 3 men and 3 women sit in a circle, if no two men and no two women are next to each other?

Pascal's Triangle

Pascal's triangle was developed by the mathematician Blaise Pascal. It is generated by adding the two terms diagonally above to receive the new term, where the first term is 1, which is defined as \(_nC_r = _{n-1}C_{r -1}+_{n-1}C_{r }\).

The triangle is useful when calculating \(_nC_r\) as well: count down \(n\) rows, and then count in \(r\) terms. For example: \(_7C_2\) means that we look at row 7, term 2: 6.

• Gives the coefficients of \( (a + b)^n.\)

• The entries of the nth row are \(C(n,0), C(n,1)...C(n,n)\).

• The sums of each row are consecutive powers of 2.

• The third element from each row yields triangular numbers.

Binomial Expansion

\((x+y)^n = x^n+n x^{(n-1)}y + \cdots+{ n\choose k} x^k y^{(n-k)} + \cdots+y^n\).