2022/05/27
Algebraic system
Groups and Burnside’s TNU CSIE Discrete Math 1
Copyright By PowCoder代写 加微信 powcoder
2022/05/27
– Let S and T be two sets. The function f: S×S→T is called a binary operation on S.
– If T ⊆ S, then the binary operation f is said to be closed.
– A set together with a number operations is called an algebraic system.
NTNU CSIE Discrete Math 2
2022/05/27
Let (S, ⋆ ) be an algebraic system. We say that
– e is a left identity if for every element s the equality e ⋆ s = s holds.
– e is a right identity if for every element s the equality s ⋆ e = s holds.
NTNU CSIE Discrete Math 3
2022/05/27
Proposition. Let (S, ⋆ ) be an algebraic system. If e1 is a left identity and e2 is a right identity, then e1 = e2.
Remark. If e is both a left identity and a right identity, then we call e an identity of the algebraic system.
Remark. The identity of an algebraic system (S, ⋆ ) is unique if it exists.
NTNU CSIE Discrete Math 4
2022/05/27
Question: Can you define an algebraic system that has only left identity(s)?
NTNU CSIE Discrete Math 5
2022/05/27
Let (S, ⋆ ) be an algebraic system with an identity, say e. – For s, t ∈ S, t is a left inverse of s if t ⋆ s = e.
– For s, t ∈ S, t is a right inverse of s if s ⋆ t = e.
NTNU CSIE Discrete Math 6
2022/05/27
Let (S, ⋆ ) be an algebraic system, where ⋆ is a binary operation on S. (S, ⋆ ) is called a group if the following conditions are satisfied:
– ⋆ is a closed operation.
– ⋆ is an associative operation.
– There exists a (unique) identity e.
– For every element s, there exists a left inverse of s.
NTNU CSIE Discrete Math 7
2022/05/27
Proposition. Let (S, ⋆ ) be a group. For s ∈ S, a left inverse of s is also a right inverse of s.
– Let t be a left inverse of s, and let u be a left inverse of t. – Then s ⋆ t = (u ⋆ t) ⋆ (s ⋆ t) = u ⋆ (t ⋆ s) ⋆ t = u ⋆ t = e.
NTNU CSIE Discrete Math 8
2022/05/27
Proposition. Let (S, ⋆ ) be a group. The inverse of every element is unique. Proof:
– Let s1 and s2 be the inverses of s, and let e be the identity.
– s1 =s1⋆e=s1⋆(s⋆s2)=(s1⋆s)⋆s2 =e⋆s2 =s2. ∎
NTNU CSIE Discrete Math 9
2022/05/27
Consider the set of all permutations 𝒫 of a finite set A = {a1, …, an}. – We view a permutation π as a bijection from A to A, denoted by
( a1,a2,…,an ). π(a1), π(a2), …, π(an)
– Let ∘ be a binary operation on A, defined as the composition of two functions.
– (𝒫, ∘ ) is a group, which is called the symmetric group of A. – Any subgraph of (𝒫, ∘ ) is called a permutation group of A.
NTNU CSIE Discrete Math 10
2022/05/27
Let (G, ∘ ) be a permutation group of a finite set A.
– The binary relation induced by (G, ∘ ) is a binary relation R on A such that
(a,b)∈Riff ∃π∈G π(a)=b.
– R is an equivalence relation.
– reflexive?
– symmetric? – transitive?
NTNU CSIE Discrete Math 11
2022/05/27
– Let A = {a,b,c,d}, π1 = (abcd),π2 = (abcd),π3 = (abcd),π4 = (abcd).
abcd bacd abdc badc
– ({π1, π2, π3, π4}, ∘ ) is a permutation group, which induces the partition {{a, b}, {c, d}}.
NTNU CSIE Discrete Math 12
2022/05/27
Question: What is the number of ways to decompose 9 into a nondecreasing sequence of three positive integers a1, a2, and a3?
– Namely, a1 + a2 + a3 = 9 and a1 ≤ a2 ≤ a3.
NTNU CSIE Discrete Math 13
2022/05/27
Theorem [ , Burnside 1897; Frobenius 1887; Cauchy 1845]. The number of equivalence classes into which a set A is divided by the equivalence relation induced by a permutation group (G, ∘ ) of A is given by
where ψ(π) is the number of elements that are invariant under the permutation π.
∑ψ(π), π∈G
NTNU CSIE Discrete Math 14
2022/05/27
– Let η(a) be the number of permutations in G that maps a to a.
-Then ∑ψ(π)=∑η(a). π∈G a∈A
– Let b be an element that belongs to the equivalence class containing a.
– The number of permutations that maps a to b is equal to η(a).
– Let {π1, π2, …, πk} be the set of all permutations that maps a to a. – There exists πx such that πx(a) = b.
– Then for i ∈ [k] (πx ∘ πi)(a) = b.
-Fori≠j,πx∘πi≠πx∘πj sinceotherwise
π =(π−1∘π)∘π =π−1∘(π ∘π)=π−1∘(π ∘π)=(π−1∘π)∘π =π. ixxixxixxjxxjj
NTNU CSIE Discrete Math 15
2022/05/27
– (so the number of permutations that maps a to b is at least η(a).) – Every permutation π that maps a to b is a member of
{πx ∘π1,πx ∘π2,…,πx ∘πk}
since π−1 ∘ π maps a to a, which is a member of {π , π , …, π }.
– Thus, we may partition G according to the image of a, and it follows that
(#elements that are related to a) ⋅ η(a) = | G | .
– Therefore, ∑ η(a) = (#equivalence classes) ⋅ | G | ∎ a∈A
NTNU CSIE Discrete Math 16
2022/05/27
Consider the set of strings of length 2 that are made up of blue beads and yellow beads.
– Two strings are indistinguishable if interchanging the ends of one will yield the other.
– How many distinct strings are there?
NTNU CSIE Discrete Math 17
2022/05/27
Consider the set of bracelets of five beads made up of yellow, blue, and white beads.
– Two bracelets are indistinguishable if the rotation of one will yield another.
– How many distinct bracelets are there?
NTNU CSIE Discrete Math 18
2022/05/27
– There are 35 distinct bracelets if rotational equivalence is not considered. – Let πi, for i ∈ {0,1,2,3,4}, be the permutation that maps a bracelet into one
which is the former rotated clockwise by i bead positions. – ({π0, π1, π2, π3, π4}, ∘ ) is a permutation group.
– ψ(π0) = 35,ψ(π1) = ψ(π2) = ψ(π3) = ψ(π4) = 3.
– By Burnside’s Lemma, there are 15(243 + 3 + 3 + 3 + 3) = 51 distinct bracelets.
NTNU CSIE Discrete Math 19
2022/05/27
Consider the set of bracelets of p beads made up of beads of a distinct colors.
– The number of distinct bracelets are
p1 ( a p + a + a + … + a ) = p1 ( a p + ( p − 1 ) a ) .
– The number is an integer so p divides ap − a.
– If gcd(a, p) = 1, then p ∣ ap−1 − 1. (Fermat’s little theorem)
NTNU CSIE Discrete Math 20
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com