Lesson 3: Counting Techniques

Lesson 3: Counting Techniques

Overview

abacus

In the previous lesson, we learned that the classical approach to assigning probability to an event involves determining the number of elements in the event and the sample space. There are many situations in which it would be too difficult and/or too tedious to list all of the possible outcomes in a sample space. In this lesson, we will learn various ways of counting the number of elements in a sample space without actually having to identify the specific outcomes. The specific counting techniques we will explore include the multiplication rule, permutations and combinations.

Objectives

Upon completion of this lesson, you should be able to:

  • Understand and be able to apply the multiplication principle.
  • Understand how to count objects when the objects are sampled with replacement.
  • Understand how to count objects when the objects are sampled without replacement.
  • Understand and be able to use the permutation formula to count the number of ordered arrangements of \(n\) objects taken \(n\) at a time.
  • Understand and be able to use the permutation formula to count the number of ordered arrangements of \(n\) objects taken \(r\) at a time.
  • Understand and be able to use the combination formula to count the number of unordered subsets of \(r\) objects taken from \(n\) objects.
  • Understand and be able to use the combination formula to count the number of distinguishable permutations of \(n\) objects, in which \(r\) are of the objects are of one type and \(n-r\) are of another type.
  • Understand and be able to count the number of distinguishable permutations of \(n\) objects, when the objects are of more than two types.
  • Learn to apply the techniques learned in the lesson to new counting problems.

3.1 - The Multiplication Principle

3.1 - The Multiplication Principle

Example 3-1

Dr. Roll Toss wants to calculate the probability that he will get:

a 6 6 on a die and a head penny

when he rolls a fair six-sided die and tosses a fair coin. Because his die is fair, he has an equally likely chance of getting any of the numbers 1, 2, 3, 4, 5, or 6. Similarly, because his coin is fair, he has an equally likely chance of getting a head or a tail. Therefore, he can use the classical approach of assigning probability to his event of interest. The probability of his event \(A\), say, is:

\(P(A)=\dfrac{N(A)}{N(S)}\)

where \(N(A)\) is the number of ways that he can get a 6 and a head, and \(N(\mathbf{S})\) is the number of all of the possible outcomes of his rolls and tosses. There is of course only one possible way of getting a 6 and a head. Therefore, \(N(A)\) is simply 1. To determine \(N(\mathbf{S})\), he could enumerate all of the possible outcomes:

\(\mathbf{S}=\{1H, 1T, 2H, 2T, \ldots\}\)

and then count them up. Alternatively, he could use what is called the Multiplication Principle and recognize that for each of the 2 possible outcomes of a tossing a coin, there are exactly 6 possible outcomes of rolling a die. Therefore, there must be \(6(2)=12\) possible outcomes in the sample space. The following animation illustrates the Multiplication Principle in action for Dr. Roll Toss' problem:

In summary, then the probability of interest here is \(P(A)=\frac{1}{12}=0.083\). Of course, this example in itself is not particularly motivating. The main takeaway point should be that the Multiplication Principle exists and can be extremely useful for determining the number of outcomes of an experiment (or procedure), especially in situations when enumerating all of the possible outcomes of an experiment (procedure) is time- and/or cost-prohibitive. Let's generalize the principle.

Multiplication Principle

If there are:

\(n_1\) outcomes of a random experiment \(E_1\)
\(n_2\) outcomes of a random experiment \(E_2\)
... and ...
\(n_m\) outcomes of a random experiment \(E_m\)
then there are \(n_1\times n_2\times\ldots\times n_m\) outcomes of the composite experiment \(E_1E_2\ldots E_m\)

The hardest part of using the Multiplication Principle is determining, \(n_i\), the number of possible outcomes for each random experiment (procedure) performed. You'll want to pay particular attention to:

  • whether replication is permitted
  • whether other restrictions exist

Let's take a look at another example.

Example 3-2

How many possible license plates could be stamped if each license plate were required to have exactly 3 letters and 4 numbers?

license plate

Solution

Imagine trying to solve this problem by enumerating each of the possible license plates: AAA1111, AAA1112, AAA1113, ... you get the idea! The Multiplication Principle makes the solution straightforward. If you think of stamping the license plate as filling the first three positions with one of 26 possible letters and the last four positions with one of 10 possible digits:

 

Enumeration of letters and numbers
A A A   0 0 0 0
B B B   1 1 1 1
C C C   2 2 2 2
 
  9 9 9 9
Z Z Z  

 

the Multiplication Principle tells us that there are:

