Counting things is hard! The following rules are shortcuts that allow us to count certain collections of things rapidly.

Example. In ordering a café latte, you have a choice of whole, skim or
soy milk; small, medium or large; and either one or two shots of espresso.
How many choices do you have in ordering one drink?

Multiplication rule

If there are a ways of doing something and b ways of doing another thing, then there are a · b ways of performing both actions.

Discuss: what is the connection between counting and probability?

Example. In the latte example above, what is the probability that a randomly selected customer will order a small soy latte with two shots of espresso? What is the probability that a customer will order a small soy latte, regardless of number of shots?

Example. A standard license plate consists of three letters followed
by four digits. For example, JRB-4412 and MMX-8901 are two standard
license plates. How many different standard license plates are possible?

Discuss: repetition vs. no repetition.

Example. In the license plate example above, what if there was a rule that no letter or digit could be used more than once in the same license plate? Now how many different license plates are possible?

Permutations

The number of ways that k items can be selected in order from a set of n elements is $P(n,k)=\frac{n!}{(n-k)!}$. NOTE: The order of selection does matter.

Example. A student president and vice president must be chosen from a class of 25 students. In how many ways can this selection be made?

Example. An entire deck of 52 cards is shuffled (put in random order). In how many ways can this be done?

Planet earth is composed of about 133,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 atoms (1.33 x 10^50). The number of ways we can shuffle a deck of cards is about 10 quadrillion times bigger than that, or: 80,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 (8×10^67).

Combinations

The number of ways that k items can be selected from a set of n elements is $nCk= {n \choose k}=\frac{n!}{(n-k)!k!}$. NOTE: The order of selection does not matter, only the items chosen.

Example. Six balls will be drawn randomly. For one dollar you buy a ticket with six blanks. You fill in the blanks with six different numbers between 1 and 36. You win $1,000,000 if you chose the same numbers that are drawn, regardless of order. What are your chances of winning?

Example. At a small company with 15 employees, a group of four is selected to represent the company at a conference. How many ways are there of selecting this group?

Group Work

Example A. A dice (die) is tossed four times in a row. How many different outcomes are possible?

Example B. You toss a coin, then roll a dice, and then draw a card from a 52-card deck.

  1. How many different outcomes are there?
  2. How many outcomes are there in which the dice lands on 3?
  3. How many outcomes are there in which the dice lands on an odd number?
  4. How many outcomes are there in which the dice lands on an odd number and the card is a King?

Example C. A password on a certain site must be five characters long, made from letters of the alphabet, and have at least one upper case letter. How many different passwords are there?

Example D. In the password example above, what if there must be a mix of upper and lower case letters?

Example D. How many even 5-digit numbers are there for which no
digit is 0, and the digit 6 appears exactly once? For instance, 55634 and
16118 are such numbers, but not 63304 (has a 0), nor 63364 (too many 6’s),
nor 55637 (not even).

Example E. How many 7-digit binary strings (0010100, 1101011, etc.) have an odd number of 1’s?

Resources on Combinatorics

  • Chapter 3: Counting in R. Hammack’s Book of Proof gives a good introduction to combinatorics, with lots of examples.