香港浸会大学：Programming Interest Group（PPT讲稿）Combinatorics & Number Theory

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

●●● ●●●● ●●●●● ●●●● ●●0●● Basic Counting Techniques ●●●● ●●●● ● Permutations o a permutation is an arrangement of n items where every item appears exactly once o There are n! different permutations o 2-1 sn! sn-1=====> n! is a very large number 232 4,294.967296 10!=3,628800 11!=39916800 12!=479,001.600 13!=6,227,020,800>232

6 Basic Counting Techniques ⚫ Permutations ⚫ A permutation is an arrangement of n items, where every item appears exactly once. ⚫ There are n! different permutations. ⚫ 2 n-1 ≤ n! ≤ nn-1 =====> n! is a very large number. ⚫ 2 32 = 4,294,967,296 ⚫ 10! = 3,628,800 ⚫ 11! = 39,916,800 ⚫ 12! = 479,001,600 ⚫ 13! = 6,227,020,800 > 232

●●● ●●●● ●●●●● ●●●● ●●0●● Basic Counting Techniques ●●●● ●●●● ● Number of subsets o a subset is a selection of elements from n possible items. ( including the empty set) o There are 2n distinct subsets of n things o E.g., set a, b, c has 8(=23)subsets ●Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}

7 Basic Counting Techniques ⚫ Number of subsets ⚫ A subset is a selection of elements from n possible items. (including the empty set) ⚫ There are 2 n distinct subsets of n things. ⚫ E.g., set {a, b, c} has 8 (=23 ) subsets: ⚫ Ф, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b ,c}

●●● ●●●● ●●●●● ●●●● ●●0●● Recurrence Relations ●●●● ●●●● e Recurrence relation is an equation which is defined in terms of itself ●E.g.1 an an-1 +1,a1=1 E.g.2:an=2 h-1,a, 2 da=2n o E.g. 3: an=nan-1, a1=1 →an=n!

8 Recurrence Relations ⚫ Recurrence relation is an equation which is defined in terms of itself. ⚫ E.g. 1: an = an-1 + 1, a1 =1 ⚫ ➔ an = n ⚫ E.g. 2: an = 2an-1 , a1 =2 ⚫ ➔ an = 2n ⚫ E.g. 3: an = nan-1 , a1 =1 ⚫ ➔ an = n!

●●● ●●●● ●●●●● ●●●● ●●0●● Recurrence relations ●●●● ●●●● o The interview question from Google To reach the nth stage, there are two possibilities First reach the(n-2)th stage, then go to the nth stage directly First reach the(n-1)th stage, then go to the nth stage We can have the following recurrence relation ●an=an+a, n-2 a1=1,a,=2

9 Recurrence Relations ⚫ The interview question from Google ⚫ To reach the nth stage, there are two possibilities: ⚫ First reach the (n-2)th stage, then go to the nth stage directly ⚫ First reach the (n-1)th stage, then go to the nth stage ⚫ We can have the following recurrence relation: ⚫ an = an-1 + an-2 ⚫ a1 = 1, a2 = 2

●●● ●●●● ●●●●● ●●●● ●●0●● Fibonacci Numbers ●●●0 ●●●● n1+Fn2;F0=0;F1 0,1,1,2,3,5,8,13,21,34,55, …=-061803 ●C| osed form 1+√5 Fn=() 2 2)/5 It can easily proved by mathematical induction ● Golden ratio 161803 o Fibonacci numbers grow exponentially

10 ⚫ Fn = Fn-1 + Fn-2 ; F0 = 0; F1 = 1 ⚫ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … ⚫ Closed form: ⚫ It can easily proved by mathematical induction. ⚫ Golden ratio: ⚫ Fibonacci numbers grow exponentially. Fibonacci Numbers 1 5 1 5 (( ) ( ) ) / 5 2 2 n n F n + − = − 1 5 1.61803 2  + = = = -0.61803…