Combinatorics (Fall 2010)/Basic enumeration

The twelvfold way

[math]\displaystyle{ f:N\rightarrow M }[/math]

Elements of [math]\displaystyle{ N }[/math]	Elements of [math]\displaystyle{ M }[/math]	Any [math]\displaystyle{ f }[/math]	Injective (1-1) [math]\displaystyle{ f }[/math]	Surjective (on-to) [math]\displaystyle{ f }[/math]
distinguishable	distinguishable	[math]\displaystyle{ m^n\, }[/math]	[math]\displaystyle{ \left(m\right)_n }[/math]	[math]\displaystyle{ m!S(n, m)\, }[/math]
indistinguishable	distinguishable	[math]\displaystyle{ \left({m\choose n}\right) }[/math]	[math]\displaystyle{ {m\choose n} }[/math]	[math]\displaystyle{ \left({m\choose n-m}\right) }[/math]
distinguishable	indistinguishable	[math]\displaystyle{ \sum_{k=1}^m S(n,k) }[/math]	[math]\displaystyle{ \begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n\gt m\end{cases} }[/math]	[math]\displaystyle{ S(n,m)\, }[/math]
indistinguishable	indistinguishable	[math]\displaystyle{ \sum_{k=1}^m p_k(n) }[/math]	[math]\displaystyle{ \begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n\gt m\end{cases} }[/math]	[math]\displaystyle{ p_m(n)\, }[/math]