Combinatorics

#matematik-discmath

Take two finite sets and consider a subset of the Set of all pairs Set of all pairs of elements from and . Now say we want to count the elements in . For each we can define and then get Likewise, we can define and then get

Theorem: The multiplication principle

Let be finite nonempty sets and be nonempty. Then with and . Also, if for every and for every , then .

Furthermore, .

Proof:
Each set in is clearly disjoint, so the sum of their sizes is the size of the union, by Theorem Theorem. The union of them is precisely since if then is in the set of . The same goes for , so the first part is done. From this, it immediately follows that if and for every and .

Finally, if we let we have for every , so .