Probability and Statistics

Counting Basics

Principles

There are two rules from Set Theory that we need before we start in earnest:

The Rule Of Sum:

The Rule Of Product:

Here is an example that uses both the Rule Of Product and the Rule Of Sum:

A certain state issues two types of license plates: Plates with 3 letters followed by 3 numbers and plates with 2 letters followed by 4 numbers. How many types of plates are there?

Type I (Rule of Product):

26 x 26 x 26 x 10 x 10 x 10 = 17,576,000

(there are 26 choices for the first letter, 26 for each of the next two letters, and 10 for each place of number)

Type II (Rule of Product):

26 x 26 x 10 x 10 x 10 x 10 = 6,760,000

Total number (Rule of Sum)

Type I + Type II = 24,336,000

So the total number of license plates possible is 24,336,000

There is another way to get this result, just using Rule Of Product. There are 26 + 10 ways to choose the third digit (it could be either a letter or a number).

Total (Rule Of Product):

26 x 26 x 36 x 10 x 10 x 10 = 24,336,000

Now, what if each digit had to be different? Then, instead of 26 choices for the second digit, we have only 25 choices. The new total is now found like this:

Type I (Rule of Product):

26 x 25 x 24 x 10 x 9 x 8 = 11,232,000

Type II (Rule of Product):

26 x 25 x 10 x 9 x 8 x 7 = 3,276,000

Total number (Rule of Sum)

Type I + Type II = 14,508,000

As expected, since the choices of numbers and letters is more restrictive, there are a few number of possible license plates than before.

Note that we cannot arrive at this result directly from the Rule Of Product, since we do not know if the third digit will be a letter or a number. If it is a number, then the fourth place has only 9 choices; if it is a letter, then the fourth place has 10. We need both the Rule Of Product and the Rule Of Sum to solve that problem, as shown above.

Order Matters, No Repetition

Next Question: From a class of 19 students, how many ways are there to arrange 3 of them (order matters) in a row?

Answer: 19 x 18 x 17 = 5814

Another way to think of this number is in the following way:

In general, the number of ways to arrange K objects from a set of size N is

An important special case: to arrange all N elements:

So the number of ways to arrange 19 students in a line is 19!=121,645,100,408,832,000

Aside:

Notice that this means 0! = 1. How do we know this? Consider this definition of factorials:

N! = N•(N-1)!

This definition means 1! = 1•0!=1, meaning that 0! = 1. What if we continue? 0! = 0 • (-1)! = 1

The only way this is possible is if . Continuing on... . This means that . From this pattern, we can see that approaching each number from the right, that

As an aside to this aside, if we approach the negative numbers from the left, then we must switch from positive infinity to negative infinity and vice-versa.

This is an introduction to the continuous version of the factorial, the Gamma function. Of course, being a continuous function, it is out of the realm of this class. Take your local calculus (or other advanced math) class for more details!

Word permutations

How many "words" can be formed from the letters in the word "book"?

Well, we can just list them out:

There are 12 possibilities. Note that since the two o's are the same that oobk would be the same as oobk. Now, how can we generate a general principle from this? Well, as since oobk is the same as oobk, one way to count them would be to list out all possibilities, then divide by two. In fact, this is exactly what we do:

4!/2! = 24/2 = 12.

What about the word "eerie"?

are all the same. If we listed them all out, with the e's labeled, we would have 5!=120 combinations of the letters. For each of these combinations, there will be a six-fold redundancy. That comes from there being 3! ways to arrange the e's. So, for "eerie", there should only be 5!/3! = 20 combinations (and, indeed, there are):

For the word, "committee", there are 9 letters, 3 of which have two-fold redundancy. The number of combinations, then, is 9!/(2! 2! 2!).

In general, we find that when we arrange K objects, where each has its own degeneracy, n_i, that the number of ways to arrange them is K!/(n₁! n₂! n₃! ... n_K!).

Circle permutations

How many ways are there to arrange 4 people in a circle? 3!=6

Number the people. Choose a chair for the first person: there is only one way to do this since the chairs have no special order. However, now that there is a reference point, there are 3! ways to choose the remaining chairs. Another way to think of it is that if the chairs ARE labeled, then there are 4! ways to arrange the people, but there is a four-fold redundancy in which way the circle is rotated, so the answer is 4!/4=3! In general, then, there are (n-1)! ways of arranging n objects in a circle.

Ring Permutations:

