Well, with Wouter punting, and no other expressed interest, I'll tell the answer to "how many ways are there to put N balls in M bins" to kill this thread:

--

Any set of balls in bins is uniquely represented by a string like "o|ooo|o|||o" where 'o' represents a ball and '|' represents a wall between bins. There are M-1 walls between bins and N balls, so these strings can be generated by starting with N+M-1 walls and choosing N to be balls.

So the answer is "N+M-1 choose N."

--

I first encountered this problem in a graduate level Information Theory course at Caltech, where it stumped a lot of people. It also stumped my research group at Columbia for a couple weeks before I noticed we were working on the same problem. It looks easy because "buckets" are used as sources of "balls" in basic probability problems, but the usual approaches to solving combinatorial problems problem fail on this one.

The problem looks easy, but is very hard, yet the answer is *obvious* basic combinatorics once you look at the problem the right way. That's why it's my favorite combinatorics problem.

--Glenn