I asked this question earlier on [math.stackexchange.com](https://math.stackexchange.com/questions/99015/counting-ordered-tuples-with-an-additional-condition) but didn't get an answer:



> 
> Let $0 < a\_1 < \cdots < a\_n$ be integers. Is there a closed formula (or some other result) for the number $N(a\_1,\ldots,a\_n)$ of integer combinations $0 < x\_1 < \cdots < x\_n$ such that $x\_i \le a\_i$ $(i=1,\ldots,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 \cdots \subseteq B\_n$ be nested boxes. $B\_i$ contains $a\_i$ balls that are labeled by $1,\ldots,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,\ldots,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,\ldots,\nu\_n)$ such that $0 \le \nu\_i \le i$ and $\nu\_1 + \cdots + \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,\ldots,a\_n) = N(a\_1,\ldots,a\_{n-1}) + N(a\_1,\ldots,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.



Number of integer combinations $x_1 < \cdots < x_n$?
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> .


