Combinatorics (Fall 2010)/Basic enumeration: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 7: | Line 7: | ||
== The twelvfold way == | == The twelvfold way == | ||
{|border="2" cellspacing="4" cellpadding=" | {|border="2" cellspacing="4" cellpadding="10" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;" | ||
|- | |- | ||
!bgcolor="#A7C1F2" | Elements of <math>N</math> | |||
!bgcolor="#A7C1F2" | Elements of <math>M</math> | |||
!bgcolor="#A7C1F2" | Any <math>f</math> | |||
!bgcolor="#A7C1F2" | Injective (1-1) <math>f</math> | |||
!bgcolor="#A7C1F2" | Surjective (on-to) <math>f</math> | |||
|- | |- | ||
| distinguishable | |align="center"| ''distinguishable'' | ||
| distinguishable | |align="center"| ''distinguishable'' | ||
| <math>m^n</math> | |align="center"| <math>m^n\,</math> | ||
| | |align="center"| <math>\left(m\right)_n</math> | ||
| | |align="center"| <math>m!S(n, m)\,</math> | ||
|- | |- | ||
| indistinguishable | |align="center"| ''indistinguishable'' | ||
| distinguishable | |align="center"| ''distinguishable'' | ||
| | |align="center"| <math>\left({m\choose n}\right)</math> | ||
|<math>{m\choose n}</math> | |align="center"|<math>{m\choose n}</math> | ||
| | |align="center"|<math>\left({m\choose n-m}\right)</math> | ||
|- | |- | ||
| distinguishable | |align="center"| ''distinguishable'' | ||
| indistinguishable | |align="center"| ''indistinguishable'' | ||
| | |align="center"| <math>\sum_{k=1}^m S(n,k)</math> | ||
| | |align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math> | ||
| | |align="center"| <math>S(n,m)\,</math> | ||
|- | |- | ||
| indistinguishable | |align="center"| ''indistinguishable'' | ||
| indistinguishable | |align="center"| ''indistinguishable'' | ||
| | |align="center"| <math>\sum_{k=1}^m p_k(n)</math> | ||
| | |align="center"| <math>\begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n>m\end{cases}</math> | ||
| | |align="center"| <math>p_m(n)\,</math> | ||
|} | |} | ||
Revision as of 05:22, 8 July 2010
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] |