# Generating function for number of r-disjoint subsets each of size k

Fix $n, k$. Let

$$C^{n,k}_r =\frac{1}{r!} \binom{n}{\underbrace{k, \ldots, k}_{\text{r times}}, n-rk} = \frac{n!}{r!(k!)^r(n - kr)!}$$

be the number of ways to form $r$ disjoint subsets each of size $k$, of $\{1 \ldots n\}$.

Is there a closed form expression for its generating function $g(t) = \sum_{r=0}^{\infty} C^{n, k}_r t^r$ ?

Motivation

Let $\mathcal{C}$ be a (possibly empty) random collection of $k$-sized disjoint subsets of $\{ 1 \ldots n\}$. That is:

• Let $\mathcal{P}_{n, k} = \{ A \, | \, A \subseteq \{ 1 \ldots n\}, |A|=k\}$
• Then $\mathcal{C} = \{A_1, A_2 \ldots A_r\} \subseteq \mathcal{P}_{n, k}$ so that $A_i \cap A_j = \emptyset$ when $i \neq j$.
• $\mathcal{C}$ is random.

If we assume that:

• $\mathbb{P}(A \in \mathcal{C}) = \alpha$ for any $A \in \mathcal{P}_{n,k}$.
• Whenever we have a collection of disjoint sets $A_1, A_2, \ldots, A_r \in \mathcal{P}_{n,k}$ the events $\{ A_i \in \mathcal{C} \}$ are independent, i.e.

$$\mathbb{P}(A_1 \in \mathcal{C}, A_2 \in \mathcal{C}, \ldots, A_r \in \mathcal{C}) = \prod_{i=1}^r \mathbb{P}(A_i \in \mathcal{C}) = \alpha^r.$$

Then

\begin{align} \mathbb{P}(\mathcal{C} \neq \emptyset) &= \mathbb{P}(\bigcup_{A \in \mathcal{P}_{n,k}} \{ A \in \mathcal{C}\})\\ &= - \sum_{r=1}^{\infty} C^{n,k}_{r} (-\alpha)^{r}. \tag{By inclusion exclusion formula} \end{align}

• $g(t) =n! [s^n]e^{ts^k/k! +s}$ for what it worth. – Fedor Petrov May 5 '18 at 7:34
• I got the same exponential generating frunction. Apart from that, I don't expect a "closed fromula" unless $k=0$ or $k=1$. For $k=0$, get $f=e^t$; for $k=1$, get $f=(1+t)^n$. – T. Amdeberhan May 5 '18 at 13:51