Stirling number of the 2nd kind with pigeonhole theorem

Question

I have just learnt Stirling number of the 2nd kind and I was also given a hint that this involves the pigeonhole theorem, but I have no idea how to approach this question. Any help would be much appreciated!

Answer 1

Hint: First remember that ${n\brace k}$ means the number of ways to partition $n$ elements into $k$ non empty blocks (without any order).

If you have $3$ out of the $n$ elements in a block, how many elements are left? How many blocks are left? So how many elements per block are there left? (notice that there are $n-3$ elements and $n-3$ blocks, so there should be one element per block. Otherwise, one block would be empty!) That gives you $\binom{n}{3}\cdot 1,$ because you just have to care who are the elements that are together in the block of $3$ elements, the rest of them are in individual singletons.

Now you do not want to put $3$ elements in one block (you have done it before!), but then the maximal number of elements in one block has to be $2$(Pidgeon principle again) and so the two remaining elements ($n-(n-2)=2$ from the ones that have to determine a block) have to be put in two different blocks.

You have, then, $2$ blocks in which there are two elements each. Choose the $2$ elements for the first block in $\binom{n}{2}$ ways and, from the remaining $n-2,$ choose the other $2$ in $\binom{n-2}{2}$ ways. Notice that we use the word first, so we are giving this $2$ blocks an order. We can not do this! Eliminate the order.

---

Example: Suppose $n=4,$ then $n-2=2$ notice that we can have the following distribution. Either there is one element alone, which forces to have $3$ elements in the other block like in $\{\{1\},\{2,3,4\}\}$ or there are two blocks containing $2$ elements like in $\{\{1,2\},\{3,4\}\}.$

Notice that to create the first way we can choose who are the elements that are in the block of $3$ elements. In how many ways? $\binom{4}{3}.$ Notice that the remaining objects is forced to be alone in another block (so we do not have to do anything to take this into consideration).

For the second way, we want to choose the two pair of elements that are together. We can do this as $\binom{4}{2}$ to choose the first two, and then, from the remainder $4-2=2$ we can choose the other two. We get, by multiplication principle, $\binom{4}{2}\binom{2}{2}$ ways. The problem, tho, is that you gave this blocks an order, to take out the two possible orders, you divide by $2$ giving you $\frac{1}{2}\binom{4}{2}\binom{2}{2}.$

Putting the two ways together, you get your result.