26 x 26 x 26 x 10 x 10 x 10 x 10
= 175,650,000

 

Again, that is:

\((26\times 26\times 26)\times (10\times 10\times 10\times 10)\)

or 175,760,000 possible license plates. That's a lot of license plates! If you're hoping for one particular license plate, your chance (1 divided by 175,760,000) of getting it are practically nil.

Now, how many possible license plates could be stamped if each license plate were required to have 3 unique letters and 4 unique numbers?

Solution

In this case, the key is to recognize that the replication of numbers is not permitted. There are still 26 possibilities for the first letter position. Suppose the first letter is an A. Then, since the second letter can't also be an A, there are only 25 possibilities for the second letter position. Now suppose the second letter is, oh let's say, a B. Then, since the third letter can't be either an A or a B, there are only 24 possibilities for the third letter position. Similar logic applies for the number positions. There are 10 possibilities for the first number position. Then, supposing the first number is a zero, there are only 9 possibilities for the second number position, because the second number can't also be a zero. Similarly, supposing the second number is a one, there are only 8 possibilities for the third number position. And, supposing the third number is a two, there are 7 possibilities for the last number position:

A       0      
B B     1 1    
C C C   2 2 2  
  3
 
  9 9 9 9
Z Z Z  

Therefore, the Multiplication Principle tells us that in this case there are 78,624,000 possible license plates:

26 x 25 x 24 x 10 x 9 x 8 x 7
= 78,624,000

That's still a lot of license plates!

Example 3-3

Let's take a look at one last example. How many subsets are possible out of a set of 10 elements?

Solution

Let's suppose that the ten elements are the letters A through J:

A, B , C, D, E, F, G, H, I, J

Well, there are 10 subsets consisting of only one element: {A}, {B}, ..., and {J}. If you're patient, you can determine that there are 45 subsets consisting of two elements: {AB}, {AC}, {AD}, ..., {IJ}. If you're nuts and don't mind tedious work, you can determine... oh, never mind! Let's use the Multiplication Principle to tackle this problem a different way. Rather than laboriously working through and counting all of the possible subsets, we could think of each element as something that could either get chosen or not get chosen to be in a subset. That is, A is either chosen or not... that's two possibilities. B is either chosen or not... that's two possibilities. C is either chosen or not... that's two possibilities. And so on. Thinking of the problem in this way, the Multiplication Principle then readily tells us that there are:

\(2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2 \)

or \(2^{10}=1024\) possible subsets. I personally would not have wanted to solve this problem by having to enumerate and count each of the possible subsets. Incidentally, we'll see many more problems similar to this one here when we investigate the binomial distribution later in the course.


3.2 - Permutations

3.2 - Permutations

Example 3-4

How many ways can four people fill four executive positions?

Answer

For the sake of concreteness, let's name the four people Tom, Rick, Harry, and Mary, and the four executive positions President, Vice President, Treasurer and Secretary. I think you'll agree that the Multiplication Principle yields a straightforward solution to this problem. If we fill the President position first, there are 4 possible people (Tom, Rick, Harry, and Mary). Let's suppose Mary is named the President. Then, since Mary can't fill more than one position at a time, when we fill the Vice President position, there are only 3 possible people (Tom, Rick, and Harry). If Tom is named the Vice President, when we fill the Treasurer position, there are only 2 possible people (Rick and Harry). Finally, if Rick is named Treasurer, when we fill the Secretary position, there is only 1 possible person (Harry). Putting all of this together, the Multiplication Principle tells us that there are:

\(4\times 3\times 2\times 1\)

or 24 possible ways to fill the four positions.

Alright, alright now... enough of these kinds of examples, eh?! The main point of this example is not to see yet another application of the Multiplication Principle, but rather to introduce the counting of the number of permutations as a generalization of the Multiplication Principle.

A Generalization of the Multiplication Principle

Suppose there are \(n\) positions to be filled with \(n\) different objects, in which there are:

  • \(n\) choices for the 1st position
  • \(n-1\) choices for the 2nd position
  • \(n-2\) choices for the 3rd position
  • ... and ...
  • 1 choice for the last position

The Multiplication Principle tells us there are then in general:

\(n\times (n-1)\times (n-2)\times \ldots \times 1=n!\)

ways of filling the \(n\) positions. The symbol \(n!\) is read as "\(n\) -factorial," and by definition 0! equals 1.

Permutation of \(n\) objects
an ordered arrangement of the \(n\) objects

We often call such a permutation a “permutation of \(n\) objects taken \(n\) at a time,” and denote it as \(_nP_n\). That is:

