Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.1: Counting

( \newcommand{\kernel}{\mathrm{null}\,}\)

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 5.1.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:

Ways=(S)(C)(T)(Ch)=(3)(2)(4)(2)=48

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

Example 5.1.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(n1)(n2).....1.

Note that 0!=1.

Example 5.1.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.2151024 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 0rn, is

nPr=n!(nr)!.

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 5.1.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 ???:

nPr=5!(53)!=5!2!=(5)(4)(3)(2)(1)(2)(1)=(5)(4)(3)=60

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 0rn, is

nCr=n!(nr)!r!

nCr is also denoted as (nr). 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 5.1.5:

Evaluate 6C2, and 4C4.

Solution

Let's try 6C2, or (62):

nCr=6!(62)!2!

nCr=6!(4)!2!

nCr=(6)(5)(4)(3)(2)(4)(3)(2)(2)

nCr=(6)(5)(2)

nCr=302

nCr=15

Now let's tackle (44):

nCr=4!(44)!4!

nCr=4!0!4!

The result of 0! is 1.

nCr=4!4!

nCr=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 5.1.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 nCr:

(305)=30!(305)!5!

(305)=30!25!5!

(305)=(30)(29)(28)(27)(26)5!

(305)=(30)(29)(28)(27)(26)120

(305)=142506

Example 5.1.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 nCr=n1Cr1+n1Cr.

The triangle is useful when calculating nCr as well: count down n rows, and then count in r terms. For example: 7C2 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.

alt

Binomial Expansion

(x+y)n=xn+nx(n1)y++(nk)xky(nk)++yn.


This page titled 5.1: Counting is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

  • Was this article helpful?

Support Center

How can we help?