# Counting ordered tuples with an additional condition

Let $a_1 \le a_2 \le ... \le a_n$ be positive integers. I'm looking for a closed formula of the number $f(a_1,...,a_n)$ of all (ordered) tuples $(x_1,...,x_n)$ of positive integers statisfying $$x_1 + ... + x_i \le a_i\quad\quad(i=1,...,n).$$ $f$ has the recursion $f(a_1,...,a_n) = \sum_{k=1}^{a_1}f(a_2-k,...,a_n-k)$ that also yields the sum expression $$f(a_1,...,a_n) = \sum_{x_1=1}^{a_1}\sum_{x_2=1}^{a_2-x_1}...\sum_{x_n=1}^{a_n-x_1-...-x_{n-1}}1$$ The only case I know of is for $a_1=...=a_n$ when one obtains $\binom{a_n}{n}$ what is also an upper bound for $f(a_1,...,a_n)$.

Edit: Using the transformation $y_i = x_1 + ... + x_i$ one finds that the searched $f$ equals the number of ordered tuples $1 \le y_1 < y_2 < ... < y_n \le a_n$, satisfying the additional condition $y_i \le a_i$ for all $i$.

It's classical that the number of ordered tuples $1 \le y_1 <...<y_n \le a$ equals the number of k-element subsets of $\lbrace 1,...,a\}$ which is $\binom{a}{n}$. Perhaps it's possible to extend one of the solutions for this classical formula to my problem ?

-
Have you tried a generating function approach? More concretely, write $b_1=a_1$ and $b_j = a_j-a_{j-1}$ for $2\le j\le n$, so that the inequalities to be satisfied are $x_1+\cdots+x_j \le b_1+\cdots+b_j$, and the $b_j$ can be any nonnegative integers (I suppose $b_1\ne0$). Then have you considered the $n$-variable generating function $F(T_1,\dots,T_n) = \sum_{k_1=0}^\infty \cdots \sum_{k_n=0}^\infty f(b_1,b_1+b_2,\dots,b_1+\cdots+b_n) T_1^{k_1} \cdots T_n^{k_n}$? – Greg Martin Jan 14 '12 at 20:33
For $n=2$ this is oeis.org/A141418 – Tad Mar 5 '15 at 5:25

$x_{1}+...+x_{i}=a_{i}$ means the compositions (= ordered partions) of the integer $a_{i}$ into exactly $i$ parts. Their number is:

$$C_{a_{i},i}=\binom{a_{i}-1}{i-1}$$

$x_{1}+...+x_{i}\le a_{i}$ means the number $C_{\le a_{i},i}$.

$$C_{\le a_{i},i}=\sum_{j=1}^{a_{i}}C_{j,i}=\sum_{j=1}^{a_{i}}\binom{j-1}{i-1}$$

The number for all i's is then:

$$\sum_{i=1}^{n}C_{\le a_{i},i}=\sum_{i=1}^{n}\sum_{j=1}^{a_{i}}C_{j,i}=\sum_{i=1}^{n}\sum_{j=1}^{a_{i}}\binom{j-1}{i-1}.$$

$$\sum_{i=1}^{n}C_{\le a_{i},i}=\sum_{i=1}^{n}\frac{\left(a_{i}-i+1\right)}{i}\binom{a_{i}}{i-1}$$

-