I'm trying to find how many ways there are to partition n into k partitions with max value s. I've found many solutions that does this for unordered partitions. They use recursion and the say that p(n, k) = p(n-1, k-1) + p(n-k, k). But I can't get this to work with ordered partitions.
So I want to find a way to calculate p(n, k, s), preferably recursively. For example p(4, 3, 2) = 3. Because we can partition 4 into (2+1+1), (1+2+1), (1+1+2).
As pointed out in the comments an ordered integer partition is actually called integer composition. I did some more searching with that term and didn't find the exact answer to my specific question, but I could come up with a solution myself.
As I wanted to solve it recursively I did some experimenting and realized the recursive relation, I'll explain it with an example. Let's say we want to find the number of compositions with length $4$ that sums up to $5$ and where no part is bigger than $3$, we call this $p(5, 4, 3)$.
Then we realize that we can't pick $3$ in the first part because by doing that we will get at least the sum $6$ if we pick $1$ in all other parts.
So what happens if we pick $2$ instead? Then we have $3$ parts left that needs to have the sum $5-2 = 3$. But we could also pick a $1$ in the first part. Then we have the sum $4$ left to be made with $3$ parts.
So now we know that $p(5, 4, 3) = p(3, 3, 3) + p(4, 3, 3)$
Now maybe you can see the pattern for the recursive relation?
$$p(n, k, s) = \sum_{i=1}^{s}{p(n-i, k-1, s)}$$
We just define everything that is not possible to $0$ and then we have the base case when $n$ and $k$ is $0$ that is equal to 1 (we use the empty part to get $0$).
Side note: I'm a more of a programmer than mathematician so please correct me if I wrote something wrong.