Combinatorial interpretation of an identity for expressing Stirling number of the second kind using binomial coefficients

Question

Consider the identities as follows (Graham, Knuth, and Patashnik, Concrete Mathematics, Sec.6.2, p.271), $${x\brace x-2}={x+1\choose4}+2{x\choose 4}$$ and $${x\brace x-3}={x+2\choose6}+8{x+1\choose6}+6{x\choose 6}$$ where the Stirling numbers of the second kind are expressed as integral combinations of binomial coefficients. The numbers in front of the binomial coefficients are 2nd order Euler numbers.

I know that the Stirling numbers are counting the number of partition of sets. Is there any combinatorial interpretation/proof of the above identities (without converting the RHS into other binomial formulas)? Many thanks!

Answer 1

To form a partition in $x$ of $x-2$ blocks you have two options. You either:

1. have $2$ blocks of size $2$ say $\{a,b\},\{c,d\}$ such that $a<c$ and $c<b,c<d$ and the rest singletons.
2. have one block of $3$ elements and the rest singletons or $2$ blocks like before but with $b<c$.

For the first one, choose $4$ elements out of $x$ and order them as $x_1<x_2<x_3<x_4$ and then $a=x_1$ and necessarily $c=x_2$ so you have two options, either $b=x_3$ or $b=x_4$ this gives you $2$ options, so in total: $2\binom{x}{4}$.

For the second one, choose $4$ elements out of $x$ and an element $*$ so choose $4$ out of $x+1$ and if you choose $*$, just put all the other elements in a block and the rest singletons. If you did not choose the $*$ then $x_1<x_2<x_3<x_4$ and make $a=x_1$ $c=x_3$ and so $b=x_2$ and $d=x_4$. All these was done in $\binom{x+1}{4}$ options.

The second identity is similar, you consider two new elements $*_1,*_2$, and do case work as before. With some time, you probably can get it.