Combinatorics

Reference: FOCS Ch. 4, first half; 2nd half is related: probability. Look For: Readings! On the course Web Page! Hint: Foundations of Computer Science (FOCS) , by Aho and Ullman.

Why? First, It's vital to count things. Better, Combx is really fun and basically simple. Not advanced math at all, just a set of ways to think about the problem. Usually only * and + with integers!.

Useful? Well, if you know how many poker hands there are and you know how many ways to get a pair, then the probability of being dealt a pair is pairs/hands. The odds of getting a pair is pairs/(hands-pairs). Easy to convert between odds and probabilities...

The Assignment Operation

Given list of items, each of which is assigned any one of a fixed set of values (duplicate values may be used). How many assignments can be made? E.g. how many different 8-long, 0-1 bitstrings are there?

How To: The number of ways to assign any one of k values to n items is kⁿ. Prove by induction. Or think: k values to choose for 1st assignment, for each choice there are k ways to choose the second...
Warning: It's no-of-values (k) to the no-of-things (n), not the other way around. Easy to get it backward.

So there are 2⁸ different bytes, from 00...00 to 11...11.

You're headed to Muchas Tapas, which has 19 tapas choices. You're going to choose three dishes, not necessarily all different. Plus you've got a coupon for a pitcher of either Cervezas Alhambra or Estrella Galicia. Hell, why not?...you can skip dessert. How many dinner choices do you have? Back-of-envelope: 2*.85*8000 = 13,600: Why? In factual act, it's 13,718: Again, Why?

Permutations

Given n distinct objects, how many ways can they be ordered (placed in a line?). E.g. if we want to sort a list, how many different inputs (initial orders of the list) can there be? Call that number Π(n).

How To: Π(n) = n!= n(n-1)(n-2)...3.2.1, n≥1. Proof by induction. Or just think: n ways to choose 1st place, leaves n-1 ways to choose 2nd place for each choice of first, or n(n-1) ways to choose the first two items...etc. Last item: 1 choice.

Big finish... from just this you can prove a general lower time bound (best possible performance) for ALL sorting algorithms that work by comparing elements, AND you don't need to know ANY sorting algorithms to prove it! (FOCS 163-4).

Ordered Selections

How many ways can we select m items from a set of n items and put the selected items in some order? This is either a simple extension of Permutations, or a simple application of Assignments.

How To Case I: We talk of "selection with replacement" when we can select the "same thing" more than once, as in the 0's and 1's and tapas choices in the Assignments section. In that case, the ordered selection problem is just a case of assignment, so we get n^m.

How To Case II: In "selection without replacement", once an item is picked, it disappears from the list of pickable items. In that case, we'd expect n choices for the 1st item, (n-1) for 2nd, down to (n-m+1) for the mth. Or the m-term, "partial factorial"-looking
n(n-1)...(n-m+1). Or the elegant n!/(n-m)!.

Unordered Selections

How many ways to select m items out of n total, disregarding differences of order?

This is a key, highly-useful concept. Notation I like is the binomial coefficient, which looks something like

  n
(   )
  m

only with big parens enclosing the upper and lower values. In the combinatorics context this would be read "n choose m". This value is a binomial coefficient, and is often called one. Here in html, we can use C(n,m) -- "The combinations of n things taken m at a time" -- one of many notational variants using C,m, and n.

How To: C(n,m) = n!/[(n-m)!m!].

Why? First, we want to choose m items out of n. By last section, the elegant way to count the choices, with every order being different, is n!/(n-m)!. BUT orders AREN'T different, so we definitely overcounted. We must divide by the number of ways to order m items, or m!, which gives the formula above. C(n,0) is 1, as is C(n,n).

Pascal's Triangle

Raise (x+1) to successive powers and you get 1, 1x+1, 1x²+2x +1, 1x³+ 3x²+3x +1... Pitch the x's and put the (binomial) coefficients in a table:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

Voici Pascal's triangle. The numbers in the mth column of the nth row are C(n,m). What's the 'rule' for computing its entries? Justify it semantically (cf FOCS p.172), getting an inductive proof. Prove it by induction using the "factorials formula".

