A few minutes ago I realized the following (which I'm sure has already been well enumerated by mathematicians before):
I want to know how many ascending sequences of numbers there are using numbers from 1 to k, of length N. We're allowing numbers to be repeated, but the sequence can't ever decrease. For example, one such sequence could be:
11355567
That's 8 numbers long, so N=8; the numbers go from 1 to 7, so k=7.
Since that problem is too complicated for now, let's do something way easier: how many ascending sequences are there that just use 0 and 1, of length N? (Let's call these sequences "sorted binary sequences" for short.) Sounds intimidating, but it's actually really easy:
Well, there's the sequence that's all zeros. Aside from that, there has to be a one in the sequence somewhere, and after the first time a one appears, the rest of the sequence has to be ones. And there are N different places for the first one to appear. Example when N = 3:
000 - all zeros
001
011 - three possible places for the first appearance of "one"
111
So in total there are N+1 sorted binary sequences of length N (here, when N=3, we have 4 possibilities).
Still with me? Good. We can use this to figure out the big problem that we started with. For every ascending sequence containing numbers from 1 to k, we can just subtract one from each of the members of the sequence to get a sequence from 0 to k-1. There's still the same number of sequences here, they just have different symbols in them. This is great, because an ascending sequence containing numbers 0 to k-1 can be "built up" by adding a bunch of sorted binary sequences. Like this:
012 = 001 + 011
or
01333 = 00111 + 00111 + 01111
To make things easier, let's start with just adding two sorted binary sequences to get a sequence containing 0 through 2. There are N+1 sequences using 0 and 1. We need to add two of them together. If we made a table of possibilities, we could put our choice for the first sequence to add on the x-axis and our choice for the second sequence to add on the y, and we get a square of possibilities, N+1 on a side, with an area (total number of possibilities) of (N+1)*(N+1).
Example for N=2:
| 00 01 11
---+--------
00 | 00 01 11
01 | 01 02 12
11 | 11 12 22
Since for addition it doesn't matter which number is written first, that square of possibilities contains some duplicates, so we cut in half along the diagonal.
Continuing the example for N=2:
| 00 01 11
---+--------
00 | 00 -- --
01 | 01 02 --
11 | 11 12 22
This gives us a triangle of possibilities with area (N+1)(N+2)/2 (from which we get the
triangle numbers 1,3,6,10,15,21, etc.). If you're paying attention, you've noticed that we can't just say (N+1)*(N+1)/2- why not?!? It's because we cut the table of possibilities almost in half, but we need to keep all the numbers in the diagonal.
So that's how many ascending sequences of length N there are that contain the numbers 0 through 2 (sorted 3-ary sequences). Now that we've seen how 0 through 1 worked, and 0 through 2, let's try to generalize to zero through k-1 (which gives us the same answer as 1 through k).
To get a sorted k-ary sequence, we need to add up k-1 sorted binary sequences. Instead of getting a triangle of possibilities (and ending up with triangle numbers as the number of possible sorted sequences), we get a
standard simplex of possibilities (and end up with
polytopic numbers as the number of possible sorted sequences). That gives us (N+1)*(N+2)*(N+3)...*(N+k-1) / (k-1)! possibilities. For a sanity check, we verify our N=2, k=3 example that we did before:
(2+1)*(2+2)/2! = 3*4/2 = 6. And there are indeed six different ascending sequences containing 0 through 2, as shown in the table above.