\(_nP_n=n\times (n-1)\times (n-2) \times \ldots \times 1=n!\)

Not that it really matters in this situation (since they are the same), but the first subscripted \(n\) represents the number of objects you are wanting to arrange, while the second subscripted \(n\) represents the number of positions you have for the objects to fill.

Example 3-5

plastic toy soldiers

The draft lottery of 1969 for military service ranked all 366 days (Jan 1, Jan 2, ..., Feb 29, ..., Dec 31) of the year. The men who were eligible for service whose birthday was selected first were the first to be drafted. Those whose birthday was selected second were the second to be drafted. And so on. How many possible ways can the 366 days be ranked?

Answer

Well, we have 366 objects (days) and 366 positions (1st spot, 2nd spot, ... , 366th spot) to arrange them. Therefore, there are 366! ("366 factorial" ) ways of ranking the 366 possible birthdays of the eligible men.

What is the probability that your birthday would be ranked first?

The answer, which is 1/366 = 0.0027, can be determined in (at least) two ways.

The simplest way is to recognize that there is only one birthday (yours!) in the event of interest, and that there are 366 birthdays in the sample space. Therefore, the classical approach to assigning probability tells us the probability is 1 divided by 366.

A second way is to recognize that there are 366! ways of ranking the 366 birthdays, and that there are 365! ways of ranking the 366 birthdays to ensure that your birthday is ranked first. Again, the classical approach to assigning probability tells us the probability is 365! divided by 366!, which after simplification is 1/366.

Example 3-6

seven books on a bookshelf

In how many ways can 7 different books be arranged on a shelf?

Answer

We could use the Multiplication Principle to solve this problem. We have seven positions that we can fill with seven books. There are 7 possible books for the first position, 6 possible books for the second position, five possible books for the third position, and so on. The Multiplication Principle tells us therefore that the books can be arranged in:

\(7\times 6\times 5\times 4\times 3\times 2\times 1\)

or 5,040 ways. Alternatively, we can use the simple rule for counting permutations. That is, the number of ways to arrange 7 distinct objects is simply \(_7P_7=7!=5040\).

Example 3-7

With 6 names in a bag, randomly select a name. How many ways can the 6 names be assigned to 6 job assignments? If we assume that each person can only be assigned to one job, then we must select (or sample) the names without replacement. That is, once we select a name, it is set aside and not returned to the bag.

Sampling without replacement
occurs when an object is not replaced after it has been selected

Answer

If we sample without replacement, the problem reduces to simply determining the number of ways the 6 names can be arranged. We have 6 objects taken 6 at a time, and hence the number of ways is 6! = 720 possible job assignments. In this case, each person is assigned to one and only one job.

What if the 6 names were sampled with replacement? That is, once we select a name, it is returned to the bag.

Sampling with replacement
occurs when an object is selected and then replaced before the next object has been selected

Answer

If we sample with replacement, we have 6 choices for each of the 6 jobs. Applying the Multiplication Principle, there are:

\(6\times 6\times 6\times 6\times 6\times 6=46656\)

possible job assignments. In this case, each person is allowed to perform more than one job. There's even the possibility that one (rather unlucky) person gets assigned to all six jobs!

The take-home message from this example is that you'll always want to ask yourself whether or not the problem involves sampling with or without replacement. Incidentally, it's not all that different from asking yourself whether or not replication is allowed. Right?

Example 3-8

three chairs

Okay, let's throw a (small) wrench into our work. How many ways can 4 people fill 3 chairs?

Answer

Again, for the sake of concreteness, let's name the four people Tom, Rick, Harry, and Mary and the chairs Left, Middle, and Right. If we fill the Left chair first, there are 4 possible people (Tom, Rick, Harry, and Mary). Let's suppose Tom is selected for the Left chair. Then, since Tom can't sit in more than one chair at a time when we fill the Middle chair, there are only 3 possible people (Rick, Harry, and Mary). If Rick is selected for the Middle chair, when we fill the Right chair, there are only 2 possible people (Harry and Mary). Putting all of this together, the Multiplication Principle tells us that there are:

\(4\times 3\times 2\)

or 24 possible ways to fill the three chairs.

Okay, okay! The main distinction between this example and the first example on this page is that the first example involves arranging all 4 people, whereas this example involves leaving one person out and arranging just 3 of the 4 people. This example allows us to introduce another generalization of the Multiplication Principle, namely the counting of the number of permutations of \(n\) objects taken \(r\) at a time, where \(r\le n\).

