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?



  • 1
    $\begingroup$ 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)$. $\endgroup$ – mhum Jan 20 '11 at 23:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Suvrit Jan 21 '11 at 8:13
  • $\begingroup$ @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. $\endgroup$ – 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}}$$

  • 1
    $\begingroup$ 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)$. $\endgroup$ – 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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.