2018 - Page 19 of 41 - Shawn Zhong

6.5 Generalized Permutations and Combinations

Permutations with Repetition • Theorem 1 ○ The number of r-permutations of a set of n objects with repetition allowed is ○ GP(n,r) n^r • Proof ○ There are n ways to select an element of the set ○ for each of the r positions in the r-permutation when repetition is allowed ○ Hence, by the product rule there are n^r r-permutations with repetition. • Example ○ How many strings of length r can be formed from the uppercase letters of the English alphabet? ○ The number of such strings is 〖26〗^r ○ which is the number of r-permutations of a set with 26 elements • Example 2 ○ How many function are there f:A→B where |A|=k, and |B|=m? m^k Combinations with Repetition • Example ○ How many ways are there to select five bills from a box containing at least five of each of the following denominations: $1, $2, $5, $10, $20, $50, and $100? ○ Place the selected bills in the appropriate position of a cash box illustrated below: ○ Some possible ways of placing the five bills: ○ The number of ways to select five bills corresponds to ○ the number of ways to arrange six bars and five stars in a row. ○ This is the number of unordered selections of 5 objects from a set of 11. ○ Hence, there are § C(11,5)=11!/5!6!=462 ○ ways to choose five bills with seven types of bills • Theorem 2 ○ The number of r-combinations from a set with n elements when repetition of elements is allowed is ○ C(n+r−1,r)=C(n+r−1,n−1) • Proof ○ Each r-combination of a set with n elements with repetition allowed can be represented by a list of n – 1 bars and r stars. ○ The bars mark the n cells containing a star for each time the ith element of the set occurs in the combination. ○ The number of such lists is C(n+r−1,r) ○ because each list is a choice of the r positions to place the stars ○ from the total of n+r−1 positions to place the stars and the bars. ○ This is also equal to C(n+r−1,n−1) ○ which is the number of ways to place the n – 1 bars • Example 1 ○ How many solutions does the equation x_1+x_2+x_3=11 (x_1,x_2,x_3∈Z+ ) have ○ Each solution corresponds to a way to select 11 items from a set with 3 elements ○ x_1 elements of type one, x_2 of type two, and x_3 of type three. ○ By Theorem 2 it follows that the number of solution is ○ C(3+11−1,11)=C(13,11)=C(13,2)=(13⋅12)/(1⋅2)=78 • Example 2 ○ Suppose that a cookie shop has four different kinds of cookies. ○ How many different ways can six cookies be chosen? ○ The number of ways to choose six cookies is ○ the number of 6-combinations of a set with four elements. ○ By Theorem 2 the number of ways to choose six cookies from the four kinds is ○ C(9,6)=C(9,3)=(9⋅8⋅7)/(1⋅2⋅3)=84 Permutations and Combinations with and without Repetition

6.4 Binomial Coefficients and Identities

