8
$\begingroup$

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

  • 0
    For $n=2$ this is http://oeis.org/A1414182015-03-05

1 Answers 1

1

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

\begin{equation}C_{a_{i},i}=\binom{a_{i}-1}{i-1}\end{equation}

(see e.g. Stover, Christopher and Weisstein, Eric W.: "Composition." From MathWorld -- A Wolfram Web Resource).

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

\begin{equation}C_{\le a_{i},i}=\sum_{j=1}^{a_{i}}C_{j,i}=\sum_{j=1}^{a_{i}}\binom{j-1}{i-1}\end{equation}

The number for all i's is then:

\begin{equation}\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}.\end{equation}

\begin{equation}\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}\end{equation}