7.4: Combinations

In many counting problems, the order of arrangement or selection does not matter. In essence, we are selecting or forming subsets.

If we are choosing \(3\) people out of \(20\) Discrete students to be president, vice-president and janitor, then the order makes a difference.  The choice of:

Steve, Ahmet, Liz (SAL) v.s Liz, Ahmet, Steve (LAS) would make quite a difference for Liz and Steve. 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.

Now, change the scenario to chose \(3\) people out of \(20\) to get an A for the course.  This time SAL and LAS are not considered different choices; here we say "order does not matter".  This scenario is the number of combinations (basically subsets) and we call this one "\(20\) choose \(3\)".  With permutations, each set of 3 letters, such as SAL, will be rearranged \(3!\) or \(6\) times.  For combinations, we only use a set of 3 letters once (since order does not matter) and so the number of combinations in this case will be \(\frac{P(20,3)}{3!}.\)

Example \(\PageIndex{1}\label{eg:combin-01}\)

Determine the number of ways to choose 4 values from 1, 2, 3, …, 20, in which the order of selection does not matter.

Solution

Let \(N\) be the number of ways to choose the 4 numbers. Since the order in which the numbers are selected does not matter, these are not sequences (in which order of appearance matters). We can change a selection of 4 numbers into a sequence. The 4 numbers can be arranged in \(P(4,4)=4!\) ways. Therefore, all these 4-number selections together produce \(N\cdot4!\) sequences. The number of 4-number sequences is \(P(20,4)\). Thus, \(N\cdot4!=P(20,4)\), or equivalently, \(N=P(20,4)/4!\).

Definition: combinations

The number of \(r\)-element subsets in an \(n\)-element set is denoted by

\[C(n,r) \qquad\mbox{ or }\qquad \binom{n}{r},\]

where \({n\choose r}\) is read as “\(n\) choose \(r\).” It determines the number of combinations of \(n\) objects, taken \(r\) at a time (without replacement). Alternate notations such as \(_nC_r\) and \(C_r^n\) can be found in other textbooks and some calculators. Do not write it as \((\frac{n}{r})\); this notation has a completely different meaning.

Recall that \(\binom{n}{r}\) counts the number of ways to choose or select \(r\) objects from a pool of \(n\) objects in which the order of selection does not matter. Hence, \(r\)-combinations are subsets of size \(r\).

Example \(\PageIndex{2}\label{eg:combin-02}\)

The 2-combinations of \(S=\{a,b,c,d\}\) are

\[\{a,b\}, \quad \{a,c\}, \quad \{a,d\}, \quad \{b,c\}, \quad \{b,d\}, \quad\mbox{and}\quad \{c,d\}.\]

Therefore \(\binom{4}{2}=6\). What are the 1-combinations and 3-combinations of \(S\)? What can you say about the values of \(\binom{4}{1}\) and \(\binom{4}{3}\)?

Solution

The 1-combinations are the singleton sets \(\{a\}\), \(\{b\}\), \(\{c\}\), and \(\{d\}\). Hence, \(\binom{4}{1}=4\). The 3-combinations are \[\{a,b,c\}, \quad \{a,b,d\}, \quad \{a,c,d\}, \quad\mbox{and}\quad \{b,c,d\}.\] Thus, \(\binom{4}{3}=4\).

 C(n,r) formula 

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

For all integers \(n\) and \(r\) satisfying \(0\leq r\leq n\), we have \[\binom{n}{r} = \frac{P(n,r)}{r!} = \frac{n(n-1)\cdots(n-r+1)}{r!} = \frac{n!}{r!\,(n-r)!}.\]

Proof

The idea is similar to the one we used in the alternate proof of Theorem [thm:circperm]. Let \(A\) be the set of all \(r\)-permutations, and let \(B\) be the set of all \(r\)-combinations. Define \(\fcn{f}{A}{B}\) to be the function that converts a permutation into a combination by “unscrambling” its order. Then \(f\) is an \(r!\)-to-one function because there are \(r!\) ways to arrange (or shuffle) \(r\) objects. Therefore \[|A| = r!\cdot|B|.\] Since \(|A|=P(n,r)\), and \(|B|=\binom{n}{r}\), it follows that \(\binom{n}{r} = P(n,r)/r!\).

