Counting Practice

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.

Problem: Take-away

Suppose that you have a deck of $c$ playing cards.

1. 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.

2. 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?)

3. 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.

4. 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\times (c-1)\times (c-2)\times (c-3)\times (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: 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.

Problem: Alternative

In the reading, you learned that the number of $k$-sized (unordered) sets drawn from $n$ objects is given by:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{(n{)}_k}{k!}.$$

If you have seen the combination (or "choose") operator before, you may not have learned that it was equal to this quantity. Instead, you likely learned that:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}.$$

In a few sentences, justify or "explain" this second formula in terms of overcounting. What are you overcounting and what are you removing from that overcount to arrive at the desired final quantity?

Problem: Poker Hands

In variations of poker, players receive a five-card hand from a deck of 52 player cards. Recall that each of the 52 cards has a rank and suit:

• The ranks range from 2--10, Jack (J), Queen (Q), King (K), and Ace (A), 13 ranks overall.
• The suits are drawn from spades, clubs, hearts, and diamonds.

Give combinatorial descriptions for each of the following values.

1. The total number of possible poker hands. Remember that a poker hand is an unordered collection of five cards.

2. The total number of possible poker hand that contains exactly two pairs. A pair is a pair of the cards with the same rank, e.g., the 8 of spades and hearts.

   Rather than computing this quantity by determining the ways of drawing the first card of the hand, the second card, and so forth, which will lead to a series of conditional choices, consider the following strategy instead:

   • Choose 2 ranks to participate in the pair.
   • Choose 2 suits from each rank to participate in the pair.
   • Choose a remaining rank and a suite from that rank as the final card.

3. The total number of possible poker hands that are a full house. A full house is a hand consisting of a three-of-a-kind and a pair. A three-of-a-kind is a pair but with three cards of the same rank instead of two.

4. The total number of possible poker hands that are a four-of-a-kind, e.g., the Ace of spades, clubs, hearts, and diamonds.

5. The total number of possible poker hands that are a single pair. A single pair is where two of the cards have the same rank, e.g., the Jack of spades and hearts. Note that when a hand contains a single pair, it should not contain other, better hands, e.g., two pairs, a three-of-a-kind, or a four-of-a-kind.

6. The total number of possible poker hands that are a flush where all five cards are of the same suit, e.g., all spades cards. Like a pair, this quantity should also not include better hands: a straight flush (where you have a flush and the cards are in consecutive rank, e.g., 5-6-7-8-9) and a royal flush (a straight flush that starts with 10, i.e., 10-J-Q-K-A).

Check your work by observing that your combinatorial descriptions produce these quantities:

• The number of poker hands: 2,598,960.
• Two pairs: 123,552.
• Full house: 3,744.
• Four-of-a-kind: 624.
• Pair: 1,098,240.
• Flush: 5,108.

Problem: Deceptive

With five-card poker hands, a royal flush is a straight flush that runs 10-J-Q-K-A. The following combinatorial description denotes the number of royal flushes:

$$\left(\genfrac{}{}{0ex}{}{4}{1}\right).$$

In a sentence or two, justify this combinatorial description.

Problem: Shades of Pre-registration

Suppose that you are building a schedule from among $k$ distinct possible courses. Give combinatorial descriptions of each of the cardinalities described below. For each description, check your work by instantiating a concrete set of courses, and demonstrating that your description works for each such concrete example.

1. The number of five course schedules (i.e., sequences of courses) you can build from these courses.

2. The number of sets of three courses (i.e., unordered collections) you can build from these courses.

3. The number of four course schedules that contain both Basket Weaving or Underwater Knitting.

   (Hint: choose positions for Basket Weaving and Underwater Knitting. This implies where the remaining two courses will go. Finally choose which courses go into those remaining two slots.)

4. The number of four course schedules that do not contain both Basket Weaving and Underwater Knitting.

   (Hint: leverage your answer to the previous part!)

5. The number of six course schedules that include Calculus I and Computer Science I but do not place Calculus I after Computer Science I in the schedule.

   (Hint: similarly to the previous part, choose positions for the two named courses. But here, you need to remove the possibilities that get the order these courses swapped.)

6. (Bonus Problem) The number of six course schedules that include Calculus I and Computer Science I but do not place Calculus I immediately after Computer Science I in the schedule.

   (Hint: unlike the previous problem, we only want to ensure that Calc I does not appear in the next time slot after CS I. How can we break up the possible positions of the two courses to get a handle on these situations? How do we then account for overcounting?)