The uncounting method

How do you write a program to list all words in {a,b} with x a's and y b's? You need to find a recursive structure.
How do you find a recursive structure? You write it out in full, for example, for x=2 and y=3, and you stare at the list until a pattern appears.
What do you do if the pattern does not appear?

That was my challenge in class the other day. I resolved it using the following uncounting method.

First, counting.
How many words are there? C(x+y,x), the binomial number.
Do you know any recursive formula for the binomial numbers? Yes: the Pascal triangle.
Let us write out the first few rows. How does one compute the next numbers?
With little effort, students remember or rediscover the recursive formulae C(n,x)=C(n-1,x)+C(n-1,x-1) .
Apply it here: C(x+y,x)=C(x+y-1,x)+C(x+y-1,x-1).

And now comes the uncounting method.

Step 1.
C(x+y,x) counts the number of words in {a,b} with x a's and y b's. Note that
C(x+y-1,x) counts the number of words in {a,b} with x a's and y-1 b's, and that
C(x+y-1,x-1) counts the number of words in {a,b} with x-1 a's and y b's.

Step 2.
So the recursive formula can be restated as:
the number of words in {a,b} with x a's and y b's equals
the number of words in {a,b} with x a's and y-1 b's plus
the number of words in {a,b} with x-1 a's and y b's.

Step 3.
Remove "number of" -- that's the uncounting:
the words in {a,b} with x a's and y b's equal (i.e. are in bijection with)
the words in {a,b} with x a's and y-1 b's plus (i.e. disjoint union)
the words in {a,b} with x-1 a's and y b's.

Now, with this big hint, back to the pattern problem. You have written your list in full for x=2 and y=3. You stare at the list until a pattern appears, where now, the pattern you're looking for is a decomposition into two subsets: one corresponding to words with x=2-1=1 and y=3, and the other corresponding to words with x=2 and y=3-1=2. At this point, students see the pattern, and we are done.

I learned this from a course on bijective combinatorics, one of my favorite courses ever, taught by Viennot when I was a student.