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



number of muti-indices of a fixed order which are less than a given multi-index 
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*](http://www.math.upenn.edu/~wilf/DownldGF.html) 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](http://en.wikipedia.org/wiki/Composition_%28number_theory%29) 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}}$$