There are 5 charms a girl wants to put on her bracelet. If she wants to try every combination, how many times must she change the charms around? 4!/2=12. There are (n-1)! ways to arrange things in a circle, but then the bracelet may be flipped over to get a reflection of the pattern, cutting down on the possible combinations by a factor of two.

Order does not matter, No repetition

Definition: is the number of size-K subsets of an N-element set; i.e., it is the number of ways to select K different objects from a set of N objects, when order does not matter. We call this "N choose K".

Question: How do you select 3 students from a group of 19?

Answer:

For now, just this answer is fine, it is our definition.

But what is the mathematical formula for this?

Recall the question: how many ways are there to arrange 3 students from a group of 19?

Answer I:

Answer II: First choose 3 students, and then arrange them:

In general, we find that

Some special properties of :

By definition: The number of ways to choose zero elements from a size-N set.

By formula:

By definition: The number of ways to choose all N elements from a size-N set.

By formula:

By definition: The number of ways to choose one element from a size-N set.

By formula:

By definition: The number of ways to choose all but one element from a size-N set.

By formula:

Proof: In a class of N students, have K of them rise. There are thus N-K students left sitting. Therefore, if ever we choose K students, it is the same as choosing N-K students.

Finally, note that the formula for N choose K only applies when . If K<0 or K>N, then .

Word example: There is no way to choose 31 elements from a 20 element set. There is also no way to choose -3 elements from a 20 element set.

Formula example:

Counting Examples

Ten different paintings are able to be allocated to n different rooms so that each room has no more than one painting. How many ways are there to do this if a) n=20? b) n=7?

a) 20!/10! = 6.7044 x 10¹¹ (Make arbitrary list of paintings. Then the first room picked gets the first painting, &c., until all paintings have been allocated.)

b) 10!/3! = 604800 (Make arbitrary list of rooms. Then the first painting picked gets first room, &c., until all of the rooms have a painting.)

You can see that the trick is to take the objects of the larger number and distribute the objects with the smaller number into them.

What if the paintings are identical?

a) : (Of the 20 rooms, choose 10 to have a painting).

b) 1: (Every room gets a painting, and there is only one way to do that). You'll have paintings left over, but you're just doing what you were told!

Another Example:

How many ways are there to choose a student council of 10 students from a student body of 100, and then choose a president and vice-president?

How many ways are there to choose a president and vice-president, and then choose the remaining 8 members of the student council from that student body of 100?

Thought question: Why are these the same?

More Examples:

In how many ways can N girls and N boys be seated in a row of 2N chairs, if the two genders must alternate?

Answer: Label the chairs. There are N! ways of distributing the boys in the odd chairs, and N! ways of distributing the girls, so (N!)² ways total. Next, the boys could be in the even seats. So total there are 2(N!)² ways.

How many ways can you arrange 20 identical candles in a circle? 1

How many ways can you arrange 20 different candles in a circle? 19!

As you can see, although each counting problem uses the same basic tools, it seems like most of them have their own tricks. The key is to learn to how to think logically and how to start a problem.

Binomial Theorem, a Combinatorial Proof:

First, we'll look at the general case of the Binomial Theorem:

We could prove this using induction, but let's use a new type of proof: combinatorial proof. In a combinatorial proof, we ask a question, and then come up with two ways to answer. Those two answers, of course, must be equal!

Question: How many ways are there to distribute N distinct Pokemon to x girls and y boys (each boy or girl could have more than one Pokemon)?

Answer I: For each Pokemon, there are (x+y) choices as to whom the Pokemon will go. Therefore there are (x+y)^N ways to distribute them.

Answer II: If we know before-hand that boys will get K of the N Pokemon, then there are ways to distribute them. The describes which K of the N go to the boys. The y^K tells us that the K Pokemon each have y choices for owners. The x^N-K tells us that the remaining N-K Pokemon each have x choices for owners. Finally, K could be any number from 0 to N, so the total number of ways to distribute the N Pokemon is

.

Since Answer I = Answer II, we then arrive at what we wanted, which is .

Here's an important special case:

Proofs:

Algebraic: You can do it, but it's nasty.

Combinatorial:

Question: From a class of N students, how many ways are there to create a committee?

Answer I: The # of size-0 committees is

The # of size-1 committees is

. . . . . . . .

. . . . . . . .

. . . . . . . .

The # of size-N committees is

Hence the total number of committees is

Answer II: For each student, decide whether she is in the committee. There are two possible choices for each student, then: in or out. The total number of committees is then

2^N

Since Answer I = Answer II, we have shown that .

Another way to show this is to set x and y both equal to 1 in the general Binomial Theorem!

Poker Hands

