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.

And this makes a nice dynamic programming homework question, when finding the actual solution is a little more involved than finding just the value of the solution.

ReplyDelete