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