I'm looking for interesting counting problems and came up with this one:
Suppose in a game of baseball that the bases are empty and that the offense is so good that runners always advance. For the sake of ease, suppose that the game keeps going until the first runner reaches home, even after 3 outs. How many ways are there for runners to run around the bases until the first run?
Of course if we only track the one runner, we will have $2^3$ ways since we might as well ask which bases he stops at. Adding two or more runners becomes more difficult. I believe it's better to think of the answer to the single runner broken up over the number of at-bats, as $$\sum_{i=0}^3 {3\choose i}$$ Then, when we add another runner at the second at-bat, the bases he stops at only have to precede the bases of the first runner, etc. So, if there are $k$ at-bats, we ask how many upper triangular $(k-1)\times(k-1)$ matrices with entries from $0,1,2,3,4$ are there so that the rows are nondecreasing, the columns strictly decreasing, and no two columns the same.
Is this a familiar kind of problem? I keep expecting there to be a little trick that will make an easy solution.
It would be interesting to add in more bases, as well.
Thanks!