Combinations

Section 9.5 Combinations

In this section we look at how to count subsets of a set and define the mathematical concept of a combination.

Definition 9.5.1.

Let

n, r

be nonnegative integers with

r \leq n .

r

-combination of a set of

n

elements is the number of subsets of size

r

that can be chosen from a set of

n

elements. We denote it

(\binom{n}{r}),

which is read “

n

choose

r .

”

🔗

Other common notation are

C (n, r),

n C r .

We will use

(\binom{n}{r})

notation, which we first saw in Section 5.1. For example,

(\binom{5}{4})

is the number of subsets of size 4 chosen from a set of 5 elements.

🔗

Since order does not matter in a set, the order in which we choose elements of a set does not matter. Recall, when counting permutations, the order in which we chose our elements did matter. We can use what we know about permutations, though, to count combinations.

🔗

We can calculate combinations by first finding all the

r

-permuatations of a set, then dividing by all the possible orderings of that subset:

\frac{P (n, r)}{r!} .

This can be rewritten to be the standard formula for calculating combinations:

(\binom{n}{r}) = \frac{n!}{r! (n - r)!} .

🔗

Note, since

0! = 1,

(\binom{n}{0}) = 1

and

(\binom{0}{0}) = 1 .

This also makes sense with the definition, as there is only one set with 0 elements, the empty set.

🔗

Activity 9.5.1.

Calculate

(\binom{6}{2})

and

(\binom{6}{4}) .

🔗

Activity 9.5.2.

Calculate

(\binom{4}{0})

and

(\binom{4}{4}) .

🔗

Example 9.5.2. Combinations versus Permutations.

Suppose you want to choose a group of 3 students in a class of 15 for a group project. How many ways can you choose the group?

🔗

We use combinations:

(\binom{15}{3}) .

It does not matter if a member was chosen first, second, or third, they would still be a member of the group. Thus, there are

\frac{15!}{3! 12!} = 455

ways to choose a group of 3.

🔗

Now suppose you want to choose a group of 3 students in a class of 15 for a group project, but the first student chosen will be the note-taker, the second will be the presenter, the third will manage the discussion. How many ways can you choose the group?

🔗

We use permutations:

P (15, 3) .

Now it does matter if a member was chosen first, second, or third, as each member has a different role. Thus, there are

\frac{15!}{12!} = 2730

ways to choose a group of 3 where the members’ roles are defined.

🔗

In deciding whether to use combinations or permutations, you need to decide whether order matters. For combinations, order doesn’t matter; think about choosing subsets. For permuations, order does matter; think about choosing ordered lists.

🔗

Recall, a binary string is just a list of 0s and 1s

🔗

Example 9.5.3. Binary Strings.

How many binary strings of length 5 can have exactly 2 ones?

🔗

We can think of forming a binary string with 2 ones as a list of 5 places where we need to choose 2 places for the ones. Once we’ve done that, the other places must have 0’s. Thus, we have five places and choose 2:

(\binom{5}{2}) = \frac{5!}{2! 3!} = 10.

🔗

How many binary strings of length 5 can have at most 2 ones?

🔗

Here we can count the strings with 2 ones, 1 one, and 0 ones. We add them since the strings with different numbers of ones are disjoint:

(\binom{5}{2}) + (\binom{5}{1}) + (\binom{5}{0}) = 10 + 5 + 1 = 16.

🔗

Activity 9.5.3.

How many binary strings of length 7 have exactly 3 ones?

🔗

Hint.

Think of this as a list of 7 digits. How many ways are there to place the ones?

🔗

Activity 9.5.4.

How many binary strings of length 7 have at most 2 ones?

🔗

Hint.

First count how many have 0 ones, then 1 one, then 2 ones. Should you use the addition rule or multiplication rule to find the total number?

🔗

Example 9.5.4. Rearranging Letters.

How many ways are there to order the letters in the word “letter”?

🔗

We can think of the string of letters as 6 places where we can choose to put letters. First we can choose the place to put the “l”: we have 6 places, we need to choose 1:

(\binom{6}{1}) .

🔗

