10
$\begingroup$

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

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

2 Answers 2

0
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .