# Number of integer combinations x_1 < … < x_n ?

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.

-
Possible duplicate mathoverflow.net/questions/83714/combination-and-probability . Gjergji's suggestion there may be worth researching. Gerhard "Ask Me About System Design" Paseman, 2012.01.17 –  Gerhard Paseman Jan 17 '12 at 21:55
Gerhard, do you know about the "determinantal formula" mentioned by Gjergji ? In the wikipedia article (and some other) I only read something about a determinant that is related to a graph. How do I construct the graph from my data ? –  Ralph Jan 17 '12 at 22:30
I'm sorry, I don't know. If you edit this question so as to provide a reference request (after doing some searches yourself), you may get some more knowledgable answers, and likely the other question (not this one) will be closed as a duplicate. Gerhard "Ask Me About System Design" Paseman, 2012.01.17 –  Gerhard Paseman Jan 17 '12 at 22:35

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 .

-
Thanks for the link. Proctor's formula in the linear case is really helpful. –  Ralph Jan 18 '12 at 21:39
The formula that Pemantle and Wilf attribute to Proctor is equivalent to a much older formula: the number of paths in the plane from the origin to the point $(a,b)$, where $a > pb$, that stay strictly below the line $x=py$, with steps $(1,0)$ and $(0,1$), is $$\frac{a-pb}{a+b}\binom{a+b}{a}.$$ This formula was apparently first stated by E. Barbier in 1887. A reference is Marc Renault, Four Proofs of the Ballot Theorem, Mathematics Magazine 80 (2007), 345--352; available online at webspace.ship.edu/msrenault/ballotproblem/…. –  Ira Gessel Jan 19 '12 at 0:32

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.

-
Dear Ira, I was wondering, - is there any representation-theoretic interpretation of this number (as a dimension of a naturally defined subspace in some construction over the Hilbert scheme etc. - in the spirit of the (Fuss-)Catalan case)? –  Vladimir Dotsenko Jan 18 '12 at 20:26
Thank you very much for your determinantal formula and the enlightening explanation in case $n=3$. It's interesting to see how this approach (that is in some sense opposite to the "intuitive way" of trying to count $x_1 < x_2 \le a_2$ for given $x_1$) solves the problem. –  Ralph Jan 18 '12 at 21:40
BTW: Do you know if there is a sign-free formula for the number the combinations ? In particular, do you know if there is a formula similar to my sum formula above in the literature ? Thanks in advance! –  Ralph Jan 18 '12 at 21:42
Vladimir: I don't know of any representation-theoretic interpretation of this number. This formula is a special case of a determinant formula for counting plane partitions of a given shape with upper and lower bounds for the parts in each row (it's the case of one column). This more general formula is related to "flagged Schur functions", which are related to Schubert polynomials, but that's as far as my knowledge goes in this direction. Ralph: I have not seen a formula like your sum in the literature, and I don't know of a sign-free formula. –  Ira Gessel Jan 18 '12 at 23:37
Thanks! This nice determinantal formula also happens to be very useful for computations towards another recent Mathoverflow question (mathoverflow.net/questions/85409). –  Noam D. Elkies Jan 20 '12 at 3:13

(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...

-
Thanks for drawing my attention to Young lattices. Also the transformation from $<$ to $\le$ as you explained will be helpful in translating Proctor's formula. –  Ralph Jan 18 '12 at 21:38