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

Fix $n, k$. Then

$$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)!}$$

is 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$ ?

EDIT:

I should explain my motivation for this problem.

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}

• The bivariate (in $n,r$) generating function is $\exp\{z +uz^k/k!\}$. It does not seem that anything better can be said. Commented Apr 28, 2018 at 11:44
• @zhoraster that might be the case. I have added my motivation to the problem if that is of any help. Commented Apr 28, 2018 at 23:19

Quoting “Hitchhikers Guide to the Galaxy”:
“Have an answer for you? Yes. But you're not going to like it.” :)
Note: I use $$\left(m\right)_{n}$$ for rising factorial and vice versa; as opposed to Wikipedia
First we rewrite:
Let $$n=k\cdot r+j$$
$$C_{r}^{n,k}=\frac{1}{r!}\left(\begin{array}{c} k\cdot r+j\\ k,k,...j \end{array}\right)\cdot t^{r}=\left(j\right)_{k\cdot r}\cdot\frac{\left(\frac{t}{k!}\right)^{r}}{r!}$$
In order to fit this into a Generalized Hypergeometric function we must convert
$$\left(j\right)_{k\cdot r}->\left(xxx\right)_{r}$$ Which, unfortunately, is extended (but not messy).
$$= \left(\frac{j}{k}\right)_{r}\cdot\left(\frac{j+1}{k}\right)_{r}\cdots\left(\frac{j+k-1}{k}\right)_{r}\cdot\left(k^{k}\right)^{r}$$
https://www.amazon.com/Generalized-Hypergeometric-Functions-Lucy-Slater/dp/052109061X
Appendix I.26
Which yields
$$_{k}F_{0}\left(\begin{array}{c} \frac{j}{k},\frac{j+1}{k},\cdots\frac{j+k-1}{k}\\ - \end{array};\left(\frac{k^{k}}{k!}\right)\cdot t\right)$$
Which is pretty much a rewrite of the binomial expansion for multinomials.
————————

The $$k\cdot r$$ term is a persistent problem. I might be willing to dig a little further if you, @Miheer, are willing to accept multivariate series; something like Appell Series or some such.
Say $$t^{k},s^{l}$$
(Of course there is no guarantee of success)

First we rewrite:

Let $$n=k\cdot r+j,p=r\cdot k$$ and assigning $$t,s,w$$ as indexing variables.

$$C_{r}^{n,k}=\frac{1}{r!}\left(\begin{array}{c} k\cdot r+j\\ k,k,...j \end{array}\right)\cdot t^{r}=\left(p\right)!\cdot\left(\begin{array}{c} j+p\\ j \end{array}\right)\cdot\frac{\left(\frac{t}{k!}\right)^{r}}{r!}$$

$$\left(p\right)!\cdot(1+s)^{j+p}=\left[s^{p}\right]\left[w^{p}\right]\left(x\right)!\cdot(1+s)^{j}\cdot\left(1+s\right)^{x}w^{x}$$

$$=\left[s^{p}\right]\left[w^{p}\right](1+s)^{j}\cdot e^{\left(w\cdot\left(1+s\right)\right)}$$

$$C_{r}^{n,k}=\left[s^{p}\right]\left[w^{p}\right]\left[t^{r}\right]p!\cdot(1+s)^{j}\cdot e^{\left(w\cdot\left(1+s\right)\right)}\cdot e^{\frac{t}{k!}}$$

It looks like $$\left[s^{p}\right]\left[w^{p}\right]=\left[\left(s\cdot w\right)^{p}\right]$$ is possible, but that seems to just be shuffling since s,w are independent.

Actually p seems redundant but looks neater to me.