# Number of ways to build a collection of numbers where $sum = k$, each $0 < n_i <= d_i$ for some corresponding $d_i$, and sum of all $d_i >= k$

I apologize for any (mis|ab)use of notation since I'm not a mathematician. My background is software engineering and computer science.

I ran into this problem while trying to figure out the state-space for a game.

Assume:

• We have a set $S = \{s_0, \dotso, s_n\}$ that represents the spaces on the game board.
• We have a $\{d_s\}_{s \in S}$ that represents the "degree" of a space, which is the maximum number of game-pieces that can be placed in a particular spot. $d_s \in \mathbb{N}_{> 0}$
• We have a total of $N$ game pieces.

Suppose we have a set $T$ such that $T \subseteq S$, and a corresponding $\{d_t\}_{t \in T}$ such that $\sum\limits_{t \in T} d_t \ge N$, and define a $\{p_t\}_{t \in T}$ such that $0 < p_t \le d_t$ and $\sum\limits_{t \in T} p_t = N$. This basically models a subset of spaces where a total of $N$ pieces have been placed, and each space has at least 1 piece, and at most $d_t$ pieces.

How many such sets $T$ are there? I tried to figure this out on my own, but quickly got lost. It seems somewhat similar to the subset-sum problem, so I'm still trying to investigate along those lines to see what I get. I've been looking at partitions of numbers as well, to see if I can get some ideas from that.

## 1 Answer

Do I understand this correctly? The degrees $d_s$ are given, and you want to count the number of subsets $T$ of $S$ such that $\sum_{t \in T} d_t \ge N$ and $|T| \le N$. Note that given such a $T$, you can easily get the $p_t$ by starting with the $d_t$ and reducing one at a time.

The number $c(m,n)$ of $T$ with each given cardinality $m = |T|$ and sum $\sum_{t \in T} d_t = n$ is the coefficient of $x^m y^n$ in the expansion of $\prod_{s \in S} (1 + x y^{d_s})$. These can be obtained in pseudo-polynomial time $O(|S|^2 D)$ where $D = \sum_{s \in S} d_s$. Then you just add these up for $0 \le m \le N$, $D \ge n \ge N$.

• Yes you understand correctly! Thank you! I just had one question: should the $d_t$ be $d_s$ in that expansion? – Vivin Paliath Apr 8 '15 at 3:43
• Oops, yes. I'll edit. – Robert Israel Apr 8 '15 at 4:15
• Thanks! I am assuming that there is no closed form for that coefficient because the $d_s$ values are arbitrary? – Vivin Paliath Apr 8 '15 at 4:19