Find the number of ways to choose N non-negative numbers that sum up to $S$ and are in strictly increasing order?

Question

More formally, find the number of ways of dividing a sum $S$ among $N$ numbers — $a_1, a_2, a_3, \dots, a_N$,
such that they are in strictly increasing order i.e. — $a_1 < a_2 < a_3 < \dots < a_n$,
given that $\sum_{i=1}^Na_i = S$ , $a_i >= 0$
Note that the order of the number is fixed.

Consider an example, $N = 3, S = 6$:
Total ways = 3
0, 1, 5
0, 2, 4
1, 2, 3

when $N = 3, S = 7$: Total ways = 4
0, 1, 6
0, 2, 5
0, 3, 4
1, 2, 4

Edit:
The question's previous title asked for the probability, but to find probability I think we ultimately need to find such number of ways (I don't know if there is some other way). Feel free to answer in terms of probability or the number of such ways.

Answer 1

We will first assume $0$ is not allowed as one of the numbers. We will cover $0$ at the end.

You can write a recurrence. If $A(S,N)$ is the number of ways of writing $S$ as a strictly increasing sum of $N$ numbers greater than $0$, we can look at whether $1$ is one of the numbers. If it is, we need to express $S-1$ as a strictly increasing sum of $N-1$ numbers greater than $1$. Subtract $1$ from them all and $N$ from $S$ and we see there are $A(S-N,N-1)$ ways to write $S$ in a way including $1$.

If $1$ is not included, we need to write $S$ as a sum of $N$ numbers greater than $1$. Again we can subtract $1$ from all the numbers and find there are $A(S-N,N)$ ways to write $S$ as a sum of $N$ numbers not including $1$, so $$A(S,N)=A(S-N,N-1)+A(S-N,N)$$ Given the observation that $A(S,N)=0$ when $S \lt \frac 12N(N+1)$ and $A(S,1)=1$ this will bottom out quickly for reasonable values of $S,N$

Let $B(S,N)$ be the number of ways of expressing $S$ as the increasing sum of $N$ numbers where $0$ is permitted. If $0$ is included there are $A(S,N-1)$ ways. If $0$ is not included, there are $A(S,N)$ ways, so $$B(S,N)=A(S,N-1)+A(S,N)$$ is the final count.

Taking the example of $S=7,N=3$ we have $$B(7,3)=A(7,3)+A(7,2)\\A(7,3)=A(4,2)+A(4,3)=1+0=1\\ A(7,2)=A(5,1)+A(5,2)=1+A(3,1)+A(3,2)=3\\B(7,3)=4$$

Answer 2

You can solve this with a generating function. Let $$P = \prod_{i=0}^S (1+x^iy)$$

The variable $y$ tracks the number of summands, and $x$ tracks the amount contributed to the sum. Then the number of sequences of $N$ strictly increasing summands adding up to $S$ is the coefficient of $x^Sy^N$ in $P$, since any set of $N$ distinct numbers adding up to $S$ creates a single such sequence due to the dual requirements for the summands being distinct and strictly increasing.

So for example with $N=3$, $S=6$ as above, we get the solution $0,1,5$ from $$(x^0y)(x^1y)(1)(1)(1)(x^5y)$$

You can calculate this for specific values using the MAGMA Online Calculator with the code:

Z<x,y>:=PolynomialRing(Integers(),2);
N:=3;
S:=30;
prod:=&*[1+x^i*y:i in {0..S}];
Coefficient(Coefficient(prod,y,N),x,S);