EF Basics

🔗

Section 22.2 Basics

🔗

combination: 🔗
a finite subset of a given set
$C (n, k)$: 🔗
the number of combinations of size $k$ taken from a set of size $n$
$C_{k}^{n},$ ${_{n} C}_{k}$: 🔗
alternative notation choices for $C (n, k)$
choose function: 🔗
the function $(n, k) \mapsto C (n, k)$

🔗

Checkpoint 22.2.1.

🔗

What are the domain and codomain of the choose function?

🔗

Warning 22.2.2.

🔗

Permutations and combinations are different. A permutation is a bijection from a set to itself. Given a fixed chosen ordering of the set elements in a list (considered as inputs), a permutation is essentially an re-ordering of the set elements into a second list, to line up outputs with inputs. So order matters in a permutation. On the other hand, a combination is just a set, and order does not matter in a set, only membership matters. That is, two listings of some of the elements from a set are the same combination if all the same elements are listed, regardless of the order of the elements in the two lists. So order does not matter in a combination.

🔗

Theorem 22.2.3. Computing $C (n, k)$ .

🔗

We have

C (n, k) = \frac{P (n, k)}{k!} = \frac{n!}{k! (n - k)!} .

🔗

Proof.

Suppose

| A | = n .

Using the solution to Worked Example 22.1.1 as a model for our proof, we note that each ordered list of

k

elements taken from

A

defines a combination from

A,

but different orderings of the same

k

elements yield the same combination. Define two permutations to be “equivalent” if they are orderings of the same elements, so that equivalent permutations are associated to the same combination. Since there are

k!

elements in each equivalence class of permutations, we may apply the Division Rule to obtain

\begin{aligned} C (n, k) & = # {combinations} \\ = \frac{# {permutations}}{# {equivalent permutations in each class}} \\ = \frac{P (n, k)}{k!} . \end{aligned}

Finally, to obtain the rightmost formula in the statement of the theorem, we just need to combine the above formula relating

C (n, k)

and

P (n, k)

with the formula for

P (n, k)

from Theorem 21.4.3.

🔗

Corollary 22.2.4.

🔗

We also have

C (n, n - k) = C (n, k) .

🔗

Proof.

Calculate

C (n, n - k) = \frac{n!}{(n - k)! (n - (n - k))!} = \frac{n!}{(n - k)! k!} = C (n, k) .

🔗

Remark 22.2.5. Choosing is equivalent to rejecting.

🔗

Interpret this last corollary as follows: from a set of

n

objects, choosing to include

k

elements in a combination is equivalent to choosing

n - k

objects to reject.

🔗

Worked Example 22.2.6. Choosing ice cream.

🔗

How many double-scoop ice cream combinations are possible if the local ice cream shop features thirty-one different flavours? (Note: Only flavour combinations are relevant, not which flavour goes on the cone first.)

Solution.

From thirty-one flavours, there are

C (31, 2) = \frac{31!}{2! 29!} = \frac{31 \cdot 30}{2} = 31 \cdot 15 = 465

possibilities for double-scoop cones with two distinct flavours. However, there are an additional

31

possibilities for double-scoop cones with two scoops the same flavour. So the answer is

465 + 31 = 496 .

🔗

Worked Example 22.2.7. Counting colour patterns (revisited).

🔗

How many different colour patterns can we achieve by placing three red bottles and five blue bottles on a shelf? (Assume the bottles are indistinguishable except by colour.)

Solution.

There are

8

possible positions in which to place a bottle. To create an arbitrary colour pattern, we can choose

3

of the positions to be filled by red bottles, then place blue in the remaining positions. So the answer is

C (8, 3) = \frac{8!}{3! 5!} = 56 .

🔗

Remark 22.2.8.

🔗

Compare the above solution for Worked Example 22.2.7 with the solution for the identical problem in Worked Example 21.3.8.

🔗

Worked Example 22.2.9. Choosing with constraints.

🔗

How many ways are there to choose a team of five people from a pool of six first-year students and four senior students if the team must have three first-years and two seniors?

Solution.

Choose the seniors for team, then the first-years (or vice-versa). Applying the Multiplication Rule to these independent, consecutive tasks yields answer

C (4, 2) \cdot C (6, 3) = (\frac{4!}{2! 2!}) (\frac{6!}{3! 3!}) = 120 .

🔗

Worked Example 22.2.10. Creating several non-overlapping combinations.

🔗

How many ways are there to choose three teams of four members each from a pool of twenty people, where no person can be on more than one team?

Solution 1.

Choose the first team (

C (20, 4)

ways), then the second team (

C (16, 4)

ways), then the third team (

C (12, 4)

ways). Applying the Multiplication Rule yields a total of

C (20, 4) \cdot C (16, 4) \cdot C (12, 4) = (\frac{20!}{4! 16!}) (\frac{16!}{4! 12!}) (\frac{12!}{4! 8!}) = \frac{20!}{8! (4!)^{3}} .

possible teams. However, the way in which we have constructed our teams has imposed an order on the collection of teams (first, second, and third team), when there is no reason to assume such structure. Given a collection of teams, re-ordering the teams themselves (not the people within each team) produces an equivalent collection of teams by membership. As there are

3!

ways to reorder the three teams, applying the Division Rule gives us a final answer of

\frac{20!}{3! 8! (4!)^{3}} .

Solution 2.

Initially choose the twelve people who will make up the three teams, but without yet assigning anyone to a particular team (

C (20, 12)

ways). Then, from this reduced pool of candidates, choose the first team (

C (12, 4)

ways) and the second team (

C (8, 4)

ways). The third team will now consist of the remaining four people from the twelve initially chosen. The Multiplication Rule gives a preliminary total of

C (20, 12) \cdot C (12, 4) \cdot C (8, 4) = (\frac{20!}{12! 8!}) (\frac{12!}{4! 8!}) (\frac{8!}{4! 4!}) = \frac{20!}{8! (4!)^{3}} .

But as in the first solution above, we need to account for the fact that we have artificially ranked teams as first, second, and third. Applying the Division Rule gives us a final answer of

\frac{20!}{3! 8! (4!)^{3}} .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 22.2 Basics

Checkpoint 22.2.1.

Warning 22.2.2.

Theorem 22.2.3. Computing $C (n, k)$ .

Proof.

Corollary 22.2.4.

Proof.

Remark 22.2.5. Choosing is equivalent to rejecting.

Worked Example 22.2.6. Choosing ice cream.

Worked Example 22.2.7. Counting colour patterns (revisited).

Remark 22.2.8.

Worked Example 22.2.9. Choosing with constraints.

Worked Example 22.2.10. Creating several non-overlapping combinations.

Section 22.2 Basics

Checkpoint 22.2.1.

Warning 22.2.2.

Theorem 22.2.3. Computing C(n,k).

Proof.

Corollary 22.2.4.

Proof.

Remark 22.2.5. Choosing is equivalent to rejecting.

Worked Example 22.2.6. Choosing ice cream.

Worked Example 22.2.7. Counting colour patterns (revisited).

Remark 22.2.8.

Worked Example 22.2.9. Choosing with constraints.

Worked Example 22.2.10. Creating several non-overlapping combinations.

Theorem 22.2.3. Computing $C (n, k)$ .