How do you do fellow Stackers, recently I've beeen studying combinatorics and surprise surprise, failing at it. My questions is probably pretty simple, in fact, it can be considered a duplicate of [Division of 11 people into 3 groups with at least 2 people in each ]. The reason I'm opening the thread is that I cannot understand the answer that was given and I'd like to be able to try and generalize it (and fail at it… again…).
Anyway, let's suppose that we want to partition a set of cardinality $n$ into $k$ subsets with at least cardinality $x$. That means we want to subtract the partitions of $k$ subsets in which one of them does not have cardinality $\ge$ (so their size is at most $x-1$) from the total number of partitions.
My attempt at this is noting that if such subset exists then the other partitions don't matter at all.
I'll try to unwrap my thought with the example of $n=11$ , $k=3$ and $x=2$
So, there are {11,3} (the brackets denote Stirling numbers of the second kind). From this we will subtract those partitions in which one of the blocks has $1$ element, so 11 * {10,2} (which are the ways to choose the lone element and from the $10$ remaining divide them into 2 subsets). Now, such partitions already attain those in which there are $2$ lone elements, so no need to take any other way or add any that might've been double counted. As such, the number we are looking for is {11,3} – 11 *{10,2}.
But this is not the same as the answer that was given and not only am I not competent enough to say this one's right, I'm also not competent enough to say why this one's wrong.
Help of any kind is of great assistance! … Ugh. What can I say, combinatorics…
Best Answer
This is what happened: You organized the people in $3$ teams ${11\brace 3}$ then you select one and take it out so you select the outsider, say $x$, and computed $11\cdot {10 \brace 2}.$ The problem here is that notice that when you select this outsider $x$ it also can have been inside the choices of ${10\brace 2}.$ For example, the partition $\{\{1\},\{2\},\{3,4,5,6,7,8,9,10,11\}\}$ is counted twice, when $x=1$ and when $x=2.$ So you have to give back these problem(this process is called Inclusion-exclusion), so you have to choose $2$ elements out of the $11$(to place as singletons) in $\binom{11}{2}$ ways and add it back, so the actual answer would be: $${11\brace 3}-11{10\brace 2}+\binom{11}{2}=22935.$$ Notice that you can write this as: $$\sum _{k=0}^2(-1)^{k}\binom{11}{k}{11-k \brace 3-k}.$$ This is an actual general result, if you call ${n\brace k}_{\geq x}$(they actually have a name, they are called Associated Stirling numbers of second kind) the partitions of $[n]$ in $k$ blocks of size at least $x,$ then $${n\brace k}=\sum _{i=0}^n\binom{n}{i}{n-i\brace k-i}_{\geq 2}.$$ Notice that this is like taking the blocks that are singletons(in the binomial) and the rest in the Stirling. Binomial transformation gives you the result.