Skip to main content

Section 2.5 Counting with Repetition or Indistinguishable Objects

Subsection 2.5.1 Tuples or Permutations with Repetition

We have already seen in Example 2.2.11 that if we want to choose an ordered list from a set of items but allow items to be chosen repeatedly, this doesn't follow the formal definition of a permutation. Instead we are forming ordered \(n-\)tuples or permutations with repetition and The Rule Of Products is applied.

How many strings of length \(r\) can be formed from the uppercase letters of the English alphabet?

Each of the \(r\) positions in the string has 26 possibilities, so by The Rule Of Products there are \(26^r\) strings.

Subsection 2.5.2 Combinations with Repetition

Suppose we don't care about the order and items can be repeated or items are indistinguishable from each other.

Consider the following counting problem:

\begin{equation*} \mbox{You have 7 identical cookies to give to 4 kids.}\\\mbox{ How many ways can you do this?} \end{equation*}

Take a moment to think about how you might solve this problem. You may assume that it is acceptable to give a kid no cookies. Also, the order in which you give out the cookies does not matter.

You might guess that each cookie can be assigned to one of four possible kids and by The Rule Of Products the answer should be \(4^7\text{.}\) However, this doesn't work. Consider a few possible outcomes: we could assign the first six cookies to kid A, and the seventh cookie to kid B. Another outcome would assign the first cookie to kid B and the six remaining cookies to kid A. Both outcomes are included in the \(4^7\) answer. But because the cookies are identical, both of those outcomes are really the same, kid A gets six cookies and kid B gets one cookie.

What do outcomes actually look like? How can we represent them? One approach would be to write an outcome as a string of four numbers like this:

\begin{equation*} 3112, \end{equation*}

to represent the outcome in which the first kid gets 3 cookies, the second and third kid each get 1 cookie, and the fourth kid gets 2 cookies. Represented this way, the order in which the numbers occur matters. 1312 is a different outcome, because the first kid gets a one cookie instead of 3. Each number in the string can be any integer between 0 and 7. But we cannot use the The Rule Of Products because the sum of the numbers must be 7.

Another way we might represent outcomes is to write a string of seven letters:

\begin{equation*} \mbox{ABAADCD} , \end{equation*}

which represents that the first cookie goes to kid A, the second cookie goes to kid B, the third and fourth cookies go to kid A, and so on. In fact, this outcome is identical to the previous one—A gets 3 cookies, B and C get 1 each and D gets 2. Each of the seven letters in the string can be any of the 4 possible letters (one for each kid), but again we cannot use The Rule Of Products because here order does not matter. In fact, another way to write the same outcome is

\begin{equation*} \mbox{AAABCDD} . \end{equation*}

Now think about how you could specify such an outcome in general. All we really need to do is say when to switch from one letter to the next. In terms of cookies, we need to say after how many cookies do we stop giving cookies to the first kid and start giving cookies to the second kid. And then after how many do we switch to the third kid? And after how many do we switch to the fourth? So yet another way to represent an outcome is like this:

\begin{equation*} ***|*|*|** \end{equation*}

