I am working my way through Combinatorics: A Guided Tour by David Mazur and I'm currently on the topic on counting set partitions;
There are two questions in the exercises which I am unsure how to tackle.
- Give a bijective proof: If $n\geq1$, then $S(n,2)=2^{n}-1$. Prove this by creating a bijection b/w the $2$ partitions of $[n]$ and the non-empty subsets of $[n-1]$.
- Give a bijective proof: If $n\geq1$, then $S(n,n-1)= N$ choose $2$. Prove this by creating a bijection b/w the $(n-1)-\text{partitions}$ of $[n]$ and the $2$ subsets of $[n]$.
(Sorry for the poor formatting, I seem to have forgotten how to format). Both $S(n,2)$ and $S(n,n-1)$ refer to Stirling Numbers of the second kind.
Anyway, I know how to provide combinatorial proofs for both these questions and can explain my reasoning well enough. I just seem to have trouble with the 'do this by creating a bijection b/w .. and ..' part.
Any and all help is appreciated! Thanks :)
For 1: if $[n] = A \cup B$ is a partition, such that the element $n$ is contained in $B$, then we map this partition to the non-empty subset $A$ of $[n - 1]$.
The inverse map: if $A$ is any non-empty subset of $[n - 1]$, then we map it to the partition $[n] = A \cup \left([n]\backslash A\right)$.
For 2: if $[n] = A_1\cup \dots\cup A_{n - 1}$ is a partition, then there is exactly one index $i$ such that $A_i$ has cardinality $2$. We then map this partition to the subset $A_i$ of $[n]$.
The inverse map: if $A$ is a two-element subset of $[n]$, then we map it to the partition such that one of the $A_i$ is $A$ and all other $A_j$'s are singletons.
It is then easy to check that these maps are inverses of each other, hence give bijections.