Counting equal covering sets

Question

Definition. We call a set $C$ of sets to be an equal covering set of $S$ if the elements of $C$ are all the same size and each element of $S$ is contained an equal number of times throughout the sets of $C$. We say that an equal covering set is of order $k$ if all elements of $C$ are size $k$.

For example, all $8$ equal covering sets of $\{1, 2, 3, 4\}$ of order $2$ are $ \{ \} $, $ \{ 12, 34 \} $, $ \{ 13, 24 \} $, $ \{ 14, 23 \} $, $ \{ 12, 34, 14, 23 \} $, $ \{ 13, 24, 14, 23 \} $, $ \{ 12, 34, 13, 24 \} $, $ \{ 12, 13, 14, 23, 24, 34 \} $ (where $ab$ is shorthand for $\{a, b\}$).

For convenience, let $f(n, k)$ denote the number of equal covering sets of order $k$ of the set $\{1, 2, \ldots, n\}$. The previous example then becomes $f(4, 2) = 8$. Immediately, a few properties of $f(n, k)$ become clear:

• $f(n, 0) = 2$,
• $f(n, 1) = 2$,
• $f(n, k) = f(n, n - k)$,
• $f(n, k) = 0$ for $k \not\in \{0, 1, \ldots, n\}$.

In addition, the covering sets are governed by the following equation \begin{align*} (\textrm{total elements}) &= (\textrm{number of sets}) \cdot (\textrm{size of sets}) = sk \\ &= (\textrm{number of distinct elements}) \cdot (\textrm{times elements are included}) = nm .\end{align*} This motivates one to count casewise on either $s$ or $m$. In particular, we can decompose $f$ into a sum in terms of another function $g$ that counts the number of covering sets subject to the parameters $(s, k, n, m)$: $$f(n,k) = \sum\limits_{\substack{0 \le m \le \binom{n - 1}{k - 1}, \\ k' \mid m}} g(n m / k, k, n, m),$$ where the bounds are obtained by taking the maximal case of $s = \binom{n}{k}$ and $k'$ denotes $k / \gcd(n, k)$.

Question. Is there any good closed form for these values or alternatively an efficient way to compute them? I'm in particular interested in all values of $f(n,k)$ for $0 \le k \le n$ as well as the sum over all these values, which we shall denote by $S(n)$.

If it's helpful, brute force computation yields the following values (perhaps interestingly, $S(n)$ does not seem to be in OEIS):

• $f(5, 2) = 14$,
• $f(6, 2) = 172, f(6, 3) = 3436$,
• $S(1) = 4, S(2) = 6, S(3) = 8, S(4) = 16, S(5) = 36, S(6) = 3788$

Are these equal covering sets well studied, and is there any literature on the topic? The name likely is not to be found anywhere as it's something I've given somewhat arbitrarily.

Thank you in advance for the help.

Answer 1

The functions $g(s,k,n,m)$ equals the coefficient of $M_{m^n}$ in the expansion of $$\exp\big(\sum_{i\geq 1} \tfrac{(-1)^{i-1}}i M_{i^k}\big),$$ where $M$ denote monomial symmetric polynomials, whose index $a^b$ denotes the partition formed by $b$ parts each equal $a$.

For practical computation, the range for $i$ can be restricted to the interval $[1,m]$ and the exponent series can be truncated at the power $s=\frac{mn}{k}$.