Number of integer combinations $x_1 < \cdots < x_n$?

Question

I asked this question earlier on math.stackexchange.com 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.

Answer 1

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 .

Answer 2

The simplest formula is the determinant $$ \left| \binom{a_i+j-i}{ j-i+1}\right|_{i,j=1,\dots,n}. $$ For example, when $n=3$ this is $$ \begin{vmatrix} \displaystyle \binom{a_1}{1}&\displaystyle \binom{a_1+1}{2}&\displaystyle \binom{a_1+2}{3}\\ 1 &\displaystyle \binom{a_2}{1}&\displaystyle \binom{a_2+1}{2}\\ 0 & 1 &\displaystyle \binom{a_3}{1} \end{vmatrix} $$ In general there are 1's in the diagonal below the main diagonal and 0's below that, so when expanded there are $2^{n-1}$ terms. It is unlikely that there is a simpler formula.

This formula is most easily proved by inclusion-exclusion. We start with the set of positive integer sequences $(x_1,\dots, x_n)$ satisfying $1\le x_i\le a_i$ for each $i$ and use inclusion-exclusion to count those sequences satisfying none of the conditions $x_i\ge x_{i+1}$, using the fact that it's easy to count the sequences satisfying any subset of them. For example, with $n=3$ the determinant expands to $$a_1a_2a_3 - a_1\binom{a_2+1}{2} -\binom{a_1+2}{2} a_3 + \binom{a_1+2}{3}.$$ Here the term $a_1\binom{a_2+1}{2}$, for example, counts sequences $(x_1,x_2,x_3)$ satisfying $a_1\ge x_1\ge 1$ and $a_2\ge x_2\ge x_3\ge 1$. The crucial fact that makes this work is that since $a_2 < a_3$, the condition $a_2\ge x_2\ge x_3\ge 1$ implies that $a_3\ge x_3$.

As Vladimir noted, an equivalent formula replaces strong with weak inequalities. This formula (in a more general form) was given by B. R. Handa and S. G. Mohanty, ``On $q$-binomial coefficients and some statistical applications," SIAM J. Math. Anal. 11 (1980), 1027--1035. A recent proof of their formula, with further references, is in my paper with Nicholas Loehr, Note on enumeration of partitions contained in a given shape, Linear Algebra Appl. 432 (2010), 583--585. A preprint version can be found on my home page, http://people.brandeis.edu/~gessel/homepage/papers/.

While I'm plugging my own papers, I'll note a paper of mine closely related to the paper of Pemantle and Wilf that William mentioned: A probabilistic method for lattice path enumeration, J. Statist. Plann. Inference 14 (1986), 49--58, also available on my home page.

Answer 3

(This is a bit too long for a comment, though not exhaustive at all.)

This number, especially if you make appropriate changes of your notation to replace $< $ by $\le$ (replace $a_i$ by $a_i-i$, and $x_i$ by $x_i-i$, that is), admits an interpretation in terms of Young lattice (inclusion partial order on Young diagrams), or, equivalently, in terms of lattice paths below the graph of $i\to a_i$).

In addition to the binomial coefficient example (in these updated terms it is the number of Young diagrams inside a rectangle, or lattice paths inside a rectangle, so manifestly a binomial coefficient), the answer which is very well known applies to the diagram $(n,n-1,\ldots,1)$, when it is the $n$th Catalan number, and more generally, for $(kn,k(n-1),\ldots,k)$, when it is the $n$th Fuss–Catalan number. This altogether suggests that there might be some hook-length-kind formula formula which I am missing, and maybe this incomplete answer will make someone who knows that formula to explain it...

Answer 4

These numbers are closely related to the Stanley-Pitman polytope, and also lattice path counts (this latter explains Ira Gessel's determinant formula).