Example \(\PageIndex{3}\label{eg:combin-03}\)

There are \(\binom{40}{5}\) ways to choose 5 numbers, without repetitions, from the integers \(1,2,\ldots,40\). To compute its numeric value by hand, it is easier if we first cancel the common factors in the numerator and the denominator. We find

\[\binom{40}{5} = \frac{40\cdot39\cdot38\cdot37\cdot36} {5\cdot4\cdot3\cdot2\cdot1} = 13\cdot38\cdot37\cdot36,\]

which gives \(\binom{40}{5}=658008\).

hands-on Exercise \(\PageIndex{1}\label{he:combin-01}\)

Compute \(\binom{12}{3}\) by hand.

hands-on Exercise \(\PageIndex{2}\label{he:combin-02}\)

A three-member executive committee is to be selected from a group of seven candidates. In how many ways can the committee be formed?

hands-on Exercise \(\PageIndex{3}\label{he:combin-03}\)

How many subsets of \(\{1,2,\ldots,23\}\) have five elements?

\(\binom{n}{r} = \binom{n}{n-r}\) 

Theorem  \(\PageIndex{2}\)

For \(0\leq r\leq n\), we have \(\binom{n}{r} = \binom{n}{n-r}\).

Proof

According to Theorem 7.4.1 we have \[\binom{n}{n-r} = \frac{n!}{(n-r)!\,(n-(n-r))!} = \frac{n!}{(n-r)!\,r!},\] which is precisely \(\binom{n}{r}\).

Example \(\PageIndex{4}\label{eg:combin-04}\)

To compute the numeric value of \(\binom{50}{47}\), instead of computing the product of 47 factors as indicated in the definition, it is much faster if we use \[\binom{50}{47} = \binom{50}{3} = \frac{50\cdot 49\cdot48}{3\cdot 2\cdot 1},\] from which we obtain \(\binom{50}{47} = 19600\).

hands-on Exercise \(\PageIndex{4}\label{he:combin-04}\)

Compute, by hand, the numeric value of \(\binom{529}{525}\).

Pascal's Triangle

In this section we will cover 

• how to construct Pascal's Triangle
• how to read values for combinations from Pascal's Triangle

In a later section, we will prove that this construction does give the values for combinations.

Start with a \(1\), then two more \(1\)'s.  Notice how the spacing is offset on each row. 

\[\begin{array}{*{13}{c}} & & & & & & 1 \\ & & & & & 1 & & 1 \\ & & & & 1 & & 2 & & 1 \\ & & & 1 & & 3 & & 3 & & 1 \end{array}\]

To create the next row, start with a \(1\) and then add the two entries just above. So under the   \( 1 \qquad 3 \qquad 3 \qquad 1\)   row, start with a \(1\), then add \(1+3=4\) to get the next entry, then \(3+3=6\), etc.  Notice the symmetry; this relates to Theorem 7.4.2.

\[\begin{array}{*{13}{c}} & & & & & & 1 \\ & & & & & 1 & & 1 \\ & & & & 1 & & 2 & & 1 \\ & & & 1 & & 3 & & 3 & & 1 \\ & & 1 & & 4 & & 6 & & 4 & & 1  \end{array}\]

 

Here's more of the triangle:

\[\begin{array}{*{13}{c}} & & & & & & 1 \\ & & & & & 1 & & 1 \\ & & & & 1 & & 2 & & 1 \\ & & & 1 & & 3 & & 3 & & 1 \\ & & 1 & & 4 & & 6 & & 4 & & 1 \\ & 1 & & 5 & &10 & &10 & & 5 & & 1 \\ 1 & & 6 & &15 & &20 & &15 & & 6 & & 1 \end{array}\]

