More Examples

Printer-friendly version

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 × 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 t time.)
• If you want to place n things in r positions, and you care about order, you can do it in n÷ (nr)! ways. (Doing so is called permuting n items r at t time.)
• If you have m items of one kind, n items of another kind, and o items of a third kind, then there are (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 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

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).

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.

Example

How many four-letter codes are possible?

Solution. 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 × 26 × 26 × 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?

Solution.  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 × 25 × 24 × 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?

Solution. 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 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

In how many ways can 4 heterosexual 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 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! × 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 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! × 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!

Example

How many ways are there to choose non-negative integers abcd, and e, such that the non-negative 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 "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, 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:

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:

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:

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 abcd, 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 and 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:

The stars-and-bars 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 non-negative integers and 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.