Three cookies go to the first kid, then we switch and give one cookie to the second kid, then switch, one to the third kid, switch, two to the fourth kid. Notice that we need 7 stars and 3 bars – one star for each cookie, and one bar for each switch between kids, so one fewer bars than there are kids (we don't need to switch after the last kid – we are done).

Why have we done all of this? Simple: to count the number of ways to distribute 7 cookies to 4 kids, all we need to do is count how many different stars and bars charts there are.

Before we get too excited, we should make sure that really any string of (in our case) 7 stars and 3 bars corresponds to a different way to distribute cookies to kids. In particular consider a string like this:

\begin{equation*} |***||**** \end{equation*}

Does that correspond to a cookie distribution? Yes. It represents the distribution in which kid A gets 0 cookies (because we switch to kid B before any stars), kid B gets three cookies (three stars before the next bar), kid C gets 0 cookies (no stars before the next bar) and kid D gets the remaining 4 cookies. No matter how the stars and bars are arranged, we can distribute cookies in that way. Also, given any way to distribute cookies, we can represent that with a stars and bars chart. For example, the distribution in which kid A gets 6 cookies and kid B gets 1 cookie has the following chart:

\begin{equation*} ******|*|| \end{equation*}

After all that work we are finally ready to count. Each way to distribute 7 cookies to 4 kids corresponds to a stars and bars chart with 7 stars and 3 bars. So there are 10 symbols, and we must choose 3 of them to be bars. Thus:

\begin{equation*} \mbox{ There are } {10 \choose 3 } = \frac{10!}{(10-3)!3!} = \frac{10*9*8}{3*2*1} = 120 \mbox{ ways to distribute 7 cookies to 4 kids.} \end{equation*}

We generalize this result in the following theorem:

While we are at it, we can also answer a related question: how many ways are there to distribute 7 cookies to 4 kids so that each kid gets at least one cookie?

Giving each kid one cookie is required and there is no choice. We only need to count how the remaining 3 cookies can be distributed to the 4 kids. So we have 3 stars and 3 bars for a total of 6 symbols, 3 of which must be bars. So we see that there are \({6 \choose 3}\) ways to distribute the cookies.

Stars and bars can be used in counting problems other than kids and cookies. Here are a few examples:

Your favorite mathematical pizza chain offers 10 toppings. How many pizzas can you make if you are allowed 6 toppings? The order of toppings does not matter but now you are allowed repeats. So one possible pizza is triple sausage, double pineapple, and onions.

Solution

We get 6 toppings (counting possible repeats). Represent each of these toppings as a star. Think of going down the menu one topping at a time: you see anchovies first, and skip to the next, sausage. You say yes to sausage 3 times (use 3 stars), then switch to the next topping on the list. You keep skipping until you get to pineapple, which you say yes to twice. Another switch and you are at onions. You say yes once. Then you keep switching until you get to the last topping, never saying yes again (since you already have said yes 6 times. There are 10 toppings to choose from, so we must switch from considering one topping to the next 9 times. These are the bars.

Now that we are confident that we have the right number of stars and bars, we answer the question simply: there are 6 stars and 9 bars, so 15 symbols. We need to pick 9 of them to be bars, so there number of pizzas possible is

\begin{equation*} {15 \choose 9} = \frac{15!}{(15-9)!9!} = \frac{15*14*13*12*11*10}{6*5*4*3*2*1} = 5005\text{.} \end{equation*}

How many 7 digit phone numbers are there in which the digits are non-increasing? That is, every digit is less than or equal to the previous one.

Solution

We need to decide on 7 digits so we will use 7 stars. The bars will represent a switch from each possible single digit number down the next smaller one. So the phone number 866-5221 is represented by the stars and bars chart

\begin{equation*} |*||**|*|||**|*| \end{equation*}

There are 10 choices for each digit (0-9) so we must switch between choices 9 times. We have 7 stars and 9 bars, so the total number of phone numbers is

\begin{equation*} {16 \choose 9}. \end{equation*}

How many solutions are there to the equation

\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 = 13. \end{equation*}

if \(x_1, x_2, x_3, x_4\) and \(x_5\) are integers?

  1. where \(x_i \ge 0\) for each \(x_i\text{?}\)

  2. where \(x_i > 0\) for each \(x_i\text{?}\)

  3. where \(x_i \ge 2\) for each \(x_i\text{?}\)

Solution

This problem is just like giving 13 cookies to 5 kids. We need to say how many of the 13 units go to each of the 5 variables. In other words, we have 13 stars and 4 bars (the bars are like the “+” signs in the equation).

  1. If \(x_i\) can be 0 or greater, we are in the standard case with no restrictions. So 13 stars and 4 bars can be arranged in \({17 \choose 4}\) ways.

  2. Now each variable must be at least 1. So give one unit to each variable to satisfy that restriction. Now there are 8 stars left, and still 4 bars, so the number of solutions is \({12 \choose 4}\text{.}\)

  3. Now each variable must be 2 or greater. So before any counting, give each variable 2 units. We now have 3 remaining stars and 4 bars, so there are \({7 \choose 4}\) solutions.

Subsection 2.5.3 Ordering Indistinguishable Objects

In the previous section, we examined how many ways we can choose from a limited number indistinguishable objects, where the order didn't matter. If one child got four cookies, it didn't matter if she was given one first and the other three after all the rest of the cookies were given out to the other children. What can we do if the order of choosing does matter?

Suppose we wish to count the number of ways we can rearrange the letters in the word "PROCESSES". For this kind of counting problem we cannot apply the Permutation Formula because two letters, "S" and "E", are repeated. We also cannot use the Rule of Products because the repetition is limited, we only have three "S"s, two "E"s, and one each of "P", "R", "O" and "C" to choose.

We have nine positions to fill. We can first choose three of those positions for the "S"s: \(\binom{9}{3}\) (note we use the binomial formula because the "S"s are identical, the order of the "S"s doesn't matter). Then we will have six positions left to fill. We can choose two of those for the "E"s: \(\binom{6}{2}\) That leaves four positions for "P", three for "R", two for "O" and one for "C": \(\binom{4}{1}\text{,}\) \(\binom{3}{1}\) , \(\binom{2}{1}\text{,}\) \(\binom{1}{1}\)

We can then apply the product rule to determine how many ways there are to do all of those:

\begin{align*} \binom{9}{3} \binom{6}{2} \binom{4}{1} \binom{3}{1} \binom{2}{1} \binom{1}{1} \amp = \frac{9!}{6!3!} * \frac{6!}{4!2!} * \frac{4!}{3!1!} * \frac{3!}{2!1!} * \frac{2!}{1!1!} * \frac{1!}{0!1!} \\ \amp \text{Most cancel or are 1}\\ \amp = \frac{9!}{3!2!1!1!1!}\\ \amp = 30240 \end{align*}
Definition 2.5.7. Multiset.

A multiset is a collection of objects, just like a set, but can contain an object more than once (the order of the elements still doesn't matter). For example, \(\{1,1, 2, 5, 5, 7\}\) is a multiset of size 6.

Definition 2.5.8. Multiplicity.

The multiplicity of a particular type of object is the number of times objects of that type appear in a multiset. For example, in the word "PROCESSES", the letter "S" has multiplicity three, the letter "E" has multiplicity two, and "P", "R", "O" and "C" each have multiplicity one.

We can generalize the result from Example 2.5.6 to the following theorem.

We saw this example in Subsection 2.4.3. Now we have a formula to solve it directly, though it might not seem like the same type of problem at first.

In bridge, the location of a hand in relation to the dealer has some bearing on the game. The number of possible hands takes into account the number each player's possible hands depending on the order in which they are dealt. The player in the West position gets their 13 cards first, then the player in the North position gets 13 cards, then the player in the East gets 13 cards and finally the South gets 13 cards. We can apply Theorem 2.5.9 to solve this.

In this case we have \(n = 52\) items, the cards, and four "types" of items, West's cards, North's cards, East's cards, and South's cards, each with multiplicity 13. To see how we can use the Theorem 2.5.9 to solve this: apply some ordering to the entire deck of cards, say the Ace of Hearts is first, the Two of Hearts is second, and so on, for all 52 cards. Then the cards dealt to West correspond to choosing positions for 13 cards (of type West's cards), the cards dealt to North correspond to choosing positions for 13 cards of type North's cards, and so on.

\begin{equation*} \binom{52}{13}\binom{39}{13}\binom{26}{13}\binom{13}{13} = \frac{52!}{13!*13!*13!* 13!} \end{equation*}

Exercises 2.5.4 Exercises

1.

  1. How many regular sets of size 5 can be made using the 10 numeric digits 0 through 9?

  2. How many multisets of size 5 can be made using the 10 numeric digits 0 through 9?

Solution
  1. \({10\choose 5}\) sets can be made. We must select 5 of the 10 digits to put in the set.

  2. Use stars and bars: each star represents one of the 5 elements of the set, each bar represents a switch between digits. So there are 5 stars and 9 bars, giving us \({14 \choose 9}\) sets.

2.

When playing Yahtzee, you roll five regular 6-sided dice. How many different outcomes are possible from a single roll? The order of the dice does not matter.

3.

Each of the counting problems below can be solved with stars and bars. For each, say what outcome the diagram

\begin{equation*} ***|*||**| \end{equation*}

represents, if there are the correct number of stars and bars for the problem. Otherwise, say why the diagram does not represent any outcome, and what a correct diagram would look like.

  1. How many ways are there to select a handful of 6 jellybeans from a jar that contains 5 different flavors?

  2. How many ways can you distribute 5 identical lollipops to 6 kids?

  3. How many 6-letter words can you make using the 5 vowels?

  4. How many solutions are there to the equation \(x_1 + x_2 + x_3 + x_4 = 6\text{.}\)

Solution

  1. You take 3 strawberry, 1 lime, 0 licorice, 2 blueberry and 0 bubblegum.

  2. This is backwards. We don't want the stars to represent the kids because the kids are not identical, but the stars are. Instead we should use 5 stars (for the lollipops) and use 5 bars to switch between the 6 kids. For example,

    \begin{equation*} **||***||| \end{equation*}

    would represent the outcome with the first kid getting 2 lollipops, the third kid getting 3, and the rest of the kids getting none.

  3. This is the word AAAEOO.

  4. This doesn't represent a solution. Each star should represent one of the 6 units that add up to 6, and the bars should switch between the different variables. We have one too many bars. An example of a correct diagram would be

    \begin{equation*} *|**||***, \end{equation*}

    representing that \(x_1 = 1\text{,}\) \(x_2 = 2\text{,}\) \(x_3 = 0\text{,}\) and \(x_4 = 3\text{.}\)

4.

Solve the three counting problems below. Then say why it makes sense that they all have the same answer. That is, say how you can interpret them as each other.

  1. How many ways are there to distribute 8 cookies to 3 kids?

  2. How many solutions in non-negative integers are there to \(x+y+z = 8\text{?}\)

  3. How many different packs of 8 crayons can you make using crayons that come in red, blue and yellow?

5.

After gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins.

  1. How many ways can you do this if there are no restrictions?

  2. How many ways can you do this if each bin must contain at least one dodgeball?

Solution
  1. \({18 \choose 4}\) ways. Each outcome can be represented by a sequence of 14 stars and 4 bars.
  2. \({13 \choose 4}\) ways. First put one ball in each bin. This leaves 9 stars and 4 bars.
6.
  1. How many ways can the letters in the word "SURFED" be rearranged?
  2. How many ways can the letters in the word "SURFER" be rearranged?
7.

How many integer solutions are there to the equation

\begin{equation*} x + y + z = 8 \end{equation*}

for which

  1. \(x\text{,}\) \(y\text{,}\) and \(z\) are all positive?
  2. \(x\text{,}\) \(y\text{,}\) and \(z\) are all non-negative?
  3. \(x\text{,}\) \(y\text{,}\) and \(z\) are all greater than \(-3\text{?}\)
Solution
  1. \({7 \choose 2}\) solutions. After each variable gets 1 star for free, we are left with 5 stars and 2 bars.
  2. \({10 \choose 2}\) solutions. We have 8 stars and 2 bars.
  3. \({19 \choose 2}\) solutions. This problem is equivalent to finding the number of solutions to \(x' + y' + z' = 17\) where \(x'\text{,}\) \(y'\) and \(z'\) are non-negative. (In fact, we really just do a substitution. Let \(x = x'- 3\text{,}\) \(y = y' - 3\) and \(z = z' - 3\)).
8.

How many integer solutions to

\begin{equation*} x_1 + x_2 + x_3 + x_4 = 25 \end{equation*}

are there for which \(x_1 \ge 1\text{,}\) \(x_2 \ge 2\text{,}\) \(x_3 \ge 3\) and \(x_4 \ge 4\text{?}\)

9.

Using the digits 2 through 8, find the number of different 5-digit numbers such that:

  1. Digits cannot be repeated and must be written in increasing order. For example, 23678 is okay, but 32678 is not.

  2. Digits can be repeated and must be written in non-decreasing order. For example, 24448 is okay, but 24484 is not.

Solution

  1. There are \({7 \choose 5}\) numbers. We simply choose five of the seven digits and once chosen put them in increasing order.

  2. This requires stars and bars. Use a star to represent each of the 5 digits in the number, and use their position relative to the bars to say what numeral fills that spot. So we will have 5 stars and 6 bars, giving \({11 \choose 6}\) numbers.

10.

Conic, your favorite math themed fast food drive-in offers 20 flavors which can be added to your shave ice. You have enough money to buy a large shave ice with 4 flavors. How many different shave ice concoctions can you order if:

  1. You refuse to use any of the flavors more than once?

  2. You refuse repeats but care about the order the flavors are added?

  3. You allow yourself multiple shots of the same flavor?

  4. You allow yourself multiple shots, and care about the order the flavors are added?

login