From the top, these rows are the 0-row, the 1-row, the 2-row, etc.

The 5-row consists of: \[1 \qquad 5 \qquad 10 \qquad 10 \qquad 5 \qquad 1\]

These numbers correspond to:

\[\binom{5}{0}  \qquad  \binom{5}{1}   \qquad  \binom{5}{2}   \qquad  \binom{5}{3}   \qquad  \binom{5}{4}   \qquad  \binom{5}{5}   \qquad .\]

The symmetry of the triangle shows the symmetric values, such as \(\binom{5}{1}=\binom{5}{4}\) 

Example \(\PageIndex{5}\)

Use Pascal's Triangle to find \(\binom{7}{3}\).

Answer

After the 6-row (see above) create the 7-row. 
\[\begin{array}{*{13}{c}}  & & 1 & & 7  & & 21 && 35 && 35 && 21 & & 7 &&  1  \end{array}\]

Count over, \(\binom{7}{0}=1, \qquad \binom{7}{1}=7, \qquad \binom{7}{2}=21\), so the answer is
  \[\binom{7}{3}=35.\]

Now we are ready to look at some mixed examples. In all of these examples, sometimes we have to use permutation, other times we have to use combination. Very often we need to use both, together with the addition and multiplication principles. You may ask, how can I figure out what to do? We suggest asking yourself these questions:

1. Use the construction approach. If you want to list all the configurations that meet the requirement, how are you going to do it systematically?
2. Are there several cases involved in the problem? If yes, we need to list them first, before we go through each of them one at a time. Finally, add the results to come up with the final answer.
3. Do we allow repetitions or replacements? This question can also take the form of whether the objects are distinguishable or indistinguishable.
4. Does order matter? If yes, we have to use permutation. Otherwise, use combination.
5. Sometimes, it may be easier to use the multiplication principle instead of permutation, because repetitions may be allowed (in which case, we cannot use permutation, although we can still use the multiplication principle). Try drawing a schematic diagram and decide what we need from it. If the analysis suggests a pattern that follows the one found in a permutation, you can then use the formula for permutation.
6. Do not forget: it may be easier to work with the complement.

It is often not clear how to get started because there seem to be several ways to start the construction. For example, how would you distribute soda cans among a group of students? There are two possible approaches:

• From the perspective of the students. Imagine you are one of the students, which soda would you receive?
• From the perspective of the soda cans. Imagine you are holding a can of soda, to whom would you give this soda?

Depending on the actual problem, usually only one of these two approaches would work.

Example \(\PageIndex{5}\label{eg:combin-05}\)

Suppose we have to distribute 10 different soda cans to 20 students. It is clear that some students may not get any soda. In fact, some lucky students could receive more than one soda (the problem does not say this cannot happen). Hence, it is easier to start from the perspective of the soda cans.

Solution

We can give the first soda to any one of the 20 students, and we can also give the second soda to any one of the 20 students. In fact, we always have 20 choices for each soda. Since we have 10 sodas, there are \(\underbrace{20\cdot20\cdots20}_{10} = 20^{10}\) ways to distribute the sodas.

Example \(\PageIndex{6}\label{eg:combin-06}\)

In how many ways can a team of three representatives be selected from a class of 885 students? In how many ways can a team of three representatives consisting of a chairperson, a vice-chairperson, and a secretary be selected?

Solution

If we are only interested in selecting three representatives, order does not matter. Hence, the answer would be \(\binom{885}{3}\). If we are concerned about which offices these three representative will hold, then the answer should be \(P(885,3)\).

hands-on Exercise \(\PageIndex{5}\label{he:combin-05}\)

Mike needs some new shirts, but he has only enough money to purchase five of the eight that he likes. In how many ways can he purchase the five shirts by choosing them at random?

hands-on Exercise \(\PageIndex{6}\label{he:combin-06}\)

Mary wants to purchase four shirts for her four brothers, and she would like each of them to receive a different shirt. She finds ten shirts that she thinks they will like. In many ways can she select them?

