Partitioning a set of size n to k-subsets of at most size b

Question

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?

Answer 1

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.