Knuth vol. I (Chapter 1.2) is a wonderful resource for some combinatorics and especially bin coef topic, and Pascal's triangle is a treasure-trove of pretty results. Did you notice that the sum of each row is 2ⁿ? Super-easy proof by induction using the "upstairs neighbors rule" for computing C(n,m). There are properties of the diagonals, I don't know what all...And many identities.

Orderings with Identical Items

How many different orders are possible if some items are identical? E.g. there are 3!=6 orders of the letters A, L, L... but only 3 different resulting "words" (where both L's are the same).

How To: With n items divided into k groups of sizes i₁, i₂, ..., i_k; items within groups are not distinguishable but those in different groups are. How many orders of the n items?
n!/[i₁! i₂!... i_k!].
Prove by induction. Or, think: suppose we label each group member with unique ID. So we get (number-in-group)! possible orders. Now we need to divide out the number of orders of the kth group, for all k. There are i_k! orders for group k. Have to divide by (the product of) them all. Obvious extension of previous ideas.

Distributions of Objects to Bins

How many ways can we divide up n identical objects to distribute into m different bins? I.e. How many distributions are there?

It sometimes takes a little effort to see our problem using this bin metaphor. An easy example: we have three kids and four apples. How many ways are there to distribute apples amongst kids? Here kids are clearly the bins.

The Trick: Pick a symbol, say A for apple, to represent the objects. So we have four A's in this problem. Let * be a "bin-separator" symbol, so we need two for three bins. Notice that every string of 4 A's and 2 *'s represents a different distribution. E.g. AAAA** says kid One gets 'em all. A*A*AA says One gets 1, Two gets 1, and Three gets 2.

How and Why To: For n items, m bins: string is n+m-1 long with n A's and m-1 *s to be distributed between the A's. Choose any n positions for the A's and the rest get the *s. OR choose any m-1 positions for the *'s and the rest get A's. Thus get
C(n+m-1, n) choices = C(n+m-1,m-1).

What's a bin? In chuck-a-luck, where 3 dice are rolled in a birdcage, how many outcomes are there? Here bins are numbers 1-6 on the die (!) and each die is an item. The roll assigns each die to a number, i.e. each item to a bin. So it's C(6+3-1,3) or 56 different outcomes.

Below the | are the five bin separators, the six bins are numbers on a die face, and we want to count how many ways to distribute the three identical dice into the bins.

     D   D   D
         V
1  | 2 | 3 | 4 | 5 | 6 |

Distributions of Distinguishable Objects to Bins

We have n objects, m bins, k different classes of object, i_k members in each class.

How To: We'll just apply the "Identical Items" formula to strings of n+m-1 items, of which (m-1) are *'s and thus are a class of identical items, and the rest may be put into the k identity class of items. So we count the different possible orders of such a string with all elements different = (n + m -1)!, and then notice that all orderings of identical elements in the string are equivalent, so we need to divide by the product of those counts for every class, including the bin-divider class. Get:
(n+m-1)!/[(m-1)!i₁!i₂!... i_k!].

Summary Distinctions

Our six different problems can all be considered as assigning objects to certain positions. For the first (Assignments), we have n different items (positions) and we need to fill each with one of k different values. Classify each proboem along three axes

1. Does it place all the given objects?
2. Is the order in which objects are assigned important?
3. Are all the objects distinct, or are some "the same"?

Practicalities: Combining Rules

Generally need several rules for a problem. Combx has some pretty sophisticated strategies and problems we didn't cover, (see a Combx text). Knowing what we do, we can often usefully

• Express count as sequence of choices
• Express count as difference of counts
• Express count as sum of counts for subcases

E.g. how many one-pair poker hands? The pair is 2 cards of same rank. The hand thus has 3 more cards, each of different rank, and not the pair's rank. Think (and Compute by multiplying) in order:
Select the rank of the pair, (13 choices)
select three cards from remaining 12 ranks, (C(12,3) choices)
select the suits of 2 cards in the pair, (C(4,2))
select the suits of the other 3 cards (4³) (FOCS p. 184-5).
Multiply these numbers of independent selections.

That's 1,098,240, or about 40% of all 2,598,960 poker hands.

Note (read on in FOCS) that the straight. flush. and straight flush hands need different treatment.

Subcases: just be organized: E.g. toss a quarter 12 times: how many times are there 8 or more heads? Boring, but easy, to calculate how many tosses give exactly 8, 9, 10, 11, and 12 heads.