Playing cards provide excellent examples for counting problems. Just in case you are not familiar with them, let us briefly review what a deck of playing cards contains.

• There are 52 playing cards, each of them is marked with a suit and a rank.
• There are four suits: spades (\(\spadesuit\)), hearts (\(\heartsuit\)), diamonds (\(\diamondsuit\)) and clubs (\(\clubsuit\)).
• Each suit has 13 ranks, labeled A, 2, 3, …, 9, 10, J, Q, and K, where A means ace, J means jack, Q means queen, and K means king.
• Each rank has 4 suits (see above).

hands-on Exercise \(\PageIndex{7}\label{he:combin-07}\)

Determine the number of five-card poker hands that can be dealt from a deck of 52 cards.

Solution

All we care is which five cards can be found in a hand. This is a selection problem. The answer is \(\binom{52}{5}\).

hands-on exercise \(\PageIndex{7}\label{eg:combin-07}\)

In how many ways can a 13-card bridge hand be dealt from a standard deck of 52 cards?

Example \(\PageIndex{8}\label{eg:combin-08}\)

In how many ways can a deck of 52 cards be dealt in a game of bridge? (In a bridge game, there are four players designated as North, East, South and West, each of them is dealt a hand of 13 cards.)

Solution

The difference between this problem and the last example is that the order of distributing the four bridge hands makes a difference. This is a problem that combines permutations and combinations. As we had suggested earlier, the best approach is to start from scratch, using the addition and/or multiplication principles, along with permutation and/or combination whenever it seems appropriate.

There are \(\binom{52}{13}\) ways to give 13 cards to the first player. Now we are left with 39 cards, from which we select 13 to be given to the second player. Now, out of the remaining 26 cards, we have to give 13 to the third player. Finally, the last 13 cards will be given to the last player (there is only one way to do it). The number of ways to deal the cards in a bridge game is \(\binom{52}{13} \binom{39}{13} \binom{26}{13}\).

We could have said the answer is \[\binom{52}{13} \binom{39}{13} \binom{26}{13} \binom{13}{13}.\] The last factor \(\binom{13}{13}\) is the number of ways to give the last 13 cards to the fourth player. Numerically, \(\binom{13}{13}=1\), so the two answers are the same. Do not dismiss this extra factor as redundant. Take note of the nice pattern in this answer. The bottom numbers are 13, because we are selecting 13 cards to be given to each player. The top numbers indicate how many cards are still available for distribution at each stage of the distribution. The reasoning behind the solution is self-explanatory!

[eg:combin-08]

Example \(\PageIndex{9}\label{eg:combin-09}\)

Determine the number of five-card poker hands that contain three queens. How many of them contain, in addition to the three queens, another pair of cards?

Solution

(a) The first step is to choose the three queens in \(\binom{4}{3}\) ways, after which the remaining two cards can be selected in \(\binom{48}{2}\) ways. Therefore, there are altogether \(\binom{4}{3} \binom{48}{2}\) hands that meet the requirements.

Solution

(b) As in part (a), the three queens can be selected in \(\binom{4}{3}\) ways. Next, we need to select the pair. We can select any card from the remaining 48 cards (therefore, there are 48 choices), after which we have to select one from the remaining 3 cards of the same rank. This gives \(48\cdot3\) choices for the pair, right? The answer is NO!

The first card we picked could be \(\heartsuit 8\), and the second could be \(\clubsuit 8\). However, the first card could have been \(\clubsuit 8\), and the second \(\heartsuit 8\). These two selections are counted as different selections, but they are actually the same pair! The trouble is, we are considering “first,” and “second” cards, which in effect imposes an ordering among the two cards, thereby turning it into a sequence or an ordered selection. We have to divide the answer by 2 to overcome the double-counting. The answer is therefore \(\frac{48\cdot3}{2}\).

Here is a better way to count the number of pairs. An important question to ask is

Which one should we pick first: the suit or the rank?

