Combinatorics (Fall 2010)/Basic enumeration

From TCS Wiki
Revision as of 05:22, 8 July 2010 by imported>WikiSysop (→‎The twelvfold way)
Jump to navigation Jump to search

Counting Problems

Sets and Multisets

Permutations

The twelvfold way

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]