Get out your fingers! In this lab, we’re going to practice writing combinatorial descriptions using our fundamental counting principles. Recall that a combinatorial description is an unsimplified arithmetic formula whose structure communicates how we’ve decomposed a set according to our counting principles. Throughout, give combinatorial descriptions for each of the desired quantities when appropriate.
You should also check your work by instantiating your combinatorial descriptions to small, artificial sets and then hand-constructing the quantities in question. In some of these problems, we’ll ask you to show your check by giving your instantiation and hand-constructed sets.
Problem 1: Take-away
Suppose that you have a deck of \(c\) playing cards.
Consider drawing a sequence of three cards from the deck where the order of the cards is relevant. However, you form this sequence by drawing a card and then putting it back in the deck, i.e., with replacement. Give a combinatorial description for the number of possible three-card sequences you could draw in this manner.
Now consider three-card sequences from the deck but without replacement. That is, each drawn card stays out of the deck. Give a combinatorial description for the number of possible three-card sequences you could draw in the manner and show your check that your description is correct.
(Hint: The description for this part should be different from the description for the previous part! Consider drawing one card from the deck. How many cards remain if you don’t replace this initial card?)
What happens when you mix the two approaches? Suppose that you:
- First draw 2 cards with replacement.
- Next, draw 2 cards without replacement.
- Finally, draw 1 card with replacement.
Give a combinatorial description of the number of such sequences of five cards.
Suppose you are interested in counting the number of five-card hands you can draw from the deck. We might suggest that the number of such hands is:
\[ c × (c-1) × (c-2) × (c-3) × (c-4). \]
Think about what it means to have a hand of cards in a card game and what you would view as two equivalent hands. With this in mind, in a sentence or two, explain why this combinatorial description does not accurately describe the situation at hand.
Problem 2: Dress-down
Suppose that we have \(a\) hats, \(s\) shirts, \(p\) pairs of pants, and \(h\) pairs of shoes in our closet.
Give a combinatorial description of the total number of clothing articles in our closet.
Give a combinatorial description of the total number of total number of outfits we can put together (consisting of a hat, shirt, pants, and shoes). Also show your check that your description is correct.
Suppose that of our \(h\) pairs of shoes, \(f\) of them are flip-flops and \(h - f\) of them are loafers. When we wear flip-flops, we don’t wear a shirt and when we wear loafers, we wear two hats. Give a combinatorial description of the total number of outfits we can put together in this situation.
Finally, consider pairing up the \(h\) hats and \(p\) shoes and then giving away those pairs of hats and shoes to needy children. Call one of these subsets a giveaway collection. Give a combinatorial description of the number of different such giveaway collections you can form in this manner.
(Hint: another way to think of this problem is as follows. You first form up all the possible pairs of hats and shoes from your collection. Then you give away a subset of those pairs. The problem is asking you how many such subsets exist.)
Problem 3: The Perfect Fit
Suppose that a software company was hiring individuals based on the following criteria:
- Knowledge of Racket programming.
- Can write an inductive proof.
- Is no taller than 175 cm.
The company, through pre-screening, ensures that all of their candidates possess at least one of these qualities. This hiring season, the company noted of their \(c\) candidates:
- \(x\) knew how to program in Racket.
- \(y\) knew how to write an inductive proof.
- \(z\) were no taller than 175 cm.
- \(a\) candidates fulfilled all three criteria.
The company ultimately decided to hire candidates that satisfied exactly two of these criteria.
Use the principle of inclusion-exclusion to derive an unsimplified combinatorial description of this quantity and show your check that your description is correct.