Here, we want to pick the rank first. There are 12 choices (the pair cannot be queens) for the rank, and among the four cards of that rank, we can pick the two cards in \(\binom{4}{2}\) ways. Therefore, the answer is \(12\binom{4}{2}\). Numerically, the two answers are identical, because \(12\binom{4}{2} = 12\cdot\frac{4\cdot3}{2} = \frac{48\cdot3}{2}\). In summary: the final answer is \(\binom{4}{3}\cdot12\binom{4}{2}\).

hands-on Exercise \(\PageIndex{8}\label{he:combin-08}\)

How many bridge hands contain exactly four spades?

hands-on Exercise \(\PageIndex{9}\label{he:combin-09}\)

How many bridge hands contain exactly four spades and four hearts?

hands-on Exercise \(\PageIndex{10}\label{he:combin-10}\)

How many bridge hands are there containing exactly four spades, three hearts, three diamonds, and three clubs?

Example \(\PageIndex{10}\label{eg:combin-10}\)

How many positive integers not exceeding 99999 contain exactly three 7s?

Solution

Regard each legitimate integer as a sequence of five digits, each of them selected from 0, 1, 2, …, 9. For example, the integer 358 can be considered as 00358. Three out of the five positions must be occupied by 7. There are \(\binom{5}{3}\) ways to select these three slots. The remaining two positions can be filled with any of the other nine digits. Hence, there are \(\binom{5}{3} \cdot 9^2\) such integers.

Example \(\PageIndex{11}\label{eg:combin-11}\)

How many five-digit positive integers contain exactly three 7s?

Solution

Unlike the last example, the first of the five digits cannot be 0. Yet, the answer is not \(\binom{5}{3} \cdot 9 \cdot 8\). Yes, there are \(\binom{5}{3}\) choices for the placement of the three 7s, but some of these selections may have put the 7s in the last four positions. This leaves the first digit unfilled. The nine choices counted by 9 allows a zero to be placed in the first position. The result is, at best, a four-digit number. The correct approach is to consider two cases:

Case 1. If the first digit is not 7, then there are eight ways to fill this slot. Among the remaining four positions, three of them must be 7, and the last one can be any digit other than 7. So there are \(8\cdot \binom{4}{3}\cdot 9\) integers in this category.

Case 2. If the first digit is 7, we still have to put the other two 7s in the other four positions. There are \(\binom{4}{2} \cdot 9^2\) such integers.

Together, the two cases give a total of \(8\cdot \binom{4}{3}\cdot 9 + \binom{4}{2} \cdot 9^2 = 774\) integers.

hands-on Exercise \(\PageIndex{11}\label{he:combin-11}\)

Five balls are chosen from a bag of eight blue balls, six red balls, and five green balls. How many of these five-ball selections contain exactly two blue balls?

Example \(\PageIndex{12}\label{eg:combin-12}\)

Find the number of ways to select five balls from a bag of six red balls, eight blue balls and four yellow balls such that the five-ball selections contain exactly two red balls or two blue balls.

Solution

The keyword “or” suggests this is a problem that involves the union of two sets, hence, we have to use PIE to solve the problem.

• How many selections contain two red balls? Following the same argument used in the last example, the answer is \(\binom{6}{2} \binom{12}{3}\).
• How many selections contain two blue balls? The answer is \(\binom{8}{2} \binom{10}{3}\).

• According to PIE, the final answer is \[\binom{6}{2} \binom{12}{3} + \binom{8}{2} \binom{10}{3} - \binom{6}{2} \binom{8}{2} \binom{4}{1}.\] In each term, the upper numbers always add up to 18, and the sum of the lower numbers is always 5. Can you explain why?

• How many selections contain two red balls and 2 blue balls? The answer is \(\binom{6}{2} \binom{8}{2} \binom{4}{1}\).

Example \(\PageIndex{13}\label{eg:combin-13}\)