Next we choose the places to put the two “e”s: we now only have 5 places (since one has the l), we need to choose 2:

(\binom{5}{2}) .

🔗

We continue in this way, with 3 places to put the two “t”s:

(\binom{3}{2}),

and one remaining place to put the “r”:

(\binom{1}{1}) .

🔗

Since placing each letter is a process (we don’t have a complete string until we have placed all the letters), we need to use the multiplication rule:

(\binom{6}{1}) \cdot (\binom{5}{2}) \cdot (\binom{3}{2}) \cdot (\binom{1}{1}) = 6 \cdot 10 \cdot 3 \cdot 1 = 180.

🔗

There is another way to calculate the previous example.

🔗

Example 9.5.5. Alternate Rearranging Letters.

How many ways are there to order the letters in the word “letter”?

🔗

We can think of the string of letters as 6 places where we can choose to put letters. First we can think of all the letters as distinct. Then we have 6 letters to choose for the first place, 5 for the second, 4 for the third, etc. Thus we have

6!

ways to place 6 distinct letters.

🔗

But the letters are not distinct, so we need to divide by the number of ways we over-counted. For each permutation we just counted, switching the two “e”s gives us the same word, so we need to divide by the number of ways to rearrange the two “e”s:

2! .

Similarly, we need to divide by equivalent arrangements of the two “t”s:

2! .

🔗

Putting this together we have

\frac{6!}{2! 2!} = 180.

🔗

Activity 9.5.5.

How many ways are there to order the letters in “book”?

🔗

Hint.

First place all the “b”s--how many ways can you do this? Then count how many ways to place all the “o”s, then all the “k”s.

🔗

Activity 9.5.6.

How many ways are there to order the letters in “infinity”?

🔗

Example 9.5.6. Forming Committees.

A class has 13 students. How many ways can a group of 7 be chosen?

🔗

Answer.

(\binom{13}{7})

🔗

Suppose in this class of 13 there are 7 juniors and 6 seniors.

🔗

How many groups of 7 can be chosen that contain 4 juniors and 3 seniors?
🔗

Answer.

$(\binom{7}{4}) \cdot (\binom{6}{3}),$ first choose the juniors then the seniors.
🔗

🔗

🔗
How many groups of 7 can be chosen so that there is at least one senior?
🔗

Answer.

$(\binom{13}{7}) - (\binom{7}{7}),$ all the possible groups minus the groups with no seniors.
🔗

🔗

🔗
How many groups of 7 can be chosen so that there are at most 3 juniors?
🔗

Answer.

$(\binom{7}{1}) \cdot (\binom{6}{6}) + (\binom{7}{2}) \cdot (\binom{6}{5}) + (\binom{7}{3}) \cdot (\binom{6}{4}),$ count the groups of one junior and 6 seniors, two juniors and 5 seniors, three juniors and 4 seniors. Note, there are no groups with no juniors.
🔗

🔗

🔗
How many groups of 7 can be chosen if two people refuse to work together?
🔗

Call the two people A and B.
🔗

Find the number of groups with A and not B: $(\binom{11}{6}) .$ Note, we only need to choose 6 out of 11 since we know A is in the group and B is not, so we just need to choose the other 6 members.
🔗

Similarly, find the number of groups with B and not A: $(\binom{11}{6}) .$
🔗

Now, find the number of groups with neither A nor B: $(\binom{11}{7}) .$ Note, we need to choose 7 out of 11 since we know A and B cannot be chosen.
🔗

Since the sets of each type of group (with A, with B, with neither) are disjoint, we use the addition rule:

$(\binom{11}{6}) + (\binom{11}{6}) + (\binom{11}{7}) .$

🔗

🔗

🔗

Reading Questions Check Your Understanding

1.

Calculate the number of 4-combinations of a set with 6 elements.

🔗

2.

Calculate

(\binom{7}{4}) .

🔗

3.

Calculate

(\binom{7}{2}) .

🔗

4.

Calculate

(\binom{7}{1}) .

🔗

5.

Calculate

(\binom{7}{7}) .

🔗

6.

Calculate

