Onetone Blog

6.3 Permutations and Combinations

Permutations • Definition ○ A permutation of a set of distinct objects is an ordered arrangement of these objects. ○ An ordered arrangement of r elements of a set is called an r-permutation. • Example ○ Let S = {1,2,3}. ○ The ordered arrangement 3,1,2 is a permutation of S. ○ The ordered arrangement 3,2 is a 2-permutation of S. ○ The number of r-permutations of a set with n elements is denoted by P(n,r). ○ The 2-permutations of S = {1,2,3} are 1,2; 1,3; 2,1; 2,3; 3,1; and 3,2 ○ Hence, P(3,2) = 6. A Formula for the Number of Permutations • Theorem 1 ○ If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are ○ P(n,r)=n(n−1)(n−2)⋯(n−r+1) ○ r-permutations of a set with n distinct elements. • Proof ○ Use the product rule. ○ The first element can be chosen in n ways. ○ The second in n − 1 ways ○ And so on until there are (n−(r−1)) ways to choose the last element. ○ Note that P(n,0) = 1, since there is only one way to order zero elements. • Corollary 1 ○ If n and r are integers with 1 ≤ r ≤ n, then ○ P(n,r)=n!/(n−r)! • Example ○ How many ways are there to select a first-prize winner, a second prize winner, and a third-prize winner from 100 different people who have entered a contest? ○ P(100,3) = 100 ∙ 99 ∙ 98 = 970,200 Example ○ Suppose that a saleswoman has to visit eight different cities. ○ She must begin her trip in a specified city ○ But she can visit the other seven cities in any order she wishes. ○ How many possible orders can the saleswoman use when visiting these cities? ○ The first city is chosen, and the rest are ordered arbitrarily. ○ Hence the orders are: 7! = 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 5040 ○ If she wants to find the tour with the shortest path that visits all the cities, ○ she must consider 5040 paths! Example ○ How many permutations of the letters ABCDEFGH contain the string ABC ? ○ We solve this problem by counting the permutations of six objects, ABC, D, E, F, G, H. ○ 6! = 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 720 Combinations • Definition ○ An r-combination of elements of a set is an unordered selection of r elements from the set. ○ Thus, an r-combination is simply a subset of the set with r elements. ○ The number of r-combinations of a set with n distinct elements is denoted by C(n, r). ○ The notation (█(n@r)) is also used and is called a binomial coefficient. ○ (We will see the notation again in the binomial theorem in Section 6.4.) • Example: ○ Let S be the set {a, b, c, d}. ○ Then {a, c, d} is a 3-combination from S. ○ It is the same as {d, c, a} since the order listed does not matter. ○ C(4,2) = 6 because the 2-combinations of {a, b, c, d} are the six subsets ○ {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, and {c, d}. • Theorem 2 ○ The number of r-combinations of a set with n elements, where n≥r ≥ 0, equals ○ C(n,r)=n!/(n−r)!r! • Proof ○ By the product rule P(n, r)=C(n,r)⋅P(r,r). Therefore, ○ C(n,r)=P(n,r)/P(r,r) =(n!∕(n−r)!)/(r!∕(r−r)!)=n!/(n−r)!r! • Example ○ How many poker hands of five cards can be dealt from a standard deck of 52 cards? ○ Also, how many ways are there to select 47 cards from a deck of 52 cards? ○ Since the order in which the cards are dealt does not matter ○ the number of five card hands is: ○ C(52,5)=52!/5!47!=(52⋅51⋅50⋅49⋅48)/(5⋅4⋅3⋅2⋅1)=26⋅17⋅10⋅49⋅12=2,598,960 ○ The different ways to select 47 cards from 52 is ○ C(52,47)=52!/47!5!=C(52,5)=2,598,960 • Corollary 2 ○ Let n and r be nonnegative integers with r≤n. Then C(n, r) = C(n, n−r). • Proof ○ From Theorem 2, it follows that ○ C(n,n−r)=n!/(n−r)!(n−(n−r))!=n!/(n−r)!r!=C(n,r) ○ Hence, C(n, r)=C(n, n−r) Combinatorial Proofs • Definition ○ A combinatorial proof of an identity is a proof that uses one of the following methods. ○ Double Counting Proof § A double counting proof uses counting arguments to prove that § both sides of an identity count the same objects, but in different ways. ○ Bijective Proof § A bijective proof shows that there is a bijection § between the sets of objects counted by the two sides of the identity. • Example ○ Here are two combinatorial proofs that C(n, r)=C(n, n−r) ○ Bijective Proof § Suppose that S is a set with n elements. § The function that maps a subset A of S to A ̅ is a bijection between § the subsets of S with r elements and the subsets with n−r elements. § Since there is a bijection between the two sets § They must have the same number of elements. ○ Double Counting Proof § By definition the number of subsets of S with r elements is C(n, r). § Each subset A of S can also be described by § specifying which elements are not in A, i.e., those which are in A ̅. § Since the complement of a subset of S with r elements has n−r elements § There are also C(n,n−r) subsets of S with r elements. More Examples • How many words can you formed by rearranging the letters in the word: ○ Combine § 7! ○ Permutation § Pick where t s go § Arrange remaining 9 letters § (█(11@2))⋅9!=11!/2! ○ Rearrange § Pick where r s go § Pick where e s go § Pick where a s go § Arrange remaining 2 letters § (█(9@3))⋅(█(6@2))⋅(█(4@2))⋅2!=9!/3!2!2! • In a game of cards a hand consists of 13 cards. How many possible hands are there with ○ Exactly one ace § Pick which ace § Pick the rest § 4⋅(█(52−4@12)) ○ At least one ace § 1 Ace + 2 Aces + 3 Aces + 4 Aces § 4⋅(█(52−4@12))+(█(4@2))⋅(█(52−4@11))+(█(4@3))⋅(█(52−4@10))+(█(4@4))⋅(█(52−4@9)) ○ Exactly one ace and two diamonds § Case 1: We pick one diamond and a diamond ace □ 1⋅12⋅(█(52−4−12@11)) § Case 2: We pick two diamonds and a different ace □ 3⋅(█(12@2))⋅(█(52−4−12@10)) § So the total number of hands is 1⋅12⋅(█(52−4−12@11))+3⋅(█(12@2))⋅(█(52−4−12@10))

Math 541 – 4/2

$Conjugacy Class • Definition ○ If G is a group, G acts on itself by conjugation: g⋅h=ghg^(−1) ○ The orbits under this action are called conjugacy classes ○ Denote a conjugate class represented by some element g∈G by conj(g) • Example 1 ○ If g∈G, and g∈Z(G), then conj(g)={g} ○ Since hgh(−1)=hh(−1) g=g, ∀h∈G ○ The converse is also true: If conj(g)={g}, then g∈Z(G) • Example 2 ○ Let G=S_n ○ If σ∈S_n, then conj(g)={all permutations of the same cycle type as σ} ○ For instance § If σ is a t-cycle, then conj(σ)={all t-cycles} ○ More generally § Let σ=(a_1^((1) )…a_(t_1)^((1) ) )⋯(a_1^((m) )…a_(t_m)^((m) ) ) be a product of disjoint cycles § Then conj(σ)={all products of disjoint cycles of length t_1,…,t_m } Theorem 51: The Class Equation • Statement ○ Let G be a finite group ○ Let g_1,…g_r∈G be representatives of the conjugacy classes of G that ○ are not contained in the center Z(G) of G ○ Then |G|=|Z(G)|+∑_(i=1)^r▒[G:C_G (g_i )] • Recall: C_G (g_i )={g∈G│gg_i=g_i g} • Proof ○ G is the disjoint union of its disjoint conjugate classes ○ Then G=Z(G)∪⋃24_(i=1)^r▒conj(g_i ) ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒|conj(g_i )| ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒|orb(g_i )| (under conjugacy action) ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒[G:stab(g_i )] by Proposition 48 ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒[G:C_G (g_i )] Corollary 52 • Statement ○ If p is a prime, and P is a group of order p^α (α 1), then |Z(P)| 1 • Note: Group of order p^α is called a p-group • Proof ○ By the class equation, |Z(P)|=|P|−∑_(i=1)^r▒[P:C_P (p_i )] , where p_1,…p_r∈P ○ are representatives of the conjugate classes of P not contained in Z(P) ○ g_i∉Z(P)⇒C_P (g_i )≠P⇒[P:C_P (g_i )]≠1 ○ By Lagrange s Theorem, ├ [P:C_P (g_i )]┤ |p^α ┤ ○ Combing previous two results, ├ p┤|├ [P:C_P (g_i )]┤ ○ Thus, ├ p┤ |(|P|−∑_(i=1)^r▒[P:C_P (g_i )] )┤=|Z(P)|, since ├ p┤ ||P|┤ ○ ⇒|Z(P)|≠1 Corollary 53 • Statement ○ If p is a prime, and P is a group of order p^2, then P is abelian. ○ In fact, either P≅Z\/p^2 Z or P≅Z\/pZ×Z\/pZ • Proof ○ By corollary 52, |Z(P)|=p or p^2 ○ Suppose |Z(P)|=p § |P/Z(P)|=[P:Z(P)]=|P|/|Z(P)| =p^2/p=p § By Corollary 26, P\/Z(P) is cyclic § By HW6 Q2, P is abelian § In this case Z(P)=P⇒|Z(P)|=p^2, which is impossible ○ Suppose |Z(p)|=p^2 § We have |Z(p)|=|P|⇒Z(P)=P § So P is abelian ○ If P is cyclic, then clearly P≅Z\/p^2 Z ○ If P is not cyclic, we need to show P≅Z\/pZ×Z\/pZ § Let z∈P∖{1}, then |z|=p. Let y∈P∖⟨z⟩ § Set H≔⟨z⟩,K≔⟨y⟩, then H∩K={1} § Since any non-identity element of H or K is a generator § For instance, if 1≠y^k∈H for some k, then y∈H, which is impossible § |HK|=(|H|⋅|K|)/|H∩K| =|H|⋅|K|=p^2=|P|⇒HK=P § By HW6 Q1, there exists an isomorphism P ⟶┴≅ P\/H×P\/K § |P/H|=[P:H]=|P|/|H| =p^2/p=p⇒P\/H≅Z\/pZ § Similarly for P\/K § Therefore P=HK≅Z\/pZ×Z\/pZ$

Math 541 – 3/23

$Proposition 47 • Statement ○ Let G act on a set X ○ The relation x~x^′⟺∃g∈G s.t. gx=x′ is an equivalence relation • Proof ○ Reflexive § 1⋅x=x ○ Symmetric § Suppose x~x^′, then ∃g∈G s.t. gx=x^′⇒x=g^(−1) x^′ ○ Transitive § Suppose x~x^′ and x^′~x^′′ § Choose g,h∈G s.t. gx=x′ and hx^′=x′′ § Then ghx=hx^′=x^′′ • Note ○ The equivalence classes are the orbits of the group action ○ Thus, the orbits partition X Proposition 48 • Statement ○ If G acts on X, and x∈X, then |orb(x)|=[G:stab(x)] • Proof ○ Define a function § F:orb(x)→{left costs of stab(x)} § gx↦g stab(x) ○ F is injective § g stab(x)=g′ stab(x) § ⟺(g^′ )^(−1) g∈stab(x) § ⟺(g^′ )^(−1) gx=x § ⟺gx=g^′ x ○ F is surjective § This is clear ○ So orb(x)≅{left costs of stab(x)} ○ Therefore |orb(x)|=[G:stab(x)] Proposition 49: Lemma for Cayley s Theorem • Statement ○ Let G be a group acting on a finite set X={x_1,…,x_n } ○ Then each g∈G determines a permutation σ_g∈S_n by ○ σ_g (i)=j⟺g⋅x_i=x_j • Proof ○ The map f:X→X, given by x↦g⋅x is bijection ∀g∈G § Injectivity: g⋅x=g⋅x^′⇒(g^(−1) g)⋅x=(g^(−1) g)⋅x^′⇒x=x^′ § Surjectivity: f(g^(−1)⋅x)=(gg^(−1) )⋅x=x ○ So each g∈G determines a permutation σ_g∈S_n where § σ_g (i)=j⟺g⋅x_i=x_j • Statement ○ The map Φ:G→S_n,g↦σ_g is a homomorphism • Proof ○ Let g,h∈G,i∈{1,…,n} ○ Suppose σ_gh(i)=j for some j ○ Then (gh x_i=x_j ○ Write hx_i=x_k for some k, then σ_h(i)=k ○ (gh x_i=x_j⟺gx_k=x_j⟺σ_g (k)=j⟺σ_g (σ_h(i))=j ○ Therefore σ_gh(i)=σ_g σ_h(i),∀i∈{1,…,n} Theorem 50: Cayley s Theorem • Statement ○ Every finite group is isomorphic to a subgroup of the symmetric group • Proof ○ Let G={g_1,…,g_n } act on itself by left multiplication g⋅h=gh ○ By Proposition 49, this action determines a homomorphism § Φ:G→S_n § g↦σ_g § where σ_g (i)=j⟺g⋅g_i=g_j ○ Φ is injective § Φ(g)=Φ(h⟺σ_g=σ_ℎ⟺ggi=hgi,∀i⟺g=h ○ Thus G≅im(Φ)≤S_n • Example ○ Klein 4 group K={1,a,b,c} ○ where a^2=b^2=c^2=1⟺ab=c,bc=a,ac=b 1 a b c 1 1 a b c a a 1 c b b b c 1 a c c b a 1 ○ Label the group elements with 1, 2, 3, 4 ○ 1↦σ_1=(1) since § σ_1 (1)=1 § σ_2 (2)=2 § σ_3 (3)=3 § σ_4 (4)=5 ○ a↦σ_a=(1 2)(3 4) since § σ_a (1)=2 § σ_a (2)=1 § σ_a (3)=4 § σ_a (4)=3 ○ b↦σ_b=(1 3)(2 4) since § σ_b (1)=3 § σ_b (2)=4 § σ_b (3)=1 § σ_b (4)=2 ○ c↦σ_c=(1 4)(2 3) since § σ_c (1)=4 § σ_c (2)=3 § σ_c (3)=2 § σ_c (4)=1 ○ Therefore K≅{(1),(1 2)(3 4),(1 3)(2 4),(1 4)(2 3)}≤S_4$

Math 521 – 4/2

Theorem 3.20 • Lemma (The Squeeze Theorem) ○ Given 0≤x_n≤s_n, for n≥N where N∈N is some fixed number ○ If s_n→0, then x_n→0 ○ (Proof on homework) • If p 0, then (lim)_(n→∞)⁡〖1/n^p 〗=0 ○ For n≥N, we need |1/n^p −0| ε⇒n 1/ε^(1∕p) ○ Given ε 0 ○ Using Archimedean Property, take N (1/ε)^(1/p) ○ So, for n≥N, n (1/ε)^(1/p)⇒n^p 1/ε⇒1/n^p ε⇒|1/n^p −0| ε ○ Therefore lim_(n→∞)⁡〖1/n^p 〗=0 • If p 0, then (lim)_(n→∞)⁡√(n&p)=1 ○ When p=1 § We are done, since lim_(n→∞)⁡1=1 ○ When p 1 § Then p−1 0 § Let x_n=√(n&p)−1, then x_n 0 § p=(x_n+1)^n≥1^n+(█(n@n−1)) 1^(n−1) x_n^1=1+nx_n § ⇒p−1≥nx_n § ⇒(p−1)/n≥x_n 0 § By the Squeeze Theorem, x_n→0 § i.e.lim_(n→∞)⁡〖√(n&p)−1〗=0 § So lim_(n→∞)⁡√(n&p)=1 ○ When p 1 § Then 1/p 1 § So, lim_(n→∞)⁡√(n&1∕p)=1 § Therefore lim_(n→∞)⁡√(n&p)=1/1=1 • (lim)_(n→∞)⁡√(n&n)=1 ○ Let x_n=√(n&n)−1≥0 ○ n=(x_n+1)^n≥(█(n@n−2)) 1^(n−2) x_n^2=n!/(n−2)!2! x_n^2=n(n−1)/2 x_n^2 ○ ⇒2/(n−1)≥x_n^2 ○ ⇒√(2/(n−1))≥x_n 0 for n 1 ○ By the Squeeze Theorem, x_n=lim_(n→∞)⁡〖√(n&n)−1〗→0 ○ i.e. lim_(n→∞)⁡√(n&n)=1 • If p 0,α∈R, then (lim)_(n→∞)⁡〖n^α/(1+p)^n 〗=0 ○ Let k∈N s.t. k α by Archimedean Property ○ For n 2k,(1+p)^n (█(n@k)) p^k=(n(n−1)⋯(n−k+1))/k! p^k (n^k p^k)/(2^k k!) ○ Because n 2k⇒n/2 k⇒n−k n/2⇒n−k+1 n/2 ○ So, 0 n^α/(1+p)^α (2^k k!)/(n^k p^k )⋅n^α=(2^k k!)/p^k ⋅n^(α−k) ○ Since a−k 0, n^(a−k)→0⇒(2^k k!)/p^k ⋅n^(α−k)→0 ○ By the Squeeze Theorem, n^α/(1+p)^α →0 ○ i.e. lim_(n→∞)⁡〖n^α/(1+p)^n 〗=0 • If |x| 1, then (lim)_(n→∞)⁡〖x^n 〗=0 ○ |x| 1⇒1/|x| 1 ○ Let p=1/|x| −1 0 ○ Take α=0 in the limit above, we get lim_(n→∞)⁡〖1/(1+p)^n 〗=0 ○ So lim_(n→∞)⁡〖1/((1+1/|x| −1)^n )〗=lim_(n→∞)⁡〖|x|^n 〗=0 ○ Then lim_(n→∞)⁡〖x^n 〗=0

Math 521 – 3/23

$Sequences Approaching Infinity • Let {s_n } be a sequence of real numbers s.t. • ∀M∈R,∃N∈N s.t. s_n≥M,∀n≥N • Then we write s_n→+∞ • Similarly if ∀M∈R,∃N∈N s.t. s_n≤M,∀n≥N • Then we write s_n→−∞ Upper and Lower Limits • Definition ○ Let {s_n } be a sequence of real numbers ○ Let E be the set of x (in the extended real number system) s.t. ○ s_(n_k )→x for some subsequence {s_(n_k ) } ○ E contains all subsequential limits of {s_n } plus possibly +∞,−∞ ○ (lim⁡sup)_(n→∞)⁡〖s_n 〗=s^∗=sup⁡E is called the upper limit of {s_n } ○ (lim⁡inf)_(n→∞)⁡〖s_n 〗=s_∗=inf⁡E is called the lower limit of {s_n } • Example 1 ○ s_n=(−1)^n/(1+1/n)={−1/2,2/3,−3/4,4/5,−5/6,…} ○ (lim⁡sup)_(n→∞)⁡〖s_n 〗=sup⁡{−1,1}=1 ○ (lim⁡inf)_(n→∞)⁡〖s_n 〗=inf⁡{−1,1}=−1 • Example 2 ○ lim_(n→∞)⁡〖s_n 〗=s⇒(lim⁡sup)_(n→∞)⁡〖s_n 〗=(lim⁡inf)_(n→∞)⁡〖s_n 〗=s § All subsequential limits of a convergent sequence § converge to the same value as the sequence ○ (lim⁡sup)_(n→∞)⁡〖s_n 〗=(lim⁡inf)_(n→∞)⁡〖s_n 〗=s⇒lim_(n→∞)⁡〖s_n 〗=s § ⇒sup⁡E=inf⁡E § ⇒E={s} § ⇒ All subsequential limits = s § ⇒lim_(n→∞)⁡〖s_n 〗=s Theorem 3.17 • Let {s_n } be a sequence of real numbers, then • s^∗∈E ○ When s^∗=+∞ § E is not bounded above, so {s_n } is not bounded above § There is a subseqnence {〖s_n〗_k } s.t. 〖s_n〗_k→∞ § So s^∗=+∞∈E ○ When s^∗∈R § E is bounded above § And at least one subsequential limit exists i.e. E≠∅ § By Theorem 3.7, E is closed i.e. E=E ̅ § By Theorem 2.28, s^∗=sup⁡E∈E ̅ § Therefore s^∗∈E ○ When s^∗=−∞ § Then E={−∞} § s_n→−∞ and s^∗=−∞∈E • If x s^∗,then ∃N∈N s.t.s_n x for n≥N ○ If ∃x s^∗ with s_n≥x for infinitely many n∈N ○ Then ∃y∈E s.t. y≥x s^∗ ○ This contradicts the definition of s^∗ • Moreover s^∗ is the only number with these properties ○ Suppose p,q∈E,p≠q s.t. the property above holds for p,q ○ Without loss of generality, suppose p q ○ Choose x s.t. p x q ○ Since p satisfies the property above ○ ∃N∈N s.t. s_n x,∀n≥N ○ So no subsequence of {s_n } can converge to q ○ This contradicts the existence of q ○ Therefore only one number can have these properties$

Shawn Zhong

Shawn Zhong

6.3 Permutations and Combinations

Math 541 – 4/2

Math 541 – 3/23

Math 521 – 4/2

Math 521 – 3/23

Search

WeChat Account