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
 A: 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}$
A: 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}}$$
