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}^{'}|\)
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}^{'}|\)
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.
Finally,
\(|F_{I,a,W}|=\sum_{w=0}^{W} |F_{I,a,w}^{'}|\)
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?
here’s code for the counting scheme, where the convolutions are computed using the direct method. I will make a post about the number theoretic transform later.
#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;
}