Combinatorics (Fall 2010)/Basic enumeration

Sets and Multisets

Let[math]\displaystyle{ S=\{x_1,x_2,\ldots,x_n\} }[/math] be an [math]\displaystyle{ n }[/math]-element set, or [math]\displaystyle{ n }[/math]-set for short. Let [math]\displaystyle{ 2^S=\{T\mid T\subset S\} }[/math] denote the set of all subset of [math]\displaystyle{ S }[/math]. [math]\displaystyle{ 2^S }[/math] is called the power set of [math]\displaystyle{ S }[/math].

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]