Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.