●●● ●●●● ●●●●● ●●●● ●●0●● Binomial coefficients ●●●● ●●●● How many ways are there to choose k things out of n possibilities? n n k丿(n-k)!k! ● Coefficients of(a+b) (a+b) a"+"a-b+…+abk+…+b
11 Binomial Coefficients ⚫ How many ways are there to choose k things out of n possibilities? ⚫ Coefficients of (a+b)n ! ( )! ! n n k n k k = − 1 ( ) 0 1 n n n n k k n n n n n a b a a b a b b k n − − + = + + + + +
●●● How to calculate binomial ●●●● ●●●●● ●●●● ●●0●● coefficients? ●●●● ●●●● o It's difficult to calculate the value of binomial coefficients by using the previous equation directly: arithmetic overflow will happen for n 12 Pascal's triangle(1654,or杨辉三角(1261) k n 1331 4641 1510105 61520156
12 How to calculate binomial coefficients? ⚫ It’s difficult to calculate the value of binomial coefficients by using the previous equation directly: arithmetic overflow will happen for n > 12! ⚫ Pascal’s triangle (1654), or 杨辉三角 (1261) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 1 1 n n n k k k − − = + −
●●● How to calculate binomial ●●●● ●●●●● ●●●● ●●0●● coefficients?(Cont ●●●● ●●●● #define maxn 100 / compute n choose m */ long binomial coef(int n, int m) int long bc[MAXNIMAXN]: /table of binomial coef*/ for(=0;i<=n;i++)bc而0]=1; for(=0; j<=n; j++)bc001 for(=1;i<=n;i++) for(=1; j<i; j++) bc[]=bc[i-1-1+bc[-1j return(bcnm])
13 How to calculate binomial coefficients? (Cont.) #define MAXN 100 /* compute n choose m */ long binomial_coef(int n, int m) { int i, j; long bc[MAXN][MAXN}; /* table of binomial coef */ for(i = 0; i <= n; i++) bc[i][0] = 1; for(j = 0; j <= n; j++) bc[j][j] = 1; for(i = 1; i <= n; i++) for(j = 1; j < i; j++) bc[i][j] = bc[i-1][j-1] + bc[i-1][j]; return (bc[n][m]); }
●●● ●●●● ●●●●● ●●●● ●●0●● Catalan Numbers ●●●● ●●●● 1(2n Cn=∑CCn n-1-k k=0 n+1(n e How many ways are there to build a balanced formula from n pairs of parentheses? Divide the formula into two parts:(........) The first part contains k pairs the second part has n 1-k pairs So the first part has Ck possibilities, while the second part has Cn- -k possibilities
Catalan Numbers ⚫ How many ways are there to build a balanced formula from n pairs of parentheses? ⚫ Divide the formula into two parts: (……)(……) ⚫ The first part contains k pairs, the second part has n- 1-k pairs. ⚫ So the first part has Ck possibilities, while the second part has Cn-1-k possibilities. 14 1 0 1 0 1 2 1, 1 n n k n k k n C C C C n n − − − = = = = +
●●● Practice 1 ●●●● ●●●●● ●●●● ●●0●● How many pieces of land? ●●●● ●●●● ohttp:/lacm.uva.es/p/v102/10213.html You are given an elliptical shaped land and you are asked to choose n arbitrary points on its boundary. Then you connect all these points with one another with straight lines (that's n*(n-1)/2 connections for n points o What is the maximum number of pieces of land you will get by choosing the points on the boundary carefully?
Practice 1: How many pieces of land? ⚫ http://acm.uva.es/p/v102/10213.html ⚫ You are given an elliptical shaped land and you are asked to choose n arbitrary points on its boundary. Then you connect all these points with one another with straight lines (that’s n*(n-1)/2 connections for n points). ⚫ What is the maximum number of pieces of land you will get by choosing the points on the boundary carefully? 15