We have 11 balls, five of which are blue, three of which are red, and the remaining three are green. How many collection of four balls can be selected such that at least two blue balls are selected? Assume that balls of the same color are indistinguishable.

Solution

The keywords “at least” mean we could have two, three, or four blue balls. There are \[\binom{5}{2} \binom{6}{2} + \binom{5}{3} \binom{6}{1} + \binom{5}{4} \binom{6}{0}\] ways to select four balls, with at least two of them being blue.

hands-on Exercise \(\PageIndex{12}\label{he:combin-12}\)

Jerry bought eight cans of Pepsi, seven cans of Sprite, three cans of Dr. Pepper, and six cans of Mountain Dew. He want to bring 10 cans to his pal’s house when they watch the basketball game tonight. Assuming the cans are distinguishable, say, with different expiration dates, how many selections can he make if he wants to bring

1. Exactly four cans of Pepsi?
2. At least four cans of Pepsi?
3. At most four cans of Pepsi?
4. Exactly three cans of Pepsi, and at most three cans of Sprite?

The proof of the next result uses what we call a combinatorial or counting argument. In general, a combinatorial argument does not rely on algebraic manipulation. Rather, it uses the combinatorial significance of the situations to solve the problem.

\(\sum_{r=0}^n \binom{n}{r} = 2^n\)

Theorem \(\PageIndex{3}\)

Prove that \(\sum_{r=0}^n \binom{n}{r} = 2^n\) for all nonnegative integers \(n\).

Proof

Since \(\binom{n}{r}\) counts the number of \(r\)-element subsets selected from an \(n\)-element set \(S\), the summation on the left is the sum of the number of subsets of \(S\) of all possible cardinalities. In other words, this is the total number of subsets in \(S\). We learned earlier that \(S\) has \(2^n\) subsets, which establishes the identity immediately.

Summary and Review

• Use permutation if order matters, otherwise use combination.
• The keywords arrangement, sequence, and order suggest using permutation.
• The keywords selection, subset, and group suggest using combination.
• It is best to start with a construction. Imagine you want to list all the possibilities, how would you get started?
• We may need to use both permutation and combination, and very likely we may also need to use the addition and multiplication principles.

Exercises 

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

If the Buffalo Bills and the Cleveland Browns have eight and six players, respectively, available for trading, in how many ways can they swap three players for three players?

Solution

\(\binom{6}{3}\binom{8}{3}\).

 

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

In the game of Mastermind, one player, the codemaker, selects a sequence of four colors (the “code”) selected from red, blue, green, white, black, and yellow.

a) How many different codes can be formed?

b) How many codes use four different colors?

c) How many codes use only one color?

d) How many codes use exactly two colors?

e) How many codes use exactly three colors?

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

Becky likes to watch DVDs each evening. How many DVDs must she have if she is able to watch every evening for 24 consecutive evenings during her winter break?

a) A different subset of DVDs?

b) A different subset of three DVDs?
 

Solution

(a) at least 5 (b) at least 7

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

Bridget has \(n\) friends from her bridge club. Every Thursday evening, she invites three friends to her home for a bridge game. She always sits in the north position, and she decides which friends are to sit in the east, south, and west positions. She is able to do this for 200 weeks without repeating a seating arrangement. What is the minimum value of \(n\)?

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

Bridget has \(n\) friends from her bridge club. She is able to invite a different subset of three of them to her home every Thursday evening for 100 weeks. What is the minimum value of \(n\)?

Solution

10.

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

How many five-digit numbers can be formed from the digits 1, 2, 3, 4, 5, 6, 7? How many of them do not have repeated digits?

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

The Mathematics Department of a small college has three full professors, seven associate professors, and four assistant professors. In how many ways can a four-member committee be formed under these restrictions:

a) There are no restrictions.

b) At least one full professor is selected.

c) The committee must contain a professor from each rank.

Solution