Another fascinating use of counting is to calculate Poker Hand probabilities. A deck of cards consists of 4 suits (Hearts, Diamonds, Spades, and Clubs), where each suit has 13 ranks (2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace (aces can be high or low)). A typical, 5-card stud, poker game means that you have 5 cards in your hand. Since order does not matter and you cannot have repeat cards, the number of hands possible is

There are eight types of winning hands, but of course there is more than one way to obtain each of these hands. For instance, one type of winning hand is a flush. A flush means that you have all five cards in your hand from the same suit. The number of hands in which this happens is

The denotes picking one of the four suits possible and the denotes picking five cards from the thirteen cards in that suit. Below you will find a list of winning hands, listed in order of best hands to worst hands. The percentage shown is the percentage of hands with that combination. For instance, there are 5148 possible ways to get a flush, out of 2,598,960 possible hands, so you should get a flush 0.1981% of the time. However, we must lastly look at hands that overlap, such as Flushes and Straight-Flushes. See the list below for the details.

Royal Flush (10, J, Q, K, A of one suit):

There is only 1 way to do it in each suit, and there are 4 suits from which to choose.

Straight Flush (any 5 consecutive ranks of one suit):

There are 9 ways to choose the ranks (the lowest card can be any of {A, 2, 3, 4, 5, 6, 7, 8, 9} (note that a low card of 10 gives us a Royal Flush, which is a different hand)). There are 4 ways to choose the suit.

Four-of-a-Kind (four cards of the same rank, plus one more card):

There are 13 ways to choose the rank of the repeated card, and there are 48 ways to choose the other card.

Full House (three cards of one rank, two cards of another):

There are 13 ways to choose the first three cards. Then, we must choose 3 out of the 4 suits for those cards. There are 12 ways to choose the other two cards; finally, we must choose 2 out of suits for those cards.

Flush (all cards of the same suit):

There are 4 ways to choose the suit, and we must choose 5 of 13 cards in that suit. Then we must subtract out the possible Straight Flushes (36) and Royal Flushes (4), since these are different hands.

Straight (Five consecutive ranks, of any suits):

There are 10 ways to choose the first card of the five {A, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Then, there are 4 ways to choose the suit of each card. Finally, we must eliminate Straight Flushes (36) and Royal Flushes (4), since these are different hands.

Three-of-a-Kind (Three cards of the same rank, and two additional cards, neither of which can be of the same rank as each other (this would be a Full House) or the same rank as the first three cards (causing a Four-of-a-Kind)):

There are 13 ways to choose the triplet rank. We then must choose 3 of the 4 suits for these three cards. For the remaining two cards, we choose 2 of the 12 remaining ranks, and each of those cards has four possible suits.

Two Pairs (Two sets of two cards of the same rank, plus one more card):

First we must choose 2 of the 13 ranks for the pairs. Note that this is not 13 ways to choose the first rank and 12 ways to choose the second rank, as this would imply an order to the pairs. For each of the pairs, we must choose 2 of the four suits for the pair. Finally, if we exclude those two ranks, that leaves us with 44 cards from which to choose the final card.

One Pair (One set of two cards of the same rank, plus three other cards, picked to avoid all of the other hands, e.g. three-of-a-kinds and full houses):

First we pick one rank out of the 13 for the pair. The other three cards must all be of different ranks, so we must choose 3 of the 12 remaining ranks. Finally, each of those cards has 4 choices of suit.

Garbage (losing) Hand (none of previous hands):

Just the total number of hands, minus each possible winning hand.

There are, of course, multiple ways of solving each of these problems. For instance, we could have calculated the Three-of-a-Kind picking the rank, choosing the 3 of 4 suits, then picking the last two cards from the 48 remaining cards of different rank. Doing it this way, we could have some Full Houses, so we subtract out the Full Houses and get the same answer as above!

Here are some more interesting derivations regarding poker hands:

At least one ace:

Wrong Way to Calculate: Choose the first card to be an ace, then choose the rest(double counting the cases when we choose two aces):

Right Way to Calculate: All of the cases added together:

Another Right Way: All possible hands minus hands with no aces:

No Pairs:

Pick 5 different ranks from the 13, and then there are 4 different suits from which to choose for each card.

Garbage Hand (revisited):

Garbage Hand = No Pairs (eliminates pair, two pairs, three-of-a-kind, full-house, and four-of-a-kind) minus Straights and Flushes (eliminates straight, flush, straight flush, and royal flush).

Back to Dr. Nandor's Discrete Math Page

Back to the Wellington Home Page