$Powers of Binomial Expressions • A binomial expression is the sum of two terms, such as x+y. • (More generally, these terms can be products of constants and variables.) • We can use counting principles to find the coefficients of (x+y)^n where n∈Z+. • To illustrate this idea, we first look at the process of expanding (x+y)^3. • (x+y)(x+y)(x+y) expands into a sum of terms that are the product of a term from each of the three sums. • Terms of the form x^3,x^2 y.xy^2,y^3 arise. • The question is what are the coefficients? ○ To obtain x^3, an x must be chosen from each of the sums. ○ There is only one way to do this. So, the coefficient of x^3 is 1. ○ To obtain x^2 y, an x must be chosen from two of the sums and a y from the other. ○ There are (█(3@2)) ways to do this and so the coefficient of x^2 y is 3. ○ To obtain xy^2, an x must be chosen from of the sums and a y from the other two. ○ There are (█(3@1)) ways to do this and so the coefficient of xy^2 is 3. ○ To obtain y^3, a y must be chosen from each of the sums. ○ There is only one way to do this. So, the coefficient of y^3 is 1. • We have used a counting argument to show that (x+y)^3=x^3+3x^2 y+3xy^2+y^3 Binomial Theorem • Binomial Theorem ○ Let x and y be variables, and n a nonnegative integer. Then: ○ (x+y)^n=∑_(j=0)^n▒〖(█(n@j)) x^(n−j) y^j 〗=(█(n@0)) x^n+(█(n@1)) x^(n−1) y+⋯+(█(n@n−1))xy^(n−1)+(█(n@n)) y^n • Proof ○ We use combinatorial reasoning. ○ The terms in the expansion of (x+y)^n are of the form x^(n−j) y^j for j=0,1,2,…,n ○ To form the term x^(n−j), it is necessary to choose n−j xs from the n sums. ○ Therefore, the coefficient of x^(n−j) is (█(n@n−j)) which equals (█(n@j)). Using the Binomial Theorem • What is the coefficient of x^12 y^13 in the expansion of (2x−3y)^25? • We view the expression as (2x+(−3y))^25. • By the binomial theorem ○ (2x+(−3y))^25=∑_(j=0)^25▒〖(█(25@j)) (2x)^(25−j) (−3y)^j 〗 • Consequently, the coefficient of x^12 y^13 in the expansion is obtained when j = 13. A Useful Identity • Corollary 1 ○ With n≥0, ∑_(k=0)^n▒(█(n@k)) =2^n • Proof (using binomial theorem) ○ With x = 1 and y = 1, from the binomial theorem we see that: ○ 2^n=(1+1)^2=∑_(k=0)^n▒〖(█(n@k)) 1^k 1^(n−k) 〗=∑_(k=0)^n▒(█(n@k)) • Proof (combinatorial) ○ Consider the subsets of a set with n elements. ○ There are (█(n@0)) subsets with zero elements, (█(n@1)) with one element, (█(n@2)) with two elements, …, and (█(n@n)) with n elements ○ Therefore the total is ∑_(k=0)^n▒(█(n@k)) ○ Since, we know that a set with n elements has 2^n subsets, we conclude: ○ ∑_(k=0)^n▒(█(n@k)) =2^n Pascal’s Identity • Pascal’s Identity ○ If n and k are integers with n ≥ k ≥ 0, then ○ (█(n+1@k))=(█(n@k−1))+(█(n@k)) • Proof ○ Let T be a set where |T|=n+1,a∈T, and S=T−{a} ○ There are (█(n+1@k)) subsets of T containing k elements. ○ Each of these subsets either: § contains a with k−1 other elements, or § contains k elements of S and not a. ○ There are § (█(n@k−1)) subsets of k elements that contain a § since there are (█(n@k−1)) subsets of k − 1 elements of S § (█(n@k)) subsets of k elements of T that do not contain a § because there are (█(n@k)) subsets of k elements of S. ○ Hence § (█(n+1@k))=(█(n@k−1))+(█(n@k)) Pascal’s Triangle • The nth row in the triangle consists of the binomial coefficients (█(n@k)), k=0,1,…,n • By Pascal’s identity, adding two adjacent binomial coefficients results is • the binomial coefficient in the next row between these two coefficients.$

Math 541 – 4/6

