Programming Interest Group http://www.comp.hkbu.eduhk/-chxw/pig/index.htm Tutorial five ●●●●● Combinatorics Number Theory 8080
1 Programming Interest Group http://www.comp.hkbu.edu.hk/~chxw/pig/index.htm Tutorial Five Combinatorics & Number Theory
●●● ●●●● ●●●●● ●●●● ●●0●● Outline ●●●● ●●●● ● Combinatorics(组合) Basic Counting Techniques Recurrence relations Binomial coefficients ● Number Theory Prime number ° Congruences ● Fermat' s Theorem o Euler's Theorem
2 Outline ⚫ Combinatorics (组合) ⚫ Basic Counting Techniques ⚫ Recurrence Relations ⚫ Binomial Coefficients ⚫ Number Theory ⚫ Prime Number ⚫ Congruences ⚫ Fermat’s Theorem ⚫ Euler’s Theorem
●●● ●●●● ●●●●● ●●●● ●●0●● Part l: combinatorics ●●●● ●●●● Combinatorics is the mathematics of counting It appears to be a collection of unrelated puzzles chosen at random Given n letters and n addressed envelopes, in how many ways can the letters be placed in the envelopes so that no letter is in the correct envelope? E.g. 2: (a Google interview problem o There are n stages. Every time you can go up either 1 stage or 2 stages. How many different ways can you reach the last stage?
3 Part I: Combinatorics ⚫ Combinatorics is the mathematics of counting. ⚫ It appears to be a collection of unrelated puzzles chosen at random. ⚫ E.g. 1: ⚫ Given n letters and n addressed envelopes, in how many ways can the letters be placed in the envelopes so that no letter is in the correct envelope? ⚫ E.g. 2: (a Google interview problem) ⚫ There are n stages. Every time you can go up either 1 stage or 2 stages. How many different ways can you reach the last stage?
●●● ●●●● ●●●●● ●●●● ●●0●● Basic Counting Techniques ●●●0 ●●●● ● Product rule If there are al possibilities from set a and b possibilities from set B, then there are Ax B ways to combine one from a and one from b E.g., suppose you own 5 shirts and 4 pants, then there are 5x4 =20 different ways you can get dressed ● Sum rule If there are a possibilities from set a and b possibilities from set B, then there are A+b ways for either A or b to occur(assuming the elements of a and B are distinct)
4 Basic Counting Techniques ⚫ Product Rule ⚫ If there are |A| possibilities from set A and |B| possibilities from set B, then there are |A|x|B| ways to combine one from A and one from B. ⚫ E.g., suppose you own 5 shirts and 4 pants, then there are 5x4 =20 different ways you can get dressed. ⚫ Sum Rule ⚫ If there are |A| possibilities from set A and |B| possibilities from set B, then there are |A|+|B| ways for either A or B to occur (assuming the elements of A and B are distinct)
●●● ●●●● ●●●●● ●●●● ●●0●● Basic Counting Techniques ●●●0 ●●●● ● Inclusion-Eⅹc| usion formula ●|AUB|=|A+B|-|A∩B ●| AUBUC|=A+B|+c|-|AnB|-|Anc|-|B∩c +|AnB∩c A B A C
5 Basic Counting Techniques ⚫ Inclusion-Exclusion Formula: ⚫ |AUB| = |A| + |B| - |A∩B| ⚫ |AUBUC| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B ∩C| A B C A B