Combinatorial arguments for two stirling numbers

Question

I'm trying to use combinatorial arguments to find simple formulas for $\begin{Bmatrix} n\\ 2 \end{Bmatrix}$ and $\begin{Bmatrix} n\\ n-2 \end{Bmatrix}$

I've used combinatorial arguments to prove equalities, but not pretty sure how I can find simple formulas for those Stirling numbers. Here's a table with Stirling numbers and Bell numbers: For $\begin{Bmatrix} n\\ 2 \end{Bmatrix}$ , I think the formula is $2^{n-1}-1$. Can I understand that as assigning $n-1$ students to 2 classrooms, and avoid the empty case?

Answer 1

The Stirling number of the second kind, $\left\{ \begin{array}{c} n\\k \end{array} \right\}$, gives the number of ways to partition the set $A=\{1,2,\cdots,n\}$ into $k$ classes.$^1$

So $$\left\{ \begin{array}{c} n\\2 \end{array} \right\}=\frac{2^n-2}{2}=2^{n-1}-1.$$

We can put each item (an element of $A$) into one of two bins. Since we don't want empty bins, we subtract $2.$ Then, since we don't distinguish between bins, we divide by $2.$

---

Now we look at $\left\{ \begin{array}{c} n\\n-2 \end{array} \right\}$.

Most of the elements will end up in its own bin. We have two cases: ($1$) three in one bin, or ($2$) there are two bins, each with two elements:

$$\left\{ \begin{array}{c} n\\n-2 \end{array} \right\}=\binom{n}{3}+\frac{1}{2}\binom{n}{2}\binom{n-2}{2}=\binom{n}{3}+3\binom{n}{4}.$$

In both combinatorial expressions, $\binom{n}{3}$ is the number of ways of executing part $(1)$.

For part $(2)$, we could either choose two to be in a bin, then choose two of the remaining $n-2$. Because we could pick the two pairs in either order, we divide by two.

Alternatively (as expressed in the last sum) we can choose the four which gives $\binom{n}{4}$, then we take any of the four and choose the other one of the remaining three to go in the same bin: $\binom{3}{1}=3$.

---

$^1$Wilf, H. S., $\textbf{generatingfunctionology}$, 3rd edition, CRC Press, p. 18.

Answer 2

An alternative for $\left\{{n}\atop{2}\right\}$:

You want to divide $n$ kids into $2$ non empty groups. Kids $2,…,n$ have two options each; be in the same group as the first kid or not, hence $2^{n-1}$. However, we don’t want all of them to opt to be in the same group as the first kid because then the second group will be empty, hence the subtraction by $1$.