0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

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.