Stirling Number of the second kind recurrence combinatorial proof

Question

I am working with the Stirling number of the Second kind problem from the book of Principles and Techniques in Combinatorics by Chen Chuang-Chong and Koh Khee-Meng. Page 73 problem 84: Given $r,n\in \mathbb{Z}$ with $0 \le n\le r$, the Stirling number $S(n,k)$ of the second kind is defined as the number of ways of distributing $r$ distinct objects into $n$ identical boxes such that no box is empty. Show that

• (i) $S(r,3)=\frac{1}{2}(3^{r-1}+1)-2^{r-1}$;

• (ii) $S(r,r-1)=\binom{r}{2}$.

• My answer for (ii)Exactly one box will contain two objects while all the other boxes contain exactly one boxes. It suffices to consider which two elements belong to the same box, and there are $\binom{r}{2}$ ways to do so. For (i) I dont know how to do the combinatorial proof. I am trying to understand so that I can get the RHS but I failed.. ANy Help is very much appreciated. Thank you so much..

Answer 1

The second one is fine. For the first one, assign a color to the blocks(i am going to use $\color{red}{red}$ $\color{blue}{blue}$ $\color{green}{green}$), so in each partition you are coloring the numbers inside the block(assume you always put $1$ in block of color $\color{red}{red}$), so you have $3^{n-1}=|\{\color{red}{\bullet}\cup \color{green}{\bullet}\cup \color{blue}{\bullet}\}^{[n]\setminus \{1\}}|$ possible colors(functions) for the remaining elements.

Now you know that you do not want less than $3$ colors by definition, so you take out when you have exactly $2$ blocks $2*(2^{n-1}-2)+2=2^n-2$(why?) also you have to take out the case when every element is colored with $1,$ and so you get $$3^{n-1}-(2^n-2)-1=3^{n-1}-2^n+2-1=3^{n-1}-2^n+1.$$ Now, the problem is that colors are not important, i mean, if $n=3$ and you have $\color{red}{1}\color{blue}{2}\color{green}{3}$ is the same as $\color{red}{1}\color{green}{2}\color{blue}{3},$ so you have an equivalent relation on this set you produce, namely $\pi _1 \sim \pi _2$ iff $\pi _1$ is the same as $\pi _2$ up to green numbers in $\pi _1$ are blue numbers in $\pi _2$ and viceversa. So if you divide by the equivalence relation and if you understand that equivalent clases have exactly $2$ elements, you get your result.

So, to prove it "formally" you will have a function $$\varphi :\mathbb{S}_{n,3}\longrightarrow \{\color{red}{\bullet}\cup \color{green}{\bullet}\cup \color{blue}{\bullet}\}^{[n-1]}$$ but you will see that the image is going to be a restriction on that set that will give you the numbers you got in the argument.