COMBINATORICS The Chart: Building Blocks of Counting -------------------------------------- Here are the 4 different categories of things we have tools to count _directly_, without breaking into parts or splitting into cases: k choices/boxes _____________________________________ | unordered | ordered | | (nondistinct) | (distinct) | ==================|=================|==================| | with unlimited | didn't learn. | k | | repetition | not on exam. | n x ... x n = n | pool of n |_________________|_________________|__________________| objects/balls | | n! | n x ... x (n-k+1)| | no repetition |( n ) = -------- | n! | | (all distinct) |( k ) (k-n)!k! | = ------- | | | | (n-k)! | |_________________|_________________|__________________| Chiseling Problems into Building Blocks --------------------------------------- In most problems, the things we want to count do not fall neatly into one of the above categories, and we must therefore break up the problem or relabel things in a way to make them fit. Here are some guidelines.... Complication: CONSTRAINED REPETITION in POOL. -Repetition occurs in exactly specified amounts, like finding anagrams of MISSISSIPPI (1 M, 2 Ps, 4 Ss, 4Is). Solutions: -Add extra labels to make the repeated guys distinct, and then divide the final answer by the number of reorderings of these extra labels (like 11!/(4!2!2!1!) for anagrams of MISSISSIPPI). -Reverse our notion of what things we regard as the objects (or balls) in our POOL with what things we regard as CHOICES (or boxes). Thus MISSISSIPPI, instead of having 11 position-boxes for a pool of M, P, S, and I, could have 4 letter-boxes (M of size 1, P of size 2, S of size 4, I of size 4) for a pool of 11 position-balls 1, 2, ..., 11. Using binomial coefficients, there are (11 choose 4, 4, 2, 1) = 11!/(4!4!2!1!) ways to distribute these 11 positions among these 4 letter-boxes. Likewise, for flipping coins, it is easiest to have a "head-box of size 4" and a "tail-box of size 6" into which we distribute 10 position-balls 1, 2, ..., 10 from our pool. This gives us (10 choose 4, 6) = (10 choose 4) = (10 choose 6) = 10!/(4!6!) ways to flip 10 coins and get 4 heads and 6 tails. Complication: FIXED POOL, but NONCONSTANT ClASSIFICATION of CHOICES. -The number of things we want of each type is not fixed, like "either 7 heads and 5 tails OR 8 heads and 4 tails". or "a committee with 19 people including at least 1 teacher." Solution: -Split problem into CASES. (And in the end, glue by ADDING.) Either this happens OR this happens OR this happens.... Complication: SEQUENCE of CHOICES with DIFFERENT POOLS -You have POOL_1, CHOICES_1; POOL_2, CHOICES_2; POOL_3, CHOICES_3; and the combination of all 3 of these makes one selection. Examples: -Pick 3 letters, 3 numbers, and 1 symbol for a license plate, out of some given collection of letters, numbers, and symbols. -Pick 1 scarf, 1 shirt, 1 skirt, and 2 bracelets for an outfit, out of some given collection of scarves, shirts, skirts,.... -Make a hand of cards with 2 queens, and 3 number cards with distinct numbers, and no aces. -Walking only north or east on a grid, make a journey that goes from A to B, then above a diagonal from B to C, then from C to D, given the eastward and northward distances for the first leg, second leg, and third leg of the journey. Solution: -Break problem into PARTS. (And in the end, glue by MULTIPLYING.) Well, this happens, AND that happens, AND this happens. Mortar: Gluing together a Solution ---------------------------------- The three above strategies tell how either to relabel or break up the problem until it (or its pieces) fit into the chart above. The last part is to glue these results togther Glue: ----- ADDITION - Count up SEPARATE CASES (5 heads OR 6 heads). SUBTRACTION - EXCLUDE cases or REMOVE OVERLAP cases after adding. MULTIPLICATION - Combine PARTS of a single case (3 hats AND 2 gloves). Example in Chiseling: Homework 8, problem 3 ------------------------------------------- This was a great example of a problem where people gave answers corresponding to the wrong parts of the chart above. In problem 8.3, to count the total possible number of sequences in bills in the lineup, we have 20 positions for 10 $5's and 10 $10's. This has constrained repetition, so we have two options to fix things. Trick 1: Add labels to get 10 distinct $5's and 10 distinct $10's. for 20 distinct positions. Then from the lower-right corner of the chart, we have 20! choices. We must then divide by the 10! orderings for the $5's and the 10! orderings for the $10's, to get 20!/(10!10!). Trick 2: Of 20 positions, choose a collection of 10 in which to put the 10 $5 bills. This puts us in the lower left-hand corner of the chart, so we have (20 choose 10) or 20!/(10!10!). Many students on the homework instead wrote 20! or 2^20. Study the interpretation of these numbers according to the chart above to see why 20! or 2^20 is incorrect.