6.042/18.] Mathematics for Computer Science March 30, 2005 Srini devadas and Eric Lehman Notes for Recitation 13 Basic Counting notions a bijection or bijective function is a function f: X Y such that every element of the codomain is related to exactly one element of the domain. here is an example of lection X 1 codomain Rule 1 (Bijection Rule). If there exists a bijection f: A-B, then A=B Rule 2(Sum Rule). If A1,..., An are disjoint sets, the k=1 Rule 3 (Product Rule). IfPi, P2,... Pn are sets, then ×P2×…Pn=|f1|·|P…|Pn two different elements of X that are mapped to the same element ofr. f: X-Y there exist Rule 4(Pigeonhole Principle). IfX>Y then for every functio If more than n pigeons are assigned to n holes, then there must exist two pigeons assigned to the same hole� � � � 6.042/18.062J Mathematics for Computer Science March 30, 2005 Srini Devadas and Eric Lehman Notes for Recitation 13 Basic Counting Notions A bijection or bijective function is a function f : X Y → such that every element of the codomain is related to exactly one element of the domain. Here is an example of a bijection: X f Y a PP 1 PPPP domain �q b PP 2 codomain c P �PPqP PP 3 PPPPq d � 4 e - 5 Rule 1 (Bijection Rule). If there exists a bijection f : A → B, then |A| = | | B . Rule 2 (Sum Rule). If A1, . . . , An are disjoint sets, then: n |A1 ∪ · · · ∪ An| | = Ak| k=1 Rule 3 (Product Rule). If P1, P2, . . . Pn are sets, then: |P1 × P2 × · · · × Pn| = | | · · · | P1| · |P2 Pn| Rule 4 (Pigeonhole Principle). If |X > | | |Y , then for every function f : X Y there exist two different elements of X that are mapped to the same element of Y . → “If more than n pigeons are assigned to n holes, then there must exist two pigeons assigned to the same hole