I asked this question earlier on math.stackexchange.com but didn't get an answer:
Let $0 < a_1 < … < a_n$ be integers. Is there a closed formula (or some other result) for the number $N(a_1,…,a_n)$ of integer combinations $0 < x_1 < … < x_n$ such that $x_i \le a_i$ $(i=1,…,n)$ ?
Of course, if $a_i = a_n – n + i$ for all $i$, then $N = \binom{a_n}{n}$.
I considered the following model: Let $B_1 \subseteq … \subseteq B_n$ be nested boxes. $B_i$ contains $a_i$ balls that are labeled by $1,…,a_i$. Choose one ball from each box (without repetition) and afterwards sort the balls. Then $N$ equals the number of different combinations that can be obtained in this way.
Example: $n=3$
For the chosen balls $b_i \in B_i$ there are the following possibilities:
1) $b_3 \in B_3 \setminus B_2$, $b_2 \in B_2 \setminus B_1$, $b_1 \in B_1$. The balls
are already sorted and there are $(a_3-a_2)(a_2-a_1)a_1$ possibilities.
2) $b_3,b_2 \in B_2 \setminus B_1$, $b_1 \in B_1$. After sorting $b_2,b_3$ there are
$\frac{(a_2-a_1)(a_2-a_1-1)}{2!}\cdot a_1$ possibilities.
3) $b_3,b_2,b_1 \in B_1$. After sorting there are $\frac{a_1 (a_1-1)(a_1-2)}{3!}$ possibilities.
4) $b_3 \in B_3 \setminus B_2$, $b_2,b_1 \in B_1$. After sorting $b_1, b_2$ there are $(a_3-a_2) \cdot \frac{a_1 (a_1-1)}{2!}$ pssibilities.
5) $b_3 \in B_2 \setminus B_1$, $b_1,b_2 \in B_1$. After sorting $b_1, b_2$ there are $(a_2-a_1) \cdot \frac{a_1 (a_1-1)}{2!}$ pssibilities.
Generalizing this pattern yields the formula
$$N(a_1,…,a_n) = \sum_{\nu} \prod_{i=1}^n \binom{a_i-a_{i-1}}{\nu_i!}$$
$(a_0 := 0)$ where $\nu_i$ is the number of balls choosen from $B_i \setminus B_{i-1}$. The sum is taken over all $\nu=(\nu_1,…,\nu_n)$ such that $0 \le \nu_i \le i$ and $\nu_1 + … + \nu_n = n$.
But this is far from a closed formula. I do not even know the exact number of summands.
Also note that there is a recursion formula
$$N(a_1,…,a_n) = N(a_1,…,a_{n-1}) + N(a_1,…,a_{n-1},a_n -1)$$
but I wasn't able to guess a closed form thereof.
Edit: Thank you all very much for your answers. Each one deserves to be accepted. Unfortunately this isn't possible in MO. I therefore accepted William's since Proctor's formula in the linear case seems to be most helpful in the application I have in mind.
Best Answer
Robin Pemantle and Herb Wilf give a short recurrence as an answer to this question, and a more compact formula when the sequence $a_n$ is linear, in a freely available paper from the EJC in 2009: vol. 16 (2009), #R60, "Counting Nondecreasing Integer Sequences that Lie Below a Barrier." Link: http://www.combinatorics.org/Volume_16/PDF/v16i1r60.pdf .