2
$\begingroup$

My little brother asked me a question that I cannot answer and I would love to get some help with it.


Background

My brother tried to understand what ${n\choose k}$ means and came to conclusion that it gives you the number of sets that have exactly $k$ distinguish elements.

After proving that ${n\choose k}={n!\over k!(n-k)!}$ he tried to find extension to this formula


His Question

He tried to find a formula for ${(n)\choose (k)}$

$${(n)\choose (k)}=\text{number of sets of subsets of $n$ elements set such that the combined size of the }\\\text{subsets is $k$ and the subsets in each set has no repeating elements}$$

For example:

For $(4)\choose(3)$ we construct the following set: $A=\{1,2,3,4\}$

I search how many sets of subsets of $A$, let's call the subsets $B_i$, there is such that the sum of $B_i$ in each set is equal $3$ and there is no repeated element from $A$.

In this example we have the following sets: $$\{\{1,2,3\}\},\\\{\{1\},\{2,3\}\},\\\{\{2\},\{1,3\}\},\\\{\{3\},\{1,2\}\},\\\{\{1\},\{2\},\{3\}\},\\ \{\{1,2,4\}\},\\\{\{1\},\{2,4\}\},\\\{\{2\},\{1,4\}\},\\\{\{4\},\{1,2\}\},\\\{\{1\},\{2\},\{4\}\},\\\{\{1,3,4\}\},\\\{\{1\},\{3,4\}\},\\\{\{3\},\{1,4\}\},\\\{\{4\},\{1,3\}\},\\\{\{1\},\{3\},\{4\}\},\\\{\{1,2,3\}\},\\\{\{2\},\{3,4\}\},\\\{\{3\},\{2,4\}\},\\\{\{4\},\{2,3\}\},\\\{\{2\},\{3\},\{4\}\}$$Overall there is exactly $20$ sets, so we say ${(4)\choose(3)}=20$


What he tried

  • ${(n)\choose(k)}={n\choose k}\times {(k)\choose(k)}$

Proof:

The number of sets of $k$ unique elements from a set with $n$ unique elements is by definition $n\choose k$, and by definition for each such set we have exactly ${(k)\choose(k)}$ ways to create it using subsets of the set, thus ${(n)\choose(k)}={n\choose k}\times {(k)\choose(k)}$


What I tried

Here he came to me, asking if I know a way to calculate ${(k)\choose(k)}$, I thought about some kind of recurrence relation:

$${(k)\choose(k)}=1+\sum_{i=1}^{\lfloor\frac k2\rfloor}\left({k\choose i}\left[{(k-i)\choose(k-i)}-a_i^{(k)}\right]+b_i^{(k)}\right)$$ Where $a_i^{(k)}$ is the number duplicates I get from a single case of ${k\choose i}{(k-i)\choose(k-i)}$, I know it is not so clear, so here is an example:

With $k=4,i=2$ I have ${4\choose2}(=6)$ ways to create a set with $2$ elements, and I have ${(4-2)\choose(4-2)}(=2)$ ways to complete it to have $4$ elements.

Here is the list of cases:

$$\overbrace{\{1,2\}\begin{cases}\{1,2\},\{3,4\}\\\{1,2\},\{3\},\{4\}\end{cases}}^{{4\choose2}\times{(4-2)\choose(4-2)}=12}\\\{1,3\}\begin{cases}\{1,3\},\{2,4\}\\\{1,3\},\{2\},\{4\}\end{cases}\\\{1,4\}\begin{cases}\{1,4\},\{2,3\}\\\{1,4\},\{2\},\{3\}\end{cases}\\\{2,3\}\begin{cases}\{2,3\},\{1,4\}\\\{2,3\},\{1\},\{4\}\end{cases}\\\{2,4\}\begin{cases}\{2,4\},\{1,3\}\\\{2,4\},\{1\},\{3\}\end{cases}\\\{3,4\}\begin{cases}\{3,4\},\{1,2\}\\\{3,4\},\{1\},\{2\}\end{cases}$$We can see that in each case we have exactly one case that appear in other case, hence $a_2^{(4)}=1$.

And $b_i^{(k)}$ is the number of duplicates, in the example above we have exactly $3$ elements that appear more than once: $\{\{3,4\},\{1,2\}\},\{\{2,3\},\{1,4\}\},\{\{2,4\},\{1,3\}\}$, hence $b_2^{(4)}=3$

But this doesn't work because when we look on other $i$ we will find more duplicates, for example for $k=4,i=1$ I have the case of $\{1\},\{2,4\},\{3\}$, this is duplicate of the third from last case from when $k=4,i=2$.


Here we both are stuck, can someone please help us?

Thanks


Edit:

@saulspatz point out that ${(k)\choose (k)}=B(k)$, where $B(k)$ is bell number of $k$.

From Wikipedia I found that $B(k)=\sum_{j=0}^k\left\{{k\atop j}\right\}$, where $\left\{{k\atop j}\right\}$ is Stirling numbers of second kind$=S(k,j)$.

With this I get that

$$\boxed{{(n)\choose (k)}={n\choose k}{(k)\choose (k)}={n\choose k}B(k)={n\choose k}\sum_{j=0}^k\left(\left\{{k\atop j}\right\}\right)={n\choose k}\sum_{j=0}^k\left(\frac1{j!}\sum_{i=0}^j\left((-1)^{j-i}{j\choose i}i^k\right)\right)}$$

$\endgroup$

1 Answer 1

2
$\begingroup$

$$\binom{n}{k}B(k)$$ where $B(k)$ is the Bell number of $k$. That, is we count the number of ways to choose $k$ items, times the number the number of ways to partition a set of $k$ items.

$\endgroup$

You must log in to answer this question.

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