Another Generalization of the Multiplication Principle

Suppose there are \(r\) positions to be filled with \(n\) different objects, in which there are:

  • \(n\) choices for the 1st position
  • \(n-1\) choices for the 2nd position
  • \(n-2\) choices for the 3rd position
  • ... and ...
  • \(n-(r-1)\) choices for the last position

The Multiplication Principle tells us there are in general:

\(n\times (n-1)\times (n-2)\times \ldots \times [n-(r-1)]\)

ways of filling the \(r\) positions. We can easily show that, in general, this quantity equals:

\(\dfrac{n!}{(n-r)!}\)

Here's how it works:

And, formally:

Permutation of \(n\) objects taken \(r\) at a time
ordered arrangement of \(n\) different objects in \(r\) positions. The number of such permutations is:

\(_nP_r=\dfrac{n!}{(n-r)!}\)

The subscripted \(n\) represents the number of objects you are wanting to arrange, while the subscripted \(r\) represents the number of positions you have for the objects to fill.

Example 3-9

An artist has 9 paintings. How many ways can he hang 4 paintings side-by-side on a gallery wall?


3.3 - Combinations

3.3 - Combinations

Example 3-10

Maria has three tickets for a concert. She'd like to use one of the tickets herself. She could then offer the other two tickets to any of four friends (Ann, Beth, Chris, Dave). How many ways can 2 people be selected from 4 to go to a concert?

Hmmm... could we solve this problem without creating a list of all of the possible outcomes? That is, is there a formula that we could just pull out of our toolbox when faced with this type of problem? Well, we want to find \(C\), the number of unordered subsets of size \(r\) that can be selected from a set of \(n\) different objects.

We can determine a general formula for \(C\) by noting that there are two ways of finding the number of ordered subsets (note that that says ordered, not unordered):

  1. Method #1

    We learned how to count the number of ordered subsets on the last page. It is just \(_nP_r\), the number of permutations of \(n\) objects taken \(r\) at a time.

  2. Method #2

    Alternatively, we could take each of the \(C\) unordered subsets of size \(r\) and permute each of them to get the number of ordered subsets. Because each of the subsets contains \(r\) objects, there are \(r!\) ways of permuting them. Applying the Multiplication Principle then, there must be \(C\times r!\) ordered subsets of size \(r\) taken from \(n\) objects.

Because we've just used two different methods to find the same thing, they better equal each other. That is, it must be true that:

\(_nP_r=C\times r!\)

Ahhh, we now have an equation that involves \(C\), the quantity for which we are trying to find a formula. It's straightforward algebra at this point. Let's take a look.

Here's a formal definition.

combination of \(n\) objects taken \(r\) at a time

number of unordered subsets is:

\(_nC_r=\dbinom{n}{r}=\dfrac{n!}{r!(n-r)!}\)

We say “\(n\) choose \(r\).”

The \(r\) represents the number of objects you'd like to select (without replacement and without regard to order) from the \(n\) objects you have.

Example 3-11

Twelve (12) patients are available for use in a research study. Only seven (7) should be assigned to receive the study treatment. How many different subsets of seven patients can be selected?

Answer

The formula for the number of combinations of 12 objects taken 7 at a time tells us that there are:

\(\dbinom{12}{7}=\dfrac{12!}{7!(12-7)!}=792\)

different possible subsets of 7 patients that can be selected.

Example 3-12

Let's use a standard deck of cards containing 13 face values (Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, and King) and 4 different suits (Clubs, Diamonds, Hearts, and Spades) to play five-card poker. If you are dealt five cards, what is the probability of getting a "full-house" hand containing three kings and two aces (KKKAA)?

If you are dealt five cards, what is the probability of getting any full-house hand?

An Aside on Binomial Coefficients

The numbers:

\(\dbinom{n}{r}\)

are frequently called binomial coefficients, because they arise in the expansion of a binomial. Let's recall the expansion of \((a+b)^2\) and \((a+b)^3\).

Now, you might recall that, in general, the binomial expansion of \((a+b)^n\) is:

\((a+b)^n=\sum\limits_{r=0}^n \dbinom{n}{r} b^r a^{n-r}\)

Let's see if we can convince ourselves as to why this is true.

Now, you might want to entertain yourself by verifying that the formula given for the binomial expansion does indeed work for \(n=2\) and \(n=3\).


3.4 - Distinguishable Permutations

3.4 - Distinguishable Permutations

Example 3-13

Suppose we toss a gold dollar coin 8 times. What is the probability that the sequence of 8 tosses yields 3 heads (H) and 5 tails (T)?

