[Math] Number of partitions of [8] into 2 blocks of different sizes

Question

Question:

What is the number of partitions of $[8]$ into two blocks, in which the two blocks do not have the same size? (where $[8]$ denotes the set $\{1,2,\dots,8\}$)

So the word "partitions" leads me to believe the Stirling Numbers of the Second Kind are involved, namely $S(8,2)$ and then applying some inclusion-exclusion principles to subtract out the bad ones (I'm not too certain how though), but what I was wondering is if this problem can be solved by simply adding ${{8}\choose{1}} + {{8}\choose{2}} + {{8}\choose{3}}$ since the only options are to partition the set into parts of 1 and 7, 2 and 6, or 3 and 5, since the parts cannot have the same size. Is the latter method correct or am I missing something?

Answer 1

Your considerations are fine and we can verify it by calculating it the other way round. The number of partitions of $[8]$ into two non-empty blocks with unequal size is the number ${8\brace 2}$ of all partitions of $[8]$ into two non-empty blocks minus the number $\frac{1}{2}\binom{8}{4}$ of two equal sized blocks.

We obtain \begin{align*} \binom{8}{1}+\binom{8}{2}+\binom{8}{3}&=8+28+56=92\\ {8\brace 2}-\frac{1}{2}\binom{8}{4}&=127-\frac{1}{2}\cdot70=92 \end{align*}