●●● ●●●● ●●●●● ●●●● ●●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…