这是一份liverpool利物浦大学COMP323的成功案例

Given a set $S \subseteq N$, let $\chi_{S}: N \rightarrow{0,1}$ be the indicator function of the set $S$, i.e., let $\chi_{S}(i)=1$ if $i \in S$ and $\chi_{S}(i)=0$ if $i \in N \backslash S$. A collection of sets $\mathcal{S} \subseteq 2^{N} \backslash{\emptyset}$ is said to be balanced if there exists a vector $\left(\delta_{S}\right){S \in \mathcal{S}}$ of positive numbers such that $$ \sum{S_{\hookrightarrow} \mathcal{S}} \delta_{S} \chi_{S}=\chi_{N}
$$
The vector $\left(\delta_{S}\right){S \in \mathcal{S}}$ is called the balancing weight system for $\mathcal{S}$. Observe that any coalition structure $C S$ over $N$ is a balanced set system with $\delta{S}=1$ for any $S \in C S$. Indeed, balanced set systems can be viewed as generalized partitions of $N$. We are now ready to state the theorem.

COMP323 COURSE NOTES ：

ranges from 0 to $n-1$, and $W$ ranges from 0 to $w(N)$. For $s=0, j=1, \ldots, n-1$, we have
$$
X[j, W, 0]= \begin{cases}1 & \text { if } W=0 \ 0 & \text { otherwise. }\end{cases}
$$
Further, for $j=1, s=1, \ldots, n-1$ we have
$$
X[1, W, s]= \begin{cases}1 & \text { if } W=w_{1} \text { and } s=1 \ 0 & \text { otherwise. }\end{cases}
$$
Now, having computed the values $X\left[j^{\prime}, W^{\prime}, s^{\prime}\right]$ for all $j^{\prime}<j$, all $W^{\prime}=0, \ldots, w(N)$, and all $s^{\prime}=$ $0, \ldots, n-1$, we can compute $X[j, W, s]$ for $W=0 \ldots, w(N)$ and $s=1, \ldots, n-1$ as follows:
$$
X[j, W, s]=X[j-1, W, s]+X\left[j-1, W-w_{j}, s-1\right]
$$
In the equation above, the first term counts the number of subsets that have weight $W$ and size $s$ and do not contain $j$, whereas the second term counts the number of subsets of this weight and size that do contain $j$.

Thus, we can inductively compute $X[n-1, W, s]$ for all $W=0, \ldots, w(N)$ and all $s=$ $0, \ldots, n-1$. Now, $N_{s}, s=0, \ldots, n-1$, can be computed as
$$
N_{s}=X\left[n-1, q-w_{n}, s\right]+\cdots+X[n-1, q-1, s]
$$