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.

- How many different outcomes are there?
- How many outcomes are there in which the dice lands on 3?
- How many outcomes are there in which the dice lands on an odd number?
- 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 and16118 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.

## 0 Comments

## 1 Pingback