Answer

Two such sequences, for example, might look like this:

H H H T T T T T or this H T H T H T T T

Assuming the coin is fair, and thus that the outcomes of tossing either a head or tail are equally likely, we can use the classical approach to assigning the probability. The Multiplication Principle tells us that there are:

\(2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\)

or 256 possible outcomes in the sample space of 8 tosses. (Can you imagine enumerating all 256 possible outcomes?) Now, when counting the number of sequences of 3 heads and 5 tosses, we need to recognize that we are dealing with arrangements or permutations of the letters, since order matters, but in this case not all of the objects are distinct. We can think of choosing (note that choice of word!) \(r=3\) positions for the heads (H) out of the \(n=8\) possible tosses. That would, of course, leave then \(n-r=8-3=5\) positions for the tails (T). Using the formula for a combination of \(n\) objects taken \(r\) at a time, there are therefore:

\(\dbinom{8}{3}=\dfrac{8!}{3!5!}=56\)

distinguishable permutations of 3 heads (H) and 5 tails (T). The probability of tossing 3 heads (H) and 5 tails (T) is thus \(\dfrac{56}{256}=0.22\).

Let's formalize our work here!

Distinguishable permutations of \(n\) objects
Given \(n\) objects with:
  • \(r\) of one type, and
  • \(n-r\) of another type

there are:

\(_nC_r=\binom{n}{r}=\dfrac{n!}{r!(n-r)!}\)

Let's take a look at another example that involves counting distinguishable permutations of objects of two types.

Example 3-14

the word Mississippi on the side of a building

How many ordered arrangements are there of the letters in MISSISSIPPI?

Answer

Well, there are 11 letters in total:

1 M, 4 I, 4 S and 2 P

We are again dealing with arranging objects that are not all distinguishable. We couldn't distinguish among the 4 I's in any one arrangement, for example. In this case, however, we don't have just two, but rather four, different types of objects. In trying to solve this problem, let's see if we can come up with some kind of a general formula for the number of distinguishable permutations of n objects when there are more than two different types of objects.

Let's formalize our work.

number of distinguishable permutations of \(n\) objects
  • \(n_1\) are of one type
  • \(n_2\) are of a second type
  • ... and ...
  • \(n_k\) are of the last type

and \(n=n_1+n_2+\ldots +n_k\)is given by:

\(\dbinom{n}{n_1n_2n_3\ldots n_k}=\dfrac{n!}{n_1!n_2!n_3! \ldots n_k!}\)

Let's take a look at a few more examples involving distinguishable permutations of objects of more than two types.

Example 3-15

How many ordered arrangements are there of the letters in the word PHILIPPINES?

Answer

The number of ordered arrangements of the letters in the word PHILIPPINES is:

\(\dfrac{11!}{3!1!3!1!1!1!1!}=1,108,800\)

Example 3-16

group of pigs

