In this lesson, our goals are to:
Dr. Roll Toss wants to calculate the probability that he will get:
a 6 and a head
when he rolls a fair sixsided 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(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(S), he could enumerate all of the possible outcomes:
S = {1H, 1T, 2H, 2T, ...}
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) = 1/12 or 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 costprohibitive. Let's generalize the principle.
The Multiplication Principle. If there are:
then there are n_{1} × n_{2} × ... × n_{m} outcomes of the composite experiment E_{1}E_{2} ... 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:
Let's take a look at another example.
How many possible license plates could be stamped if each license plate were required to have exactly 3 letters and 4 numbers?
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:
the Multiplication Principle tells us that there are:
Again, that is:
(26 × 26 × 26) × (10 × 10 × 10 × 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:
Therefore, the Multiplication Principle tells us that in this case there are 78,624,000 possible license plates:
That's still a lot of license plates!
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 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2)
or 2^{10 }= 1,024 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.
How many ways can four people fill four executive positions?
Solution. 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 × 3 × 2 × 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.
Suppose there are n positions to be filled with n different objects, in which there are:
The Multiplication Principle tells us there are then in general:
n × (n − 1) × (n − 2) × ... × 1 = n!
ways of filling the n positions. The symbol n! is read as "nfactorial," and by definition 0! equals 1.
Definition. A permutation of n objects is 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 _{n}P_{n}. That is:
_{n}P_{n} = n × (n − 1) × (n − 2) × ... × 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.
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?
Solution. 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? 
(After you've thought of how you'd solve our problem, click on the icon to reveal one possible solution.)
In how many ways can 7 different books be arranged on a shelf?
Solution. 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 × 6 × 5 × 4 × 3 × 2 × 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 _{7}P_{7 }= 7! = 5,040.
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.
Definition. Sampling without replacement occurs when an object is not replaced after it has been selected. 
Solution. 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.
Definition. Sampling with replacement occurs when an object is selected and then replaced before the next object has been selected. 
Solution. If we sample with replacement, we have 6 choices for each of the 6 jobs. Applying the Multiplication Principle, there are:
6 × 6 × 6 × 6 × 6 × 6 = 46,656
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 takehome 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?
Okay, let's throw a (small) wrench into our work. How many ways can 4 people fill 3 chairs?
Solution. 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 × 3 × 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 ≤ n.
Suppose there are r positions to be filled with n different objects, in which there are:
The Multiplication Principle tells us there are in general:
n × (n − 1) × (n − 2) × ... × [n − (r − 1)]
ways of filling the r positions. We can easily show that, in general, this quantity equals:
\(\dfrac{n!}{(nr)!}\)
Here's how it works:
And, formally:
Definition. A permutation of n objects taken r at a time is an ordered arrangement of n different objects in r positions. The number of such permutations is: \(_nP_r=\dfrac{n!}{(nr)!}\)

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.
An artist has 9 paintings. How many ways can he hang 4 paintings sidebyside on a gallery wall?
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):
(Method #1) We learned how to count the number of ordered subsets on the last page. It is just _{n}P_{r}, the number of permutations of n objects taken r at a time.
(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 × 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:
_{n}P_{r }= C × 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.
Definition. The number of unordered subsets, called a combination of n objects taken r at a time, is: \(_nC_r=\dbinom{n}{r}=\dfrac{n!}{r!(nr)!}\) 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.
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?
Solution. 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!(127)!}=792\)
different possible subsets of 7 patients that can be selected.
Let's use a standard deck of cards [1] 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 fivecard poker. If you are dealt five cards, what is the probability of getting a "fullhouse" hand containing three kings and two aces (KKKAA)?
If you are dealt five cards, what is the probability of getting any fullhouse hand?
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^{nr}\)
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.
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)?
Solution. 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 × 2 × 2 × 2 × 2 × 2 × 2 × 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 56/256 = 0.22.
Let's formalize our work here!
Definition. Given n objects with:
there are: \(_nC_r=\binom{n}{r}=\dfrac{n!}{r!(nr)!}\) distinguishable permutations of the n objects. 
Let's take a look at another example that involves counting distinguishable permutations of objects of two types.
Suppose Dr. DoesBadThings conducts research which involves infecting 20 people with the swine flu virus. He is interested in studying how many actually end up ill (I) and how many remain healthy (H).
How many arrangements are there of the 20 people that involve 0 people ill?
Solution. In this case, we can readily determine that there is just 1 way. The sequence would look like this:
HHHHHHHHHHHHHHHHHHHH
Alternatively, we could use the formula for counting distinguishable permutations. The formula yields:
\(\dbinom{20}{0}=\dfrac{20!}{0!20!}=1\)
How many arrangements are there of the 20 people that involve 1 person ill?
Solution. I think we can readily convince ourselves that there are 20 ways. The first possible sequence might look like this:
I H H H H H H H H H H H H H H H H H H H
The second possible sequence might look like this:
H I H H H H H H H H H H H H H H H H H H
And, the last possible sequence might look like this:
H H H H H H H H H H H H H H H H H H H I
That must mean that there are 20 possible positions for the one I. Alternatively, we could use the formula for counting distinguishable permutations. The formula yields:
\(\dbinom{20}{1}=\dfrac{20!}{1!19!}=20\)
How may arrangements are there of the 20 people that involve 2 people ill?
Solution. I'm going to leave it to you to decide if you want to try to count this one out by hand! I can tell you that the first possible sequence might look like this:
I I H H H H H H H H H H H H H H H H H H
The formula for counting distinguishable permutations yields:
\(\dbinom{20}{2}=\dfrac{20!}{2!18!}=190\)
possible arrangements.
How many ordered arrangements are there of the letters in MISSISSIPPI?
Solution. 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.
Definition. The number of distinguishable permutations of n objects, of which:
and n = n_{1} + n_{2} + ... + 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.
How many ordered arrangements are there of the letters in the word PHILIPPINES?
Solution. 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\)
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?
Solution. 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!
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:
Let's take a look at some examples now!
A 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?
Solution. 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).
Now the ship's captain sends signals by arranging 3 red, 4 orange and 2 blue flags on a vertical pole. How many different signals could the ship's captain possibly send?
Solution. 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.
How many fourletter codes are possible?
Solution. One example of a fourletter code is XSST. Another example is RLPR. If we were to try to enumerate all of the possible fourletter 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 × 26 × 26 × 26 = 456, 976
possible fourletter codes.
Now, let's add a restriction. How many fourletter codes are possible if no letter may be repeated?
Solution. One example of a fourletter code, with no letters repeated, is XSGT. Another such example is RLPW. If we were to try to enumerate all of the possible fourletter 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 × 25 × 24 × 23 = 358,800
possible fourletter 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 fourletter codes.
Now, let's add yet another restriction. How many fourletter codes are possible if no repetition is allowed and order is not important?
Solution. Again, one example of a fourletter 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 fourletter 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 overcounted, that is, by the 4! ways of ordering the four letters. That is, the 4! in the denominator reduces the number of 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 fourletter 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!
In how many ways can 4 married couples attending a concert be seated in a row of 8 seats if there are no restrictions as to where the 8 people can sit?
Solution. Here are the eight 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 × 7 × 6 × 5 × 4 × 3 × 2 × 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?
Solution. Here are the eight seats shown as four paired 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 twostep 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! × 2! × 2! × 2! × 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?
Solution. Here are the eight seats, shown as two sets of fours 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 twostep 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! × 4! × 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!
How many ways are there to choose nonnegative integers a, b, c, d, and e, such that the nonnegative integers add up to 6, that is:
a + b + c + d + e = 6
Solution. 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, and e = 3. Another example is:
1 + 0 + 1 + 4 + 0 = 6
where a = 1, b = 0, c = 1, d = 4, and e = 0. And one last example is:
0 + 0 + 0 + 0 + 6 = 6
where a = 0, b = 0, c = 0, d = 0, 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, and e must each be an integer between 0 and 6.
Now, to advance our solution, we'll use what is called the "starsandbars" 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, 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 starsandbars would look like for our first example in which 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 starsandbars would look like for our second example in which 1 + 0 + 1 + 4 + 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 starsandbars would look like for our last example in which 0 + 0 + 0 + 0 + 6 = 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 nonnegative 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 nonnegative integers a, b, c, d, and e, such that the nonnegative integers add up to 6.
Do you get it? Try this next one out to test yourself. How many ways are there to choose nonnegative integers a and b such that the nonnegative integers add up to 5, that is:
a + b = 5
One such example is 1 + 4 = 5. Its starsandbars graphic would look like this:
The starsandbars graphic for 2 + 3 = 5 would look like this:
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 nonnegative integers a and b such that the nonnegative integers add up to 5.
Are you ready for another one? How many ways can you specify 89 nonnegative integers such that the nonnegative 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 nonnegative integers, then the starsandbars 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 nonnegative integers.
Links:
[1] https://onlinecourses.science.psu.edu/stat414/sites/onlinecourses.science.psu.edu.stat414/files/lesson02/cards.gif