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

restricted partitionof $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. $\endgroup$ – Suvrit Jan 21 '11 at 8:13