Sunday, October 31, 2010

A combinatorial dessert?

Last weekend, I was doing some QA testing when one of our interns from this summer messaged me with a problem she was solving. It turns out to have an elegant solution, and will be my first blog!
A group of friends and I have found that solving puzzles seems to remove some of the drudgery in our life, and keep the work day interesting. Whenever I find new puzzles/ or problems of interest, I plan to update this blog with them. It is also a way for me to keep track of all these problems.

So here goes: How many non decreasing sequences can you form with n digits?
For example, with two digits, we can have sequences like 00, 01, 11, 45, 66, etc that are non decreasing, while a sequence of the form 43 would be decreasing and would not count. For two digits, you can easily convince yourself that we have 55 non decreasing sequences. For general n, what is this number?

Note that I am counting 00, 01 etc as two digit numbers . If I were to count them as one digit numbers, then the answer would be slightly different.