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