Welcome to MathOverflow

Question

3

4

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

flag	asked Jan 20 2011 at 18:54 herrsimon 149●4

1

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 2011 at 23:47

1

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. – S. Sra Jan 21 2011 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 2011 at 17:35

mhum · Accepted Answer · 2011-01-21 19:54:51Z UTC

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

unknown (google) · Answer 2 · 2011-01-21 20:37:57Z UTC

1

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

answered Jan 21 2011 at 20:37

unknown (google)
11●1

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.