(\binom{7}{0}) .

🔗

7.

Find the number of binary strings of length 7 with 4 zeros.

🔗

8.

Find the number of binary strings of length 7 with at most 2 zeros.

🔗

9.

Find the number of strings that can be formed from the letters in the word “calculate”.

🔗

Exercises Exercises

1.

Calculate

🔗

$(\binom{6}{0})$
🔗

🔗
$(\binom{6}{1})$
🔗

🔗
$(\binom{6}{2})$
🔗

🔗
$(\binom{6}{3})$
🔗

🔗
$(\binom{6}{4})$
🔗

🔗
$(\binom{6}{5})$
🔗

🔗
$(\binom{6}{6})$
🔗

🔗

🔗

2.

A student council consists of 15 students.

🔗

In how many ways can a committee of 6 be selected from the membership of the council?
🔗

🔗
Two council members have the same major and are not permitted to serve together on a committee. How many ways can a committee of 6 be selected from the membership of the council?
🔗

🔗
Two council members always insist on serving together on a committee. If they can’t serve together, they won’t serve at all. How many ways can a committee of 6 be selected from the membership of the council?
🔗

🔗
Suppose the council contains 8 seniors and 7 juniors.
🔗
1. How many committees of six contain three seniors and three juniors?
  🔗
  
  🔗
2. How many committees of six contain at least one junior?
  🔗
  
  🔗
🔗
🔗
Suppose the council consists of three freshmen, four sophomores, three juniors, and five seniors. How many committees of eight contain two from each class?
🔗

🔗

🔗

3.

An instructor gives an exam with fourteen questions. Students are allowed to choose any ten questions to answer.

🔗

How many different choices of ten questions are there?
🔗

🔗
Suppose six questions require proof and eight do not.
🔗
1. How many groups of ten questions contain four that require proof and six that do not?
  🔗
  
  🔗
2. How many groups of ten questions contain at least one that requires proof?
  🔗
  
  🔗
3. How many groups of ten questions contain at most three that require proof?
  🔗
  
  🔗
🔗
🔗
Suppose the exam instructions specify that at most one of the questions 1 and 2 may be included among the ten. How many different choices of the ten questions are there?
🔗

🔗
Suppose the exam instructions specify that either questions 1 and 2 are to be included among the ten or neither is to be included. How many different choices of ten questions are there?
🔗

🔗

🔗

4.

A coin is tossed ten times. In each case the outcome (H or T) is recorded.

🔗

What is the total number of possible outcomes of the coin tossing experiment?
🔗

🔗
In how many of the possible outcomes are exactly five heads obtained?
🔗

🔗
In how many of the possible outcomes are at least eight heads obtained?
🔗

🔗
In how many of the possible outcomes is at least one head obtained?
🔗

🔗
In how many of the possible outcomes is at most one head obtained?
🔗

🔗

🔗

5.

A binary or bit string consists of just 0’s and 1’s. A bit string of length 16 is called a 16-bit string.

🔗

How many 16-bit strings contain exactly seven 1’s?
🔗

🔗
How many 16-bit strings contain at least thirteen 1’s?
🔗

🔗
How many 16-bit strings contain at least one 1?
🔗

🔗
How many 16-bit strings contain at most one 1?
🔗

🔗

🔗

6.

Consider the word

N I N E T E E N T H

🔗

How many distinguishable ways are there to order the letters in the word $N I N E T E E N T H ?$
🔗

🔗
How many distinguishable ways are there to order the letters in the word $N I N E T E E N T H$ if it must begin with $I$ and end with $E ?$
🔗

🔗
How many distinguishable ways are there to order the letters in the word $N I N E T E E N T H$ if the letters $H I$ must be next to each other in order?
🔗

🔗

🔗

7.

In Morse code, symbols are represented by variable-length sequences of dots and dashes. For example,

A = \cdot -, 1 = \cdot - - - -, ? = \cdot \cdot - - \cdot \cdot .

How many different symbols can be represented by sequences of seven or fewer dots and dashes?

🔗

You have attempted 1 of 10 activities on this page.

🔗

Prev Top Next