7.5: Combinations WITH Repetitions

Last updated
Save as PDF

Page ID: 28730

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Consider our choice of \(3\) people out of \(20\) Discrete students.

Permutations include all the different arrangements, so we say "order matters" and there are \(P(20,3)\) ways to choose \(3\) people out of \(20\) to be president, vice-president and janitor. Steve, Ahmet, Liz (SAL) v.s Liz, Ahmet, Steve (LAS) are two different arrangements.

For combinations, we chose \(3\) people out of \(20\) to get an A for the course so order does not matter. This is "\(20\) choose \(3\)", the number of sets of 3 where order does not matter. SAL and LAS are the same arrangement. This one is \(\binom{20}{3}\).

In both permutations and combinations, repetition is not allowed. LLA is not a choice.

Now we move to combinations with repetitions. Here we are choosing \(3\) people out of \(20\) Discrete students, but we allow for repeated people. These are combinations, so SAL and LAS are still the same choice, but we have other distinct choices such as LLA, SSS, WAW, SWW, and many more!

Example \(\PageIndex{1}\) First example

Determine the number of ways to choose 3 tea bags to put into the teapot. You have 100 each of these six types of tea: Black tea, Chamomile, Earl Grey, Green, Jasmine and Rose. (Essentially you have an unlimited number of each type of tea.). You can repeat types of tea.

For example, some choices are: CEJ, CEE, JJJ, GGR, etc.

type of tea:	Black	Chamomile	Earl Grey	Green	Jasmine	Rose
choices:	x		xx
# of choices:	1	0	2	0	0	0

This arrangement is BEE.

type of tea:	Black	Chamomile	Earl Grey	Green	Jasmine	Rose
choices:				xx		x
# of choices:	0	0	0	2	0	1

This arrangement is GGR.

Our 6 types of tea gives us 5 dividers.

We are choosing 3 tea bags, so we need 3 x's along with the 5 dividers.

Here are the two choices on the tables above: x | | x x | | | and | | | x x | | x.

What are the letters for these two choices? | | | | xx|x and x| | x | x | | .

Answer: JJR and BEG

We are arranging 8 objects (5 dividers and 3 choices of tea bags), so we have 8 spots to put the 3 tea bags.

______ ______ ______ ______ ______ ______ ______ ______

Once we place the 3 tea bags, the placement of the 5 dividers is automatically determined.

There are \(\binom{8}{3}\) ways to pick the 3 tea bags.

Where did the \(8\) and \(3\) come from? See the following theorem.

Combination with Repetition formula

Theorem \(\PageIndex{1}\label{thm:combin}\)

If we choose a set of \(r\) items from \(n\) types of items, where repetition is allowed and the number items we are choosing from is essentially unlimited, the number of selections possible:

\[\binom{n+r-1}{r}.\]

Example \(\PageIndex{2}\) Example with Restrictions

From an unlimited selection of five types of soda, one of which is Dr. Pepper, you are putting 25 cans on a table.

(a) Determine the number of ways you can select 25 cans of soda.

Solution: This is the case with no restrictions. \(\binom{5+25-1}{25}=\binom{29}{25}=23751\)
There are 23751 ways to select 25 cans of soda with five types.

(b) Determine the number of ways you can select 25 cans of soda if you must include at least seven Dr. Peppers.

Solution: Here figure seven Dr. Peppers are already selected, so you are really choosing \(25-7=18\) cans. \(\binom{5+18-1}{18}=\binom{22}{18}=7315\)
There are 7315 ways to select 25 cans of soda with five types, with at least seven of one specific type.

(c) Determine the number of ways you can select 25 cans of soda if it turns out there are only three Dr. Peppers available.

