Problem
\(n\in\mathbb{N}\)
\(I = [0,n)\)
\(a\in\mathbb{N}^{I}\)
\(W \in \mathbb{N}\)
\(F(I)=\{J \mid J \subseteq I, \sum_{i \in J}a(i) \leq W\}\)
The problem is counting the set family \(F(I)\), i.e. evaluate \(|F(I)|\).
Solution
\(F(I)\) can be decomposed into a finite union of disjoint sets.
\(F_{w}(I)=\{J \mid J \subseteq I, \sum_{i \in J} a(i) = w\}\)
\(F(I)=\bigcup_{w\in [0,W]} F_{w}(I)\)
\(|F(I)|=\sum_{w\in[0,W]} |F_{w}(I)|\)
\(F(\cdot)\) and \(F_w(\cdot)\) are compatible with respect to the inclusion relation. So, if \(\emptyset \subseteq I_1 \subseteq I_2 \subseteq \dots \subseteq I\), then \(F_w(\emptyset) \subseteq F_w(I_1) \subseteq F_w(I_2)\subseteq\dots\subseteq F_w(I)\) and \(F_w(\emptyset) \subseteq F_w(I_1) \subseteq F_w(I_2)\subseteq\dots\subseteq F_w(I)\).
Let \(I_i=[0,i)\). \(I_0=\emptyset\).
\(w=0\rightarrow |F_{w}(\emptyset)|=|\{\emptyset\}|=1\)
\(w\neq 0 \rightarrow |F_{w}(\emptyset)|=|\emptyset|=0\)
Now, here’s the important relation that makes the decomposition of \(F(I)\) useful. It’s a recurrence.
\(|F_{w}(I_{i+1})|=|F_{\textbf{w}}(I_{i})|+|F_{\textbf{w-a(i)}}( I_{i} )|\)
\(|F(I)|=\sum_{w\in[0,W]} |F_{w}(I)|\)
If you fix the set of indices \(J\subseteq I\), then \(|F_{w}(J)|\) is a total function of w. \(|F_{w}(J)|\) can be expressed as a convolution.
\(|F_w(I)| = |F_w(\emptyset)|* |F_w(\{0\})| * |F_w(\{1\})| *\dots * |F_w(\{n-1\})|\)
You can arrive at this convolution term with generating functions too. There’s a nice signal processing intuition for this: the functions being convolved are essentially linear two-tap unattenuated forward echo filters. And applying the recurrence successively just performs a sparse convolution. Notice that \(|F_{w}(\emptyset)|\) is basically the unit impulse.
I think there’s more counting schemes than this. I’m not surprised since this problem is coupled with many other counting problems in algebra and geometry: for example, the constraint on the set system is that of the 0-1 knapsack problem, and the feasible points for that integer linear program are exactly the characteristic functions/vectors of feasible sets in the set system \(F(I)\).
I thought of another problem for later while solving this one. If \(F(I)\) is an independence system over a finite \(I\), then it’s equal to the union of its maximal elements. How do you count or enumerate those elements?
Also, here’s code for the counting scheme, where the convolutions are computed using the direct method. For sequences with many elements and many repeated elements, a number theoretic transform might be better.
#include<iostream>
#include<vector>
#include<cassert>
int main() {
int n;
int W;
std::cin >> n;
std::cin >> W;
assert(W >= 0);
std::vector<int> a(n); // sequence a
int i = 0;
while (i < n) {
int a_i;
std::cin >> a_i;
assert(a_i >= 0);
a[i] = a_i;
i = i + 1;
}
std::vector<long long> count_F(W + 1);
count_F[0] = 1;
i = 0;
while (i < n) {
int w = W;
while (w >= a[i]) {
if (w - a[i] >= 0) {
count_F[w] = count_F[w] + count_F[w - a[i]];
}
w = w - 1;
}
i = i + 1;
}
long long count = 0;
int w = 0;
while (w <= W) {
std::cout << count_F[w] << std::endl;
count = count + count_F[w];
w = w + 1;
}
std::cout << count << std::endl;
}