Let $S$ be a finite set. Following Lovasz (Matroid matching and some applications), let us define a polymatroid function over $S$ as a function $f : 2^S \rightarrow \mathbb{N}$ such that(1) $f(\emptyset) = 0$,(2) $X \subseteq Y \Rightarrow f(X) \leq f(Y)$,(3) $f(X \cup Y) + f(X \cap Y) \leq f(X) + f(Y)$.The function $f$ defines a 2-polymatroid if $f({x}) \leq 2$ for every $x \in S$. My question is as follows: given two such functions $f,g$ over the same set $S$, and given two integers $r,s$, what is the complexity of counting sets $Z \subseteq S$ such that $f(Z) = r$ and $g(Z) = s$?The $\# \mathsf{P}$-hardness of this problem is not clear to me, if by chance it was in $\mathsf{P}$ it would have some interesting consequences. Indeed, it encompasses natural problems such as counting the number of $k$-vertex trees in a graph, which complexity is open afaik.
Counting problems with two-polymatroids
counting complexity