# number of muti-indices of a fixed order which are less than a given multi-index

Dear all,

I have the following problem which seems quite standard to me but nevertheless I'm stuck right now.

Given a positive integer $n$ and a multi-index $p \in \mathbb{N}_0^n$ I want to count the number of multi-indices $k \in \mathbb{N}_0^n$ which are dominated by $p$ (i.e. every component of $k$ is less than or equal to the corresponding component of $p$) and whose components sum up to a given positive integer $s$. To express this in another way, I am interested in the cardinality of the set

$C(n,s,p) = \{ k = (k_1, \ldots, k_n) \in \mathbb{N}_0^n \mid k \leq p, |k| = s\}$ .

Without the condition $k \leq p$ I have found a solution by recursion (which I guess is not the most elegant way). Does anyone have a suggestion for the general cardinality?

Regards,

Simon

-
This is probably no better than your recursive solution, but you can get $C(n,s,p)$ as the coefficient of $x^s$ in $\Pi_{j=1}^n \Sigma_{i=0}^{p_j} x^i = \Pi_{j=1}^n (x^{p_j+1}-1) / (x-1)$. –  mhum Jan 20 '11 at 23:47
It seems what you are searching for is a restricted partition of $s$, where the restriction is defined by $p$; perhaps that's the logic behind mhum's comment. If $p$ were full of the same constant, then the answer would be much easier I guess. –  Suvrit Jan 21 '11 at 8:13
@mhum: Thanks for the comment, your formula is perfect for numerical applications (and more general than my recursion as it just solved the problem without the condition $k \leq p$). @Suvrit: If all components of $p$ are equal there should indeed be a simple answer as then you can exploit symmetry (and for example just look at those $k$ whose components are non-decreasing). I will think about the problem again over the weekend but as I know almost nothing about combinatorics I am not very optimistic... A quick search on 'restricted partitions' was also not successful. –  herrsimon Jan 21 '11 at 17:35

Expanding my comment into a full answer:

By inspection, we can see that $C(n,s,p)$ is the coefficient of $x^s$ in:

$(1 + x + x^2 + \cdots + x^{p_1}) (1 + x + x^2 + \cdots + x^{p_2}) \cdots (1 + x + x^2 + \cdots + x^{p_n})$

$= \Pi_{j=1}^n \Sigma_{i=0}^{p_j} x^i$

$= \Pi_{j=1}^n {{(x^{p_j+1}-1)}\over{(x-1)}}$

I'm not particularly expert at generating functions, so I haven't been able to reduce this to a more pleasing (closed-form) expression. Perhaps more time studying Wilf's generatingfunctionology will yield better results.

The asker also mentions the special case where the $k \leq p$ constraint is ignored (which is equivalent to the situation when $p_i \geq s$ for all $i$). In this case, we can get a better formula. Let $C(n,s)$ denote the desired quantity.

First, we recall the definition of the composition of an integer. Next, we observe that there are ${s-1}\choose{i-1}$ compositions of $s$ into $i$ (non-zero) parts and that there are ${n}\choose{i}$ ways to distribute these $i$ parts into the $n$ indices (we let the other $n-i$ indices be zero). Thus, we have $$C(n,s) = \Sigma_{i=1}^{min(n,s)} {{s-1}\choose{i-1}} {{n}\choose{i}}$$

-
The number of ways of writing $s$ as a sum of $n$ nonnegative integers is ${s + n - 1\choose n-1}$--this is the multiset number $\left({s\choose n}\right)$. –  alpoge Jan 21 '11 at 20:09

The number of solutions to the equation $a_{1}+a_{2}+\cdots+a_{n}=k$ where $s>a_{i}\geq0$, $a_{i}\in\mathbb{N}$ for all i is (unless I typo'd) $\sum_{j=0}^{n}\left(-1\right)^{j}\binom{n}{j}\binom{n+k-js-1}{n-1}$

-