1、Binomial Coefficients, Inclusion-exclusion principle,Lecture 13: Oct 31,A,B,C,D,1,Plan,Binomial coefficients, combinatorial proofInclusion-exclusion principle,2,Binomial Theorem,We can compute the coefficients ci by counting arguments.,e.g.,(expanding by taking either 1 or x in each factor and multi
2、ply),(grouping the terms with the same power and add),So in this case, c0 = 1, c1 = 3, c2 = 3, c3 = 1.,3,Binomial Theorem,We can compute the coefficients ci by counting arguments.,n factors,Each term corresponds to selecting 1 or x from each of the n factors. The coefficient ck is equal to the numbe
3、r of terms with exactly k xs. Each term with exactly k xs corresponds to choosing the k positions of x. Therefore,These are called the binomial coefficients.,4,Binomial Theorem,(1+X)1 =,(1+X)0 =,(1+X)2 =,(1+X)3 =,1,1 + 1X,1 + 2X + 1X2,1 + 3X + 3X2 + 1X3,(1+X)4 =,1 + 4X + 6X2 + 4X3 + 1X4,5,We can see
4、 that a coefficient is the sum of two coefficients in the previous level. This is called the Pascals formula and we will prove it soon.,Binomial Coefficients,In general we have the following identity:,When x=1, y=1, it implies that,because if we choose k xs then there are n-k ys.,Corollary:,The sum
5、of the binomial coefficients is equal to 2n.,6,Binomial Coefficients,When x=-1, y=1, it implies that,In general we have the following identity:,Corollary:,The sum of “odd” binomial coefficients is equal to the sum of “even” binomial coefficients.,7,Proving Identities,Direct proof:,Combinatorial proo
6、f:,Number of ways to choose k items from n items= number of ways to choose n-k items from n items,One can often prove identities about binomial coefficients by a counting argument.,8,Finding a Combinatorial Proof,A combinatorial proof is an argument that establishes an algebraic fact by relying on c
7、ounting principles. Many such proofs follow the same basic outline:1. Define a set S. 2. Show that |S| = n by counting one way. 3. Show that |S| = m by counting another way. 4. Conclude that n = m.,Double counting,9,Proving Identities,Pascals Formula,Direct proof:,10,Proving Identities,Pascals Formu
8、la,Combinatorial proof:,The LHS is number of ways to choose k elements from n+1 elements. Let the first element be x. If we choose x, then we need to choose k-1 elements from the remaining n elements, and number of ways to do so is If we dont choose x, then we need to choose k elementsfrom the remai
9、ning n elements, and number of ways to do so is This partitions the ways to choose k elements from n+1 elements,therefore,11,Combinatorial Proof,Consider we have 2n balls, n of them are red, and n of them are blue.,The RHS is number of ways to choose n balls from the 2n balls. To choose n balls, we
10、can - choose 0 red ball and n blue balls, number of ways = - choose 1 red ball and n-1 blue balls, number of ways = choose i red balls and n-i blue balls, number of ways = choose n red balls and 0 blue ball, number of ways =Hence number of ways to choose n balls is also equal to the LHS.,12,Another
11、Way to Combinatorial Proof (Optional),We can also prove the identity by comparing a coefficient of two polynomials.,Consider the identity,Consider the coefficient of xn in these two polynomials.Clearly the coefficient of xn in (1+x)2n is equal to the RHS.,So the coefficient of xn in (1+x)n(1+x)n is
12、equal to the LHS.,13,Exercises,Give a combinatorial proof of the following identify.,Can you give a direct proof of it?,Prove that,14,Plan,Binomial coefficients, combinatorial proofInclusion-exclusion principle,15,If sets A and B are disjoint, then |A B| = |A| + |B|,A,B,What if A and B are not disjo
13、int?,Sum Rule,16,For two arbitrary sets A and B,A,B,Inclusion-Exclusion (2 sets),17,Inclusion-Exclusion (2 sets),Let S be the set of integers from 1 through 1000 that are multiples of 3 or multiples of 5.,Let A be the set of integers from 1 to 1000 that are multiples of 3.,Let B be the set of intege
14、rs from 1 to 1000 that are multiples of 5.,A,B,It is clear that S is the union of A and B, but notice that A and B are not disjoint.,|A| = 1000/3 = 333,|B| = 1000/5 = 200,A B is the set of integers that are multiples of 15, and so |A B| = 1000/15 = 66,So, by the inclusion-exclusion principle, we hav
15、e |S| = |A| + |B| - |A B| = 467.,18,A,B,C,|A B C| = |A| + |B| + |C| |A B| |A C| |B C|+ |A B C|,Inclusion-Exclusion (3 sets),19,Inclusion-Exclusion (3 sets),From a total of 50 students:,30 know Java 18 know C+ 26 know C# 9 know both Java and C+ 16 know both Java and C# 8 know both C+ and C# 47 know a
16、t least one language.,How many know none?How many know all?,|A B C| = |A| + |B| + |C| |A B| |A C| |B C| + |A B C|,|A|,|B|,|C|,|A B|,|A C|,|B C|,|A B C|,|A B C|,47 = 30 + 18 + 26 9 16 8 + |A B C|,|A B C| = 6,20,A,B,C,|A B C D| = |A| + |B| + |C| + |D| |A B| |A C| |A D| |B C| |B D| |C D|+ |A B C| + |A
17、B D| + |A C D| + |B C D| |A B C D |,Inclusion-Exclusion (4 sets),D,21,Inclusion-Exclusion (n sets),What is the inclusion-exclusion formula for the union of n sets?,22,sum of sizes of all single sets sum of sizes of all 2-set intersections+ sum of sizes of all 3-set intersections sum of sizes of all
18、4-set intersections+ (1)n+1 sum of sizes of intersections of all n sets,Inclusion-Exclusion (n sets),23,Inclusion-Exclusion (n sets),We give a proof of the inclusion exclusion formula. Consider an element x in the intersection of A1, A2, , Ak. What is the contribution of this element to the RHS of t
19、he formula? It is counted +1 in |A1|, |A2|, , |Ak|, so it is counted +k for single sets. It is counted -1 in -|A1A2|, -|A1A3|, , -|Ak-1Ak|, so it is counted (k choose 2) for two set intersections. It is counted +1 in |A1A2A3|, , |Ak-2Ak-1Ak|, so it is counted +(k choose 3) for three set intersection
20、s. And so on So its contribution to the formula is,see slide 7,24,Each element is counted exactly once, and so the formula is correct.,Applications,In a Christmas party, everyone brings his/her present. There are n people and so there are totally n presents. Suppose the host collects and shuffles al
21、l the presents. Now everyone picks a random present. What is the probability that no one picks his/her own present?,25,Using inclusion-exclusion we can show that the answer is 1/e where e=2.71828,Given a number n, how many numbers from 1 to n are relatively prime to n?,Let,Using inclusion-exclusion
22、we can show that the answer is n(1-1/p1)(1-1/p2)(1-1/pn),Quick Summary,We have studied how to determine the size of a set directly.The basic rules are the sum rule, product rule, and the generalized product rule.We apply these rules in counting permutations and combinations,which are then used to count other objects like poker hands.Then we prove the binomial theorem and study combinatorial proofs of identities.Finally we learn the inclusion-exclusion principle and see some applications.Later we will learn how to count “indirectly” by “mapping”.,26,