(a) \(\binom{14}{4}\) (b) \(\binom{14}{4}-\binom{11}{4}\) (c) \(\binom{3}{2}\binom{7}{1}\binom{4}{1} +\binom{3}{1}\binom{7}{2}\binom{4}{1} +\binom{3}{1}\binom{7}{1}\binom{4}{2}\)

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

 A department store manager receives from the company headquarters 12 football tickets to the same game (hence they can be regarded as “identical”). In how many ways can she distribute them to 20 employees if no one gets more than one ticket? What if the tickets are for 12 different games?

Exercise \(\PageIndex{9}\label{ex:combin-09}\)

A checkerboard has 64 distinct squares arranged into eight rows and eight columns.

a) In how many ways can eight identical checkers be placed on the board so that no two checkers can occupy the same row or the same column?

b) In how many ways can two identical red checkers and two identical black checkers be placed on the board so that no two checkers of the same color can occupy the same row or the same column?

Solution

(a) \(8!\) (b) \(\binom{8}{2}\,P(8,2)\, \big[\binom{6}{2}\,P(8,2)+2\cdot7\cdot6\cdot7+7\cdot6\big]\)

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

Determine the number of permutations of \(\{A, B, C, D, E\}\) that satisfy the following conditions:

a) \(A\) occupies the first position.

b) \(A\) occupies the first position, and \(B\) the second.

c) \(A\) appears before \(B\).

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

A binary string is a sequence of digits chosen from 0 and 1. How many binary strings of length 16 contain exactly seven 1s?

Solution

\(\binom{16}{7}\).

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

In how many ways can a nonempty subset of people be chosen from eight men and eight women so that every subset contains an equal number of men and women?

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

A poker hand is a five-card selection chosen from a standard deck of 52 cards. How many poker hands satisfy the following conditions?

a) There are no restrictions.

b) The hand contains at least one card from each suit.

c) The hand contains exactly one pair (the other three cards all of different ranks).

d) The hand contains three of a rank (the other two cards all of different ranks).

e) The hand is a full house (three of one rank and a pair of another).

f) The hand is a straight (consecutive ranks, as in 5, 6, 7, 8, 9, but not all from the same suit).

g) The hand is a flush (all the same suit, but not a straight).

h) The hand is a straight flush (both straight and flush).

Solution

(a) \(\binom{52}{5}\) (b) \(4 \,\binom{13}{2}\,13^3\) (c) \(13\,\binom{4}{2}\binom{12}{3}\,4^3\) (d) \(13\,\binom{4}{3}\binom{12}{2}\,4^2\)

(e) \(13\,\binom{4}{3}\,12\,\binom{4}{2}\) (f) \(10\cdot(4^5-4)\) (g) \(4\,\big[\binom{13}{5}-10\big]\) (h) \(4\cdot10\)

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

A local pizza restaurant offers the following toppings on their cheese pizzas: extra cheese, pepperoni, mushrooms, green peppers, onions, sausage, ham, and anchovies.

a) How many kinds of pizzas can one order?

b) How many kinds of pizzas can one order with exactly three toppings?

c) How many kinds of vegetarian pizza (without pepperoni, sausage, or ham) can one order?

Exercise \(\PageIndex{15}\)

Write the numbers for the 8-row for Pascal's Triangle.

Solution

\[1 \qquad 8 \qquad 28 \qquad 56 \qquad 70 \qquad 56 \qquad 28 \qquad 8 \qquad 1\]     

Exercise \(\PageIndex{16}\)

In terms of selecting objects and Pascal's Triangle, explain why

(a) \(\binom{8}{0}=\binom{8}{8}\)

(b) \(\binom{8}{1}=8\)

(c) \(\binom{8}{2}\) is the third number in the 8-row rather than the second number

 

 

Exercise \(\PageIndex{17}\)

Use the 8-row of Pascal's Triangle to find

(a) \(\binom{8}{4}\)

(b) \(\binom{8}{6}\)

(c) \(\binom{8}{5}=\binom{?}{?}\)

Solution

(a) 70          (b) 28        (c) \(\binom{8}{5}=\binom{8}{3}\)