The Problem
\(I = [0,n), a \in Z^{I}\), \(a(i) \geq 0 \text{ } \forall i \in I\)
\(W \in Z\), \(W \geq 0\)
\(F_{I,a,W}=\{J \mid J \subseteq I, \sum_{i \in J} a(i) \leq W)\)
What is \(|F_{I,a,W}|\)?
\(F_{I,a,W}\) can be decomposed into a finite union of disjoint sets.
\(F_{I,a,w}^{'}=\{J \mid J \subseteq I, \sum_{i \in J} a(i) = w)\)
\(F_{I,a,w} = \cup_{w\leq W} F_{I,a,w}^{'}\)
Because \(a(i) \geq 0\), \(F_{I,a,w}^{'}=\emptyset\) for all \(w < 0\), so:
\(F_{I,a,w} = \cup_{0 \leq w\leq W} F_{I,a,w}^{'}\)
If \(J_0 \subseteq J_1 \subseteq \dots \subseteq I\) is a chain, then \(F_{J_0,a,w}^{'} \subseteq F_{J_1,a,w}^{'} \subseteq \dots \subseteq F_{I,a,w}^{'}\) is a chain. A chain of subsets that also covers \(I\) can be used to count \(|F_{I,a,w}^{'}|\)
Let \(J_i=[0,i)\). Then, \(J_0=[0,0)=\emptyset\) and \(I = J_{n}=[0,n)\)
If \(w=0\), then \(|F_{\emptyset,a,w}^{'}|=1\)
If \(w \neq 0\), then \(|F_{\emptyset,a,w}^{'}|=0\)
\(|F_{J_{i},a,w}^{'}|=|F_{J_{i-1},a,w}^{'}|+|F_{J_{i-1},a,w-a(i)}^{'}|\)
\(|F_{I,a,W}|=\sum_{w=0}^{W} |F_{I,a,w}^{'}|\)
You could stop here and adapt this to a dynamic programming algorithm over \(i\) and \(w\). I gave code for this below because it’s easy.
If you fix \(J\), then \(|F_{J,a,w}^{'}|\) is a total function of w. \(|F_{J_i,a,w}^{'}|\) can be expressed as a convolution.
\(|F_{J_i,a,w}^{'}| = |F_{\emptyset,a,w}^{'}|*|F_{\{a(0)\},a,w}^{'}|*\dots * |F_{\{a(i-1)\},a,w}^{'}|\)
\(|F_{I,a,w}^{'}| = |F_{\emptyset,a,w}^{'}|*|F_{\{a(0)\},a,w}^{'}|*\dots * |F_{\{a(n-1)\},a,w}^{'}|\)
\(|F_{I,a,W}|=\sum_{w=0}^{W}|F_{I,a,w}^{'}|\)
You can arrive at this convolution 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.
Supposedly, there’s more counting schemes beyond 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,a,W}\).
I thought of another problem for later while solving this one. If \(F_{I,a,w}\) 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?
#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;
}