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

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?

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$.
• 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$. – Trevor Gunn Mar 26 '18 at 22:42