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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with '== Counting Problems == == Sets and Multisets == == Permutations == == The twelvfold way =='
 
imported>WikiSysop
Line 6: Line 6:


== The twelvfold way ==
== The twelvfold way ==
{|border="2"  cellspacing="4" cellpadding="3" 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
| distinguishable
| <math>m^n</math>
|
|
|-
| indistinguishable
| distinguishable
|
|<math>{m\choose n}</math>
|
|-
| distinguishable
| indistinguishable
|
|
|
|-
| indistinguishable
| indistinguishable
|
|
|
|}

Revision as of 02:51, 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]
indistinguishable distinguishable [math]\displaystyle{ {m\choose n} }[/math]
distinguishable indistinguishable
indistinguishable indistinguishable