Fifteen (15) pigs are available to use in a study to compare three (3) different diets. Each of the diets (let's say, A, B, C) is to be used on five randomly selected pigs. In how many ways can the diets be assigned to the pigs?

Answer

Well, one possible assignment of the diets to the pigs would be for the first five pigs to be placed on diet A, the second five pigs to be placed on diet B, and the last 5 pigs to be placed on diet C. That is:

A A A A A B B B B B C C C C C

Another possible assignment might look like this:

A B C A B C A B C A B C A B C

Upon studying these possible assignments, we see that we need to count the number of distinguishable permutations of 15 objects of which 5 are of type A, 5 are of type B, and 5 are of type C. Using the formula, we see that there are:

\(\dfrac{15!}{5!5!5!}=756756\)

ways in which 15 pigs can be assigned to the 3 diets. That's a lot of ways!


3.5 - More Examples

3.5 - More Examples

We've learned a number of different counting techniques in this lesson. Now, we'll get some practice using the various techniques. As we do so, you might want to keep these helpful (summary) hints in mind:

  • When you begin to solve a counting problem, it's always, always, always a good idea to create a specific example (or two or three...) of the things you are trying to count.
  • If there are \(m\) ways of doing one thing, and \(n\) ways of doing another thing, then the Multiplication Principle tells us there are \(m\times n\) ways of doing both things.
  • If you want to place \(n\) things in \(n\) positions, and you care about order, you can do it in \(n!\) ways. (Doing so is called permuting \(n\) items \(n\) at a time.)
  • If you want to place \(n\) things in \(r\) positions, and you care about order, you can do it in \(\dfrac{n!}{(n-r)!}\) ways. (Doing so is called permuting \(n\) items \(r\) at a time.)
  • If you have \(m\) items of one kind, \(n\) items of another kind, and \(o\) items of a third kind, then there are \(\dfrac{(m+n+o)!}{m!n!o!}\) ways of arranging the items. (Doing so is called counting the number of distinguishable permutations.)
  • If you have \(m\) items of one kind and \(n-m\) items of another kind, then there are \(\dfrac{n!}{m!(n-m)!}\) ways of choosing the \(m\) items without replacement and without regard to order. (Doing so is called counting the number of combinations, and we say "\(n\) choose \(m\)".)

Let's take a look at some examples now!

Example 3-17

flagsA ship's captain sends signals by arranging 4 orange and 3 blue flags on a vertical pole. How many different signals could the ship's captain possibly send?

Answer

If the flags were numbered 1, 2, 3, 4, 5, 6 and 7, then the orange flags and blue flags would be distinguishable among themselves. In that case, the ship's captain could send any of 7! = 5,040 possible signals.

The flags are not numbered, however. That is, the four orange flags are not distinguishable among themselves, and the 3 blue flags are not distinguishable among themselves. We need to count the number of distinguishable permutations when the two colors are the only features that make the flags distinguishable. The ship's captain has 4 orange flags and 3 blue flags. Using the formula for the number of distinguishable permutations, the ship's captain could send any of:

\(\dfrac{7!}{4!3!}=\dbinom{7}{4}\)

or 35 possible signals.

By the way, recall that the 4! in the denominator reduces the number of 7! arrangements by the number of ways in which the four orange flags could have been arranged had they been distinguishable among themselves (if they were labeled 1, 2, 3, 4, for example). Likewise, the 3! in the denominator reduces the number of 7! arrangements by the number of ways in which the three blue flags could have been arranged had they been distinguishable among themselves (if they were labeled 1, 2, 3, for example).

Example 3-18

Now the ship's captain sends signals by arranging 3 red, 4 orange and 2 blue flags on a vertical pole. How many different flagssignals could the ship's captain possibly send?

Answer

Again, if the flags were numbered 1, 2, 3, 4, 5, 6, 7, 8, and 9, then the red, yellow, and blue flags would be distinguishable among themselves. In that case, the ship's captain could send any of \(9!=362,880\) possible signals.

The flags are not numbered, however. That is, the three red flags are not distinguishable among themselves, the four orange flags are not distinguishable among themselves, and the 2 blue flags are not distinguishable among themselves. We need to count the number of distinguishable permutations when the three colors are the only features that make the flags distinguishable. Again, using the formula for the number of distinguishable permutations, the ship's captain could send any of:

\(\dfrac{9!}{4!3!2!}=\dbinom{9}{4\ 3\ 2}\)

or 1260 possible signals.

Example 3-19

How many four-letter codes are possible?

Answer

One example of a four-letter code is XSST. Another example is RLPR. If we were to try to enumerate all of the possible four-letter codes, we'd have to place any of 26 letters in the first position, any of 26 letters in the second position, any of 26 letters in the third position, and any of 26 letters in the fourth position:

___ , ___ , ___ , ___

Yikes, that sounds like a lot of work! Fortunately, the Multiplication Principle tells us to simply multiply those 26's together. That is, there are:

\(26 \times 26 \times 26\times 26=456,976\)

possible four-letter codes.

Now, let's add a restriction. How many four-letter codes are possible if no letter may be repeated?

Answer

One example of a four-letter code, with no letters repeated, is XSGT. Another such example is RLPW. If we were to try to enumerate all of the possible four-letter codes with no letters repeated, we'd have to place any of 26 letters in the first position. Then, since one of the letters would be chosen for the first position, we'd have to place any of 25 letters in the second position. Then, since two of the letters would be chosen for the first and second positions, we'd have to place any of 24 letters in the third position. Finally, since three of the letters would be chosen for the first, second, and third positions, we'd have to place any of 23 letters in the fourth position:

___ , ___ , ___ , ___

Again, the Multiplication Principle tells us to simply multiply the numbers together. When we don't allow repetition of letters, there are:

\(26\times 25\times 24\times 23=358, 800\)

possible four-letter codes. By the way, we could alternatively recognize here that we are permuting 26 letters, 4 at a time, and then use the formula for a permutation of 26 objects (letters) taken 4 at a time:

\(_{26}P_4=\dfrac{26!}{22!}=26\times 25 \times 24 \times 23\)

Either way, we still end up counting 358,800 possible four-letter codes.

Now, let's add yet another restriction. How many four-letter codes are possible if no repetition is allowed and order is not important?

Answer

Again, one example of a four-letter code, with no letters repeated, is XSGT. In this case, however, we would not distinguish the code XSGT from the code TGSX. That is, all we care about is counting how many ways we can choose any four letters from the 26 possible letters in the alphabet. So, we sample without replacement (to ensure no letters are repeated) and we don't care about the order in which the letters are chosen. It sounds like the formula for a combination will do the trick then. It tells us that there are:

\(_{26}C_4=\dfrac{26!}{22!4!}\)

or 14,950 four-letter codes when order doesn't matter and repetition is not permitted.

By the way, the formula here differs from the formula in the previous example by having a \(4!\) in the denominator. The \(4!\) appears in the denominator because we added the restriction that the order of the letters doesn't matter. Therefore, we want to divide by the number of ways we over-counted, that is, by the \(4!\) ways of ordering the four letters. That is, the \(4!\) in the denominator reduces the number of \(\dfrac{26!}{22!}\) arrangements counted in the previous example by the number of ways in which the four letters could have been ordered.

If you hadn't noticed already, you might want to take note now that the solutions to each of the three previous examples started out by highlighting a specific example (or two) of the kinds of four-letter codes we were trying to count. This is a really good practice to follow when trying to count objects. After all, it is awfully hard to count correctly if you don't know what it is you are counting!

Example 3-20

In how many ways can 4 heterosexual married couples (1 male, 1 female) attending a concert be seated in a row of 8 seats if there are no restrictions as to where the 8 can sit?

Answer

Here are the eight seats:

seats

If we arbitrarily name the people A, B, C, D, E, F, G, and H, then one possible seating arrangement is ABCDEFGH. Another is DGHCAEBF. These examples suggest that we have to place 8 people into 8 seats without repetition. That is, one person can't occupy two seats!

Well, we can place any of the 8 people in the first seat. Then, since one of the people would be chosen for the first seat, we'd have to place any of the remaining 7 people in the second seat. Then, since two of the people would be chosen for the first and second seats, we'd have to place any of the remaining 6 people in the third seat. And so on ... until we have just one person remaining to occupy the last seat. The Multiplication Principle tells us to multiply the numbers together. That is, there are:

\(8\times 7\times 6\times 5\times 4\times 3\times 2\times 1=40, 320\)

possible seating arrangements. Of course, we alternatively could have recognized that we are trying to count the number of permutations of 8 objects taken 8 at a time. The permutation formula would tell us similarly that there are \(8! = 40,320\) possible seating arrangements.

Now, let's add a restriction. In how many ways can 4 married couples attending a concert be seated in a row of 8 seats if each married couple is seated together?

Answer

Here are the eight seats shown as four paired seats:

seats

If we arbitrarily name the people A1, A2, B1, B2, C1, C2, D1, and D2, then one possible seating arrangement is B2, B1, A1, A2, C2, C1, D1, D2. Another such assignment might be B1, B2, A2, A1, C1, C2, D1, D2. These two examples illustrate that counting here is a two-step process. First, we have to figure out how many ways the couples A, B, C, and D can be arranged. Permuting 4 items (couples) 4 at a time... there are 4! ways. Then, we have to arrange the partners within each couple. Well, couple A can be arranged 2! ways. We can even list the ways... they can sit either as A1, A2 or as A2, A1. Likewise, couple B can be arranged in 2! ways, as can couples C and D. The Multiplication Principle then tells us to multiply all the numbers together. Four married couples can be seated in a row of 8 seats in:

\(4!\times 2!\times 2!\times 2!\times 2!=384\) ways

if each married couple is seated together.

Are you enjoying this?! Now, let's add a different restriction. In how many ways can 4 married couples attending a concert be seated in a row of 8 seats if members of the same sex are all seated next to each other?

Answer

Here are the eight seats, shown as two sets of fours seats:

seats

If we arbitrarily name the people M1, M2, M3, M4 and F1, F2, F3, F4, then one possible seating arrangement is M1, M2, M4, M3, F2, F1, F3, F4. Another such assignment might be F1, F2, F4, F3, M2, M1, M4, M3. Again, these two examples illustrate that counting here is a two-step process. First, we have to figure out how many ways the genders M and F can be arranged. There are, of course, 2 ways... the males in the seats on the left and females in the seats on the right or the females in the seats on the left and the males in the seats on the right. Then, we have to arrange the people within each gender. Let's take the females first. Permuting 4 items (females) 4 at a time... there are \(4!\) ways. Likewise, there are \(4!\) ways of arranging the males within their 4 seats. The Multiplication Principle then tells us to multiply all the numbers together. Four married couples can be seated in a row of 8 seats in:

\(4!\times 4!\times 2=1,152\) ways

if the members of the same sex are seated next to each other.

You might want to note again that the solutions to each of the three previous examples started out by highlighting a specific example (or two) of the kinds of seating arrangements we were trying to count. Doing so really does help get you started in the right direction!

Example 3-21

How many ways are there to choose non-negative integers \(a, b, c, d, \text{ and }e\), such that the non-negative integers add up to 6, that is:

\(a+b+c+d+e=6\)

Answer

This is definitely a counting problem where you'll want to start by looking at a few examples first! One such example is:

\(1+2+1+0+2=6\)

where \(a = 1,\; b = 2,\; c = 1,\; d = 0,\text{ and }e = 3\). Another example is:

\(1+0+1+4+0=6\)

where \(a = 1,\; b = 0,\; c = 1,\; d = 4,\text{ and }e = 0\). And one last example is:

\(0 + 0 + 0 + 0 + 6 = 6\)

where \(a = 0,\; b = 0,\; c = 0, \;d = 0,\text{ and }e = 6\). So, what have we learned from these examples? Well, one thing becomes clear, if it wasn't already, is that \(a, b, c, d,\text{ and }e\) must each be an integer between 0 and 6.

Now, to advance our solution, we'll use what is called the "stars-and-bars" method. Because the sum that we are trying to obtain is 6, we'll divvy 6 stars into 5 bins called \(a, b, c, d, \text{ and }e\). If we arrange the 6 stars in a row, we can use 4 bars to represent the bins' walls. Here's what the stars-and-bars would look like for our first example in which \(1 + 2 + 1 + 0 + 2 = 6\):

1 2 1 0 2 =6

 

The first bin, \(a\), has 1 star; the second bin, \(b\), has 2 stars; the third bin, \(c\), has 1 star; the fourth bin, \(d\), has 0 stars; and the fifth bin, \(e\), has 2 stars. Now, here's what the stars-and-bars would look like for our second example in which \(1 + 0 + 1 + 4 + 0 = 6\):

1 1 4 0 0 =6

 

Notice that two bars adjacent either to each other or a bar at the end of the row of the stars implies that that bin has 0 stars in it. Here's what the stars-and-bars would look like for our last example in which \(0 + 0 + 0 + 0 + 6 = 6\):

0 6 0 0 0 =6

Here, the first bin, \(a\), has 0 stars; the second bin, \(b\), has 0 stars; the third bin, \(c\), has 0 stars; the fourth bin, \(d\), has 0 stars; and the fifth bin, \(e\), has 6 stars. All we've done so far is look at examples! By doing so though, perhaps we are now ready to make the jump to see that enumerating all of the possible ways of getting 5 non-negative integers to sum to 6 reduces to counting the number of distinguishable permutations of 10 items... of which 4 items are bars and 6 items are stars. That is, there are:

\(\dfrac{10!}{6!4!}=210\) ways

to choose non-negative integers \(a, b, c, d, \text{ and }e\), such that the non-negative integers add up to 6.

Do you get it? Try this next one out to test yourself. How many ways are there to choose non-negative integers \(a\) and \(b\)such that the non-negative integers add up to 5, that is:

\(a + b = 5\)

One such example is \(1 + 4 = 5\). Its stars-and-bars graphic would look like this:

1 4 =5

 

The stars-and-bars graphic for \(2 + 3 = 5\) would look like this:

2 3 =5

 

In this case, we have to count the number of distinguishable permutations of 6 items... of which 1 item is a bar and 5 items are stars. There are thus:

\(\dfrac{6!}{5!1!}=6\) ways

to choose non-negative integers \(a\) and \(b\) such that the non-negative integers add up to 5.

Are you ready for another one? How many ways can you specify 89 non-negative integers such that the non-negative integers add up to 258? Do you see a pattern from the previous examples? If we are trying to obtain a sum of some number \(m\) using \(k+1\) non-negative integers, then the stars-and-bars method tells us we'd need to count the number of permutations of \(m\) stars and \(k\) bars. In general, then, there are:

\(\dfrac{(m+k)!}{m!k!}\)

ways of obtaining the sum \(m\) using \(k+1\) non-negative integers.


Legend
[1]Link
Has Tooltip/Popover
 Toggleable Visibility