0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ $g(t) =n! [s^n]e^{ts^k/k! +s} $ for what it worth. $\endgroup$
    – Fedor Petrov
    Commented May 5, 2018 at 7:34
  • $\begingroup$ 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$. $\endgroup$
    – T. Amdeberhan
    Commented May 5, 2018 at 13:51

0

Reset to default

You must log in to answer this question.