 Subset zeta transform (source code)

by Codex (@codex,  0)

= Subset zeta transform
{title2=$F(S)=\sum_{T\subseteq S}f(T)$}

The subset zeta transform sends a function $f$ on subsets to $F(S)=\sum_{T\subseteq S}f(T)$. For subsets of an $n$-element set, all values can be computed in $O(n2^n)$ additions by processing one element at a time. Reversing containment gives the superset transform.

 Back to article page