$Homework 8 Question 3 • Statement ○ If G is a group with |G|≤11, and ├ d┤ ||G|┤, then G has a subgroup of order d • Proof ○ For |G|=2,3,5,7,11 § |G| is prime, thus cyclic ○ For |G|=4,6,9,10 § |G| is product of two primes, so use the Cauchy s Theorem ○ For |G|=8 § d∈{1,2,4,8} § When d=1,2,8, this is obvious § So assume d=4 § If G contains an element of order 4, then we are done § So, we may assume |g|=2,∀g∈G∖{1}, then G is abelian § Let a,b∈G∖{1}. Let H≔{1,a,b,ab} § H is closed under inverse □ The inverse of every element of G is itself § H is closed under multiplication □ ■8(⋅&1&a&b&ab@1&1&a&b&ab@a&a&1&ab&b@b&b&ab&1&a@ab&ab&b&a&1) Lemma 56 • Statement ○ Let G be a finite abelian group of order mn, where (m,n)=1 ○ If M={x∈G│x^m=1}, N={x∈G│x^n=1}, then ○ M,N≤G and the map α:M×N→G given by (g,h=gh is an isomorphism ○ Moreover, if m,n≠1, then M and N are nontrivial • Proof ○ M,N≤G § It suffices to check M≤G § M≠∅, since 1∈M § If x,y∈M, then (xy^(−1) )^m=x^m (y^m )^(−1)=1. Thus xy^(−1)∈M ○ MN=G § Choose r,s∈Z s.t. mr+ns=1 § Let g∈G, then g=g^(mr+ns)=g^mr g^ns § (g^mr )^n=(g^mn )^r=(g^|G| )^r=1 by Lagrange s Theorem § Similarly, (g^ns )^m=1 § So, g^ns∈M, g^mr∈N, so g∈MN § Therefore MN=G ○ M∩N={1} § Let g∈M∩N, then g^m=1=g^n § Then ├ |g|┤ |m┤ and ├ |g|┤ |n┤ § Since (m,n)=1,|g|=1 § Thus M∩N={1} ○ By Lemma 55, M∩N={1} and MN=G⇒α is an isomorphism ○ M and N are nontrivial § Suppose m≠1 § Let p be a prime divisor of m § Then G contains an element z of order p, by Cauchy s Theorem § z∈M, so M≠{1} § Similarly, if n≠1, N≠{1} Corollary 57 • Statement ○ Let G be a finite abelian group, and p be a prime divisor of |G| ○ Choose m∈Z( 0) s.t. |G|=p^m n and p∤n ○ Then G≅P×T, where P,T≤G, |P|=p^m, and p∤|T| • Intuition ○ If |G|=p_1^(m_1 ) p_2^(m_2 )…p_n^(m_n ) ○ This corollary says G≅P_1×…×P_n, where |P_i |=p_i^(m_i ) ○ This reduces the Fundamental Theorem of Finite Abelian Groups ○ to the case where the group has order given by a prime power • Proof ○ Let P≔{x∈G│x^(p^m )=1}, T≔{x∈G│x^n=1} ○ By Lemma 56, G≅P×T ○ p∤|T| § Suppose, by way of contradiction, that ├ p┤ ||T|┤ § By Cauchy s Theorem, ∃z∈T s.t. |z|=p § Since z∈T, z^n=1, so ├ p┤ |n┤ § This is impossible, thus p∤|T| ○ |P|=p^m § Since |G|=|P|⋅|T|=p^m n, ├ p^m ┤ ||T|┤ § Suppose p^m |P| § Then, ∃ prime q s.t. p≠q and ├ q┤ ||P|┤ § By Cauchy s Theorem, ∃y∈P s.t. |y|=q § This is impossible since y∈P⇒y^(p^m )=1⇒├ q┤ |p^m ┤ § Thus p^m=|P|$

Math 521 – 4/6

$Theorem 3.27 (Cauchy Condensation Test) • Statement ○ Suppose a_1≥a_2≥…≥0, then ○ ∑_(n=1)^∞▒a_n converges⟺∑_(k=0)^∞▒〖2^k a_(2^k ) 〗=a_1+2a_2+4a_4+…converges • Proof ○ By Theorem 3.24, we just need to look at boundness of partial sums ○ Let § s_n=a_1+a_2+…+a_n, § t_k=a_1+2a_2+…+2^k a_(2^k ) ○ For n≤2^k § s_n≤a_1+(a_2+a_3 )+…+(a_(2^k )+…+a_(2^(k+1)−1) ) § ≤a_1+2a_2+…+2^k a_(2^k )=t^k ○ For n≥2^k § s_n≥a_1+(a_2+a_3 )+…+(a_(2^(k−1)+1)+…+a_(2^k ) ) § ≥1/2 a_1+a_2+…+2^(k−1) a_(2^k )=1/2 t^k ○ For n=2^k § s_n≤t_k≤2s_n⇒s_(2^k )≤t_k≤2s_(2^k ) § So {s_n } and {t_k } are both bounded or unbounded Theorem 3.28 • Statement ○ ∑_(n=1)^∞▒1/n^p converges if p 1 and diverges if p≤1 • Proof ○ If p≤0 § Theorem 3.23 says if∑_(n=1)^∞▒a_n converges, then lim_(n→∞)⁡〖a_n 〗=0 § In this case lim_(n→∞)⁡〖1/n^p 〗≠0, so series diverges ○ If p 0 § 1/n^p ≥1/(n+1)^p and 1/n^p ≥0 § By Cauchy Condensation Test, § lim_(n→∞)⁡〖1/n^p 〗 converges⟺∑_(n=1)^∞▒〖2^k 1/(2^k )^p 〗 converges § ∑_(n=1)^∞▒〖2^k 1/(2^k )^p 〗=∑_(n=1)^∞▒(2^(1−p) )^k which is a geometric series § By Theorem 3.26, this converges if 2^(1−p) 1⟺p 1 § Otherwise, 2^(1−p) 1, and this diverges Theorem 3.33 (Root Test) • Given ∑_(n=1)^∞▒a_n , put α=(lim⁡sup)_(n→∞)⁡√(n&|a_n | ), then • If α 1, ∑_(n=1)^∞▒a_n converges ○ Theorem 3.17(b) says if x s^∗,then ∃N∈N s.t.s_n x for n≥N ○ So let β∈(α,1) and N∈N s.t. ∀n≥N, √(n&|a_n | ) β i.e. |a_n | β^n ○ 0 β 1, so ∑_(n=1)^∞▒β^n converges ○ Thus, ∑_(n=1)^∞▒a_n converges by comparison test • If α 1, ∑_(n=1)^∞▒a_n diverges ○ By Theorem 3.17, there exists a sequence {n_k } s.t. √(n_k&|a_(n_k ) | )→α ○ So |a_n | 1 for infinitely many n, i.e. a_n↛0 ○ By Theorem 3.23, ∑_(n=1)^∞▒a_n diverges • If α=1, this test gives no information ○ For ∑_(n=1)^∞▒1/n, (lim⁡sup)_(n→∞)⁡√(n&n^(−1) )=lim_(n→∞)⁡√(n&n^(−1) )=1, but the series diverges ○ For ∑_(n=1)^∞▒1/n^2 , (lim⁡sup)_(n→∞)⁡√(n&n^(−2) )=lim_(n→∞)⁡〖1/(√(n&n))^2 〗=1, but the series converges Theorem 3.34 (Ratio Test) • Statement ○ ∑_(n=1)^∞▒a_n converges if (lim⁡sup)_(n→∞)⁡〖|a_(n+1)/a_n | 1〗 ○ ∑_(n=1)^∞▒a_n diverges if |a_(n+1)/a_n |≥1,∀n≥n_0 for some fixed n_0∈N • Proof ○ If (lim⁡sup)_(n→∞)⁡〖|a_(n+1)/a_n | 1〗 ○ We can find β 1, N∈N s.t. |a_(n+1)/a_n | β,∀n≥N ○ In particular § |a_(N+1) | β|a_N | § |a_(N+2) | β|a_(N+1) | β^2 |a_N | § ⋮ § |a_(N+p) | β^p |a_N | ○ So, |a_n | |a_N | β^(−N) β^n, ∀n≥N ○ β 1, so ∑_(n=1)^∞▒β^n converges ○ So ∑_(n=1)^∞▒〖⏟(|a_N | β^(−N) )┬constant β^n 〗 also converges ○ Therefore ∑_(n=1)^∞▒a_n converges by comparison test ○ On the other hand, if |a_(n+1) |≥|a_n |,∀n≥n_0∈N ○ Then a_n↛0, so series divreges by Theorem 3.23 • Note ○ For ∑_(n=1)^∞▒1/n, lim_(n→∞)⁡〖(1/n)/(1/(n+1) )〗=1 ○ For ∑_(n=1)^∞▒1/n^2 , lim_(n→∞)⁡〖(1/n^2)/(1/(n+1)^2 )〗=1 ○ So lim_(n→∞)⁡〖a_n/a_(n+1) 〗=1 is not enough to conclude anything$

Math 541 – 4/4

$Theorem 54: Cauchy s Theorem • Statement ○ If G is a finite group, and p is a prime divisor of |G|, then ∃H≤G of order p • Proof ○ Write |G|=mp. We argue by strong induction on m ○ When m=1, this is trivial, since any non-identity element of G has order p ○ Suppose m 1, and ∀n∈{1,…,m−1} if |G^′ |=np, then ∃H^′≤G^′ of order p ○ If G is abelian § Let x∈G∖{1} § If ⟨x⟩=G □ By the Fundamental Theorem of Cyclic Groups, □ G=⟨x⟩ contains a (unique) subgroup of order p § If ⟨x⟩≠G □ Set H≔⟨x⟩⊴G □ By the Lagrange s Theorem, |G|=|H|[G:H]=|H|⋅|G/H| □ Since ├ p┤ ||G|┤,either ├ p┤ ||H|┤ or ├ p┤ ||G/H|┤ □ If ├ p┤ ||H|┤ ® Since H is cyclic, H contains a (unique) subgroup of order p ® It follows that G contains a subgroup of order p □ If ├ p┤ ||G/H|┤ ® |G/H| |G|, so, by induction, ∃gH∈G\/H s.t. |gH|=p ® So we only need to prove ├ |gH|┤ ||g|┤ ◊ If K ⟶┴f K′ is a group homomorphism, ├ |f(k)|┤ ||k|┤,∀k∈K ◊ Now, take K=G, K^′=G\/H, f the usual surjection g↦gH ® Therefore ├ p┤ ||g|┤ ® Since ⟨g⟩ is cyclic, ⟨g⟩ contains a (unique) subgroup of order p ® It follows that G contains a subgroup of order p ○ If G is not abelian § By the Lagrange s Theorem, |G|=|C_G (g_i )|⋅[G:C_G (g_i )], ∀i∈{1,…,r} § Since ├ p┤ ||G|┤,either ├ p┤ ||C_G (g_i )|┤ or ├ p┤ |[G:C_G (g_i )]┤ § If ├ p┤ ||C_G (g_i )|┤ for some i □ Since G is not abelian, C_G (g_i )≨G for all i □ Apply the induction hypothesis, C_G (g_i ) contains a subgroup of order p □ It follows that G contains a subgroup of order p § If ├ p┤ |[G:C_G (g_i )]┤,∀i □ By the Class Equation, |G|=|Z(G)|+∑_(i=1)^r▒[G:C_G (g_i )] where g_1,…,g_r∈G □ are the representatives of the conjugate classes not contained in Z(G) □ It follows that ├ p┤ |(|G|−∑_(i=1)^r▒[G:C_G (g_i )] )┤=|Z(G)| □ G is not abelian, so Z(G)≨G □ Apply the induction hypothesis, Z(G) contains a subgroup of order p □ It follows that G contains a subgroup of order p Lemma 55: Recognizing Direct Products • Statement ○ Let G be a group with normal subgroups N_1,N_2 ○ The map α:N_1×N_2→G given by (n_1,n_2 )↦n_1 n_2 is an isomorphism ○ if and only if N_1 N_2=G and N_1∩N_2={1} • Proof (⟹) ○ Since α is surjective, N_1 N_2=G ○ Suppose n∈N_1∩N_2 ○ Then α(n,1)=n=α(1,n) ○ Since α is injective, (1,n)=(n,1)⇒n=1 ○ So N_1∩N_2={1} • Proof (⟸) ○ α is surjective § This is true since N_1 N_2=G ○ α is a homomorphism § α((n_1,n_2 ),(n_1^′,n_2^′ ))=α((n_1 n_1^′,n_2 n_2^′ ))=n_1 n_1^′ n_2 n_2^′ § α(n_1,n_2 )α(n_1^′,n_2^′ )=n_1 n_2 n_1^′ n_2^′ § We want show that α((n_1,n_2 ),(n_1^′,n_2^′ )) (α(n_1,n_2 )α(n_1^′,n_2^′ ))^(−1)=1 § (n_1 n_1^′ n_2 n_2^′ ) (n_1 n_2 n_1^′ n_2^′ )^(−1)=n_1 n_1^′ n_2 n_2^′ (n_2^′ )^(−1) (n_1^′ )^(−1) n_2^(−1) n_1^(−1) § =n_1 ⏟(n_1^′ n_2 (n_1^′ )^(−1) )┬(∈N_2 ) n_2^(−1) n_1^(−1)=n_1 ⏟(n_1^′ n_2 (n_1^′ )^(−1) n_2^(−1) )┬(∈N_2 ) n_1^(−1)∈N_2 § =n_1 n_1^′ ⏟(n_2 (n_1^′ )^(−1) n_2^(−1) )┬(∈N_1 ) n_1^(−1)=n_1 ⏟(n_1^′ n_2 (n_1^′ )^(−1) n_2^(−1) )┬(∈N_1 ) n_1^(−1)∈N_1 § Thus (n_1 n_1^′ n_2 n_2^′ ) (n_1 n_2 n_1^′ n_2^′ )^(−1)∈N_1∩N_2={1} § Therefore α((n_1,n_2 ),(n_1^′,n_2^′ ))=α((n_1,n_2 ),(n_1^′,n_2^′ )) ○ α is injective § If (n_1,n_2 )=1 § ⇒n_1 n_2=1 § ⇒n_1=n_2^(−1) § ⇒n_1∈N_2,n_2∈N_1 § ⇒n_1=n_2=1 § ⇒(n_1,n_2 )=(1,1) § ⇒α is injective$

Shawn Zhong

Shawn Zhong

6.5 Generalized Permutations and Combinations

6.4 Binomial Coefficients and Identities

Math 541 – 4/6

Math 521 – 4/6

Math 541 – 4/4

Search

WeChat Account