April 9, 2018 - Shawn Zhong

Math 541 – 4/9

$Lemma 58 • Statement ○ If G is an abelian group of order p^n, where p is a prime ○ Let a∈G has maximal order among all the elements of G ○ Then G≅A×Q, where A=⟨a⟩, Q≤G • Proof ○ We argue by induction on n ○ If n=1, then G=A, so we may take Q={1} ○ Now suppose n 1 ○ Case 1: ∃b∈G s.t. b∉A and b^p=1 § Let B≔⟨b⟩⊴G § A∩B={1} □ |b| is prime, since b^p=1 □ Recall: If (x,n)=1, then Z\/nZ=⟨x ̅ ⟩ □ So every non-identity element of B is a generator □ Thus, if x∈A∩B, and x≠1, then B=⟨x⟩⊂A∩B⊂A □ Then b∈A, which contradicts the assumption □ Therefore A∩B={1} § Let G ̅≔G\/B, then |G ̅ | |G| since B≠{1} § aB is an element of maximal order in G ̅ □ ├ |aB|┤ ||a|┤ ® a^|a| =1 ® ⇒a^|a| ∈B ® ⇒(aB)^|a| =1_G ̅ ® ⇒├ |aB|┤ ||a|┤ □ ├ |a|┤ ||aB|┤ ® (aB)^|aB| =1_G ̅ ® ⇒a^|aB| B=B ® ⇒a^|aB| ∈B ® ⇒a^|aB| ∈A∩B={1} ® ⇒a^|aB| =1 ® ⇒├ |a|┤ ||aB|┤ □ So |aB|=|a| □ Therefore aB is an element of maximal order in G ̅ § By induction, ∃Q ̅≤G ̅ s.t. G ̅≅⟨aB⟩×Q ̅ § Apply the Correspondence Theorem, choose Q≤G s.t. Q ̅=Q\/B § Claim: G≅A×Q □ By Lemma 55, we need only show A∩Q={1} and AQ=G □ A∩Q={1} ® Let g∈A∩Q, then g=a^i for some i ® Thus, a^i B∈⟨aB⟩∩Q ̅≤G ̅ ® Since G ̅≅⟨aB⟩×Q ̅, ⟨aB⟩∩Q ̅={1} ® Therefore a^i B=1_G ̅ ® ⇒├ |a|=|aB|┤ |i┤ ® ⇒a^i=1 ® ⇒A∩Q={1} □ AQ=G ® Let g∈G ® Since G ̅=⟨aB⟩×Q ̅, ® gB=a^i ByB for some a^i B∈⟨aB⟩ and yB∈Q ̅, ® Thus gB=a^i yB⟺g(a^i y)^(−1)∈B ® Choose b∈B s.t. ga^(−i) y^(−1)=b ® Then g=⏟(a^i )┬(∈A) ⏟yb┬(∈Q) ® Therefore AQ=G ○ Case 2: ∄b∈G s.t. b∉A and |b|=p § In this case, we need to prove G=A § By way of contradiction, suppose otherwise § Choose x∈G∖A with the smallest order § Recall: If H=⟨z⟩,then |⟨z^m ⟩|=|z|/((|z|,m) ) § |x^p | |x|, so x^p∈A § Choose i s.t. x^p=a^i § Say |a|=p^s § Since a has maximal order, x^(p^s )=1 § ⇒1=x^(p^s )=(x^p )^(p^(s−1) )=(a^i )^(p^(s−1) )=a^(ip^(s−1) ) § It follows that ├ p┤ |i┤ § So x^p=a^i, where ├ p┤ |i┤ § Set y≔a^(−i\/p) x, then y^p=a^(−i) x^p=1 § But y∉A, since ya^(i\/p)=x∉A § This contradicts the assumption that ∄b∈G s.t. b∉A and |b|=p § So G∖A=∅ § Therefore G=A=⟨a⟩, and Q={1} Theorem 59: Fundamental Theorem of Finite Abelian Groups • Statement ○ Every finite abelian group G is a product of cyclic groups • Proof ○ Say |G|=p_1^(m_1 )⋯p_n^(m_n ), where p_i are distinct primes ○ By Corollary 57, and induction G≅P_1×…×P_n where ○ P_i={x∈G│x^(p_i^(m_i ) )=1} and |P_i |=p_i^(m_i ) ○ So, it suffices to show each P_i is a product of cyclic groups ○ By Lemma 58, P_i≅A_i×Q_i, where A_i is cyclic ○ The result immediately follows by induction on m_i • Example ○ How may abelian groups of order 8 are there up to isomorphism ○ There are 3 abelian groups of order 8: Z8ℤ, Z2ℤ×Z4ℤ, Z2ℤ×Z2ℤ×Z2ℤ Corollary 60 • Partition ○ A partition of n∈Z( 0) is a way of writing n as a sum of positive integers ○ Example: 3 has 3 partitions: 3, 2+1, 1+1+1 • Statement ○ If n=p_1^(e_1 )⋯p_n^(e_m ), where p_i are distinct primes ○ Then the number of finite abelian groups of order n is ○ ∏_(i=1)^m▒〖number of partitions of e_i 〗 • Note ○ If (λ^1,…,λ^m ) are partitions of e_1,…,e_m, where λ_i={λ_i^1,…,λ_i^(s_i ) } ○ Then this list of partitions corresponds to the abelian group ○ (Z(p_1^(λ_1^1 ) Z×…×Z(p_1^(λ_1^(s_1 ) ) Z)×…×(Z(p_1^(λ_m^1 ) Z×…×Z(p_1^(λ_m^(s_m ) ) Z) • Example ○ When n=72=2^3⋅3^2 ○ Z2ℤ×Z2ℤ×Z2ℤ×Z3ℤ×Z3ℤ≅Z2ℤ×Z6ℤ×Z6ℤ ○ Z2ℤ×Z2ℤ×Z2ℤ×Z9ℤ ○ Z4ℤ×Z2ℤ×Z3ℤ×Z3ℤ ○ Z4ℤ×Z2ℤ×Z9ℤ ○ Z8ℤ×Z3ℤ×Z3ℤ ○ Z8ℤ×Z9ℤ$

Math 521 – 4/9

$Power Series • Given a sequence {c_n } of complex numbers • The series ∑_(n=1)^∞▒〖c_n z^n 〗 is a power series Theorem 3.39 (Convergence of Power Series) • Statement ○ Given the power sires ∑_(n=1)^∞▒〖c_n z^n 〗 ○ Put α≔(lim⁡sup)_(n→∞)⁡√(n&|c_n | ) ○ Let R≔1/α (If α=+∞,R=0; If α=0,R=+∞) ○ Then ∑_(n=1)^∞▒〖c_n z^n 〗 converges if |z| R and diverges if |z| R • Proof ○ Let a_n=c_n z^n and apply the root test ○ (lim⁡sup)_(n→∞)⁡√(n&|a_n | )=|z| (lim⁡sup)_(n→∞)⁡√(n&|c_n | )=|z|/R • Note: R is called the radius of convergence of the power series • Examples ○ ∑_(n=1)^∞▒〖n^n z^n 〗 has R=0 ○ ∑_(n=0)^∞▒z^n/n! has R=+∞ ○ ∑_(n=0)^∞▒z^n has R=1. If |z|=1, then the series diverges ○ ∑_(n=1)^∞▒z^n/n has R=1,diverges if z=1, converges for all other z with |z|=1 ○ ∑_(n=1)^∞▒z^n/n^z has R=1, but converges for all z with |z|=1 by comparison Theorem 3.43 (Alternating Series Test) • Statement ○ Suppose we have a real sequence {c_n } s.t. ○ |c_1 |≥|c_2 |≥|c_3 |≥… ○ c_(2m−1)≥0, c_2m≤0, ∀m∈N ○ lim_(n→∞)⁡〖c_n 〗=0 ○ Then ∑_(n=1)^∞▒c_n converges • Proof: HW • Example: alternating harmonic series ○ ∑_(n=1)^∞▒(−1)^(n+1)/n=1−1/2+1/3−1/4+1/5⋯converges to ln⁡2 Absolute Convergence • The series Σa_n is said to converge absolutely if the series Σ|a_n | converges • If Σa_n converges but Σ|a_n | diverges • We way that Σa_n converges nonabsolutely or conditionally Theorem 3.45 (Property of Absolute Convergence) • Statement ○ If Σa_n converges absolutely, then Σa_n converges • Proof ○ |∑_(k=1)^∞▒a_k |≤∑_(n=k)^∞▒|a_k | ○ The result follows by Cauchy Criterion Rearrangement • Let {k_n } be a sequence in which every natural number appears exactly once • Let a_n^′=a_(k_n ), then Σa_n^′ is called a rearrangement of Σa_n Theorem 3.54 (Riemann Series Theorem) • Let Σa_n be a series of real number which converges nonabsolutely • Let −∞≤α≤β≤+∞ • Then there exists a rearrangement Σa_n^′ s.t. • (lim⁡inf)_(n→∞)⁡〖s_n^′ 〗=α, (lim⁡sup)_(n→∞)⁡〖s_n^′ 〗=β Theorem 3.55 • If Σa_n is a series of complex numbers which converges absolutely • Then every rearrangement of Σa_n converges to the same sum$

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.$

Shawn Zhong

Shawn Zhong

Math 541 – 4/9

Math 521 – 4/9

6.5 Generalized Permutations and Combinations

6.4 Binomial Coefficients and Identities

Search

WeChat Account