3
$\begingroup$

I want to count the number of possibilities that one can produce $k$-subsets of a larger set $V$ with size $n$ such that 1) each subset $X_i$ has size at most $b$, 2) subsets do not have a common element, and 3) subsets altogether cover the elements in the larger set $V$.

More specifically, given a set $V$ where $|V|=n$, how many possibilities is there to choose subsets $X_1, ..., X_k \subseteq V$ such that

1) $|X_i| \leq b$,

2) $\forall_{i \neq j} X_i,X_j :$ $X_i \cap X_j = \emptyset$,

3) $\bigcup_{i \in \{1,...,k\}} X_i = V$,

Two possibilities are different if they do not have exactly same subsets. The order of subsets doesn't matter.

If finding the exact number of possibilities is hard, an upper bound suffices.

Can anyone suggest an approach to counting such possibilities?

$\endgroup$
1
$\begingroup$

An exponential generating series is a formal sum $f(x) = \sum_{n \ge 0} a_n \frac{x^n}{n!}$. We denote the relationship between $f(x)$ and $a_n$ by saying that $n![x^n]f(x) = a_n$. Here $[x^n]f(x)$ is the coefficient in front of $x^n$ in the formal sum.

This is $$\frac{n!}{k!} [x^n] \left( x + \frac{x^2}{2} + \frac{x^3}{3!} + \dots + \frac{x^b}{b!} \right)^k$$ by basic exponential generating function theory.

Here $$ x + \frac{x^2}{2} + \frac{x^3}{3!} + \dots + \frac{x^b}{b!} $$ is the generating function for non-empty sets of size at most $b$ and so $$ \frac{\left( x + \frac{x^2}{2} + \frac{x^3}{3!} + \dots + \frac{x^b}{b!} \right)^k}{k!} $$ is the generating function for a partitions of a set into $k$ sets of size between $1$ and $b$.

For example, $$ \frac{(2n)!}{n!} [x^{2n}]\left( \frac{x^2}{2} \right)^n = \frac{(2n)!}{n!2^n}$$ is the number of ways to partition a $2n$-element set into $n$ sets of size $2$.

I haven't read it but my guess is that Combinatorial Species and Tree-like Structures by François Bergeron,‎ Gilbert Labelle and Pierre Leroux would explain this sort of thing in more detail. Any other source on exponential generating functions and/or combinatorial species would also do.

$\endgroup$
  • $\begingroup$ Look up generating functions (also called generating series). They are a convenient way of encoding data. For instance, the sequence $(1,1,1,\dots)$ is encoded in $\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots$ via the coefficients. Another example is $\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \dots$ which is the generating function for the sequence $(1,2,3,\dots)$. The operator $[x^n]$ picks up the coefficient in front of $x^n$. $\endgroup$ – Trevor Gunn Mar 26 '18 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.