Combinatorics (Fall 2010)/Basic enumeration: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
No edit summary
Line 1: Line 1:
== Counting Problems ==
== Counting Problems ==


== Permutations ==
== Tuples and Permutations ==
 


== Sets and Multisets ==
== Sets and Multisets ==

Revision as of 01:26, 9 July 2010

Counting Problems

Tuples and Permutations

Sets and Multisets

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]