Solution: This is harder to do directly, and easier to use the complement. The complement is "four or more Dr. Peppers" which is at least four Dr. Peppers.
Following our reasoning in (b), the number of ways to select 25 cans with at least four Dr. Peppers is \(\binom{5+21-1}{21}=\binom{25}{21}=12650.\)
So there are 12650 ways to get four or more Dr. Peppers. We need to subtract that from the total in order to get the number of three or less Dr. Peppers.
\(\binom{5+25-1}{25}-\binom{5+21-1}{21}=\binom{29}{25}-\binom{25}{21}=23751-12650=11101.\)
There are 11101 ways to select 25 cans of soda with five types, with no more than three of one specific type.

Summary and Review

Permutations: order matters, repetitions are not allowed.
(regular) Combinations: order does NOT matter, repetitions are not allowed.
Combinations WITH Repetitions: order does NOT matter, repetitions ARE allowed.

Exercises

Exercise \(\PageIndex{1}\label{ex:combin-01}\)

Lollypop Farm has cats, dogs, goats, ducks and horses. How many ways can you select three pets to take home?

Solution: \(\binom{7}{3}=35\)

Exercise \(\PageIndex{2}\label{ex:combin-02}\)

You are going to bring two bags of chips to a party. In the chip aisle, you see regular potato chips, barbecue potato chips, sour cream and onion potato chips, corn chips and scoopable corn chips. How many selections can you make?

Exercise \(\PageIndex{3}\label{ex:combin-03}\)

(a) Compute \(\binom{5+7-1}{7}\) (to an integer).

(b) If you had to compute \(\binom{5+7-1}{7}\) without a calculator, how could you simplify the calculations?

You are sitting with a number of friends and go to get ____________cans of soda for your table. There are __________types of soda. How many selections can you make?

Solution: (a) 330
(b) \(\binom{5+7-1}{7}=\binom{11}{7} =\binom{11}{4}=\frac{11 \cdot 10 \cdot 9 \cdot 8}{4 \cdot 3 \cdot 2 \cdot 1}=\frac{11 \cdot 10 \cdot 9}{3}=11 \cdot 10 \cdot 3=110 \cdot 3=330\)
(c) get 7 cans of soda; 5 types of soda

Exercise \(\PageIndex{4}\label{ex:combin-04}\)

You are setting out 30 cans of drinks. There are six types of drinks, and one type is seltzer.

(a) How many ways can you choose drinks to set out?

(b) How many ways can you choose drinks to set out that include at least 8 cans of seltzer?

Exercise \(\PageIndex{5}\label{ex:combin-05}\)

Twenty batteries will be put on the display. The types of batteries are: AAA, AA, C, D, and 9-volt.

(a) How many ways can we choose the twenty batteries?

(b) How many ways can we choose the twenty batteries but be sure that at least four batteries that are are 9-volt batteries?

Solution: (a) \(\binom{24}{20}=10626\)

(b) \(\binom{20}{16}=4845\)

(c) \(\binom{24}{20}-\binom{21}{17}=4641\)

Exercise \(\PageIndex{6}\label{ex:combin-06}\)

Use the tea bags from Example 7.5.1: Black, Chamomile, Earl Grey, Green, Jasmine and Rose for these questions.

(a) You are making a cup of tea for the Provost, a math professor and a student. How many ways can you do this?

(b) You are making a cup of tea for the Provost, a math professor and a student. Each person will have a different flavor. How many ways can you do this?

(d) You are making a pot of tea with four tea bags, each a different flavor. How many ways can you do this?

(e) You are setting out 30 tea bags. How many ways can you do this?

(f) You are setting out 30 tea bags, but there are only five Rose tea bags available. How many ways can you do this?

(g) You are setting out 30 tea bags and will include at least 10 Earl Grey. How many ways can you do this?

Exercise \(\PageIndex{7}\label{ex:combin-07}\)

How many non-negative integer solutions are there to this equation: \[x_1+x_2+x_3+x_4=18?\]

Solution: \(\binom{21}{18}=1330\)

Exercise \(\PageIndex{8}\label{ex:combin-08}\)

How many non-negative solutions are there to this equation: \[x_1+x_2+x_3+x_4+x_5=26?\]