Sem 2 Liebeck Flashcards
1
Q
multiplication principle
A
multiplying number of options in each category to get total number of combinations
eg: 3 stages of choosing one of 26 letters and 3 stages of choosing one of ten letters
26x26x26x10x10x10=17576000 combinations
2
Q
orderings
A
s is a set containing n elements
number of different orderings of elements of s is n!
3
Q
two questions to ask when taking selections
A
- does order matter?
- are repetitions allowed?
4
Q
ordered selection allowing repetitions
A
n^r
5
Q
ordered selections not allowing repetitions
A
n!/(n-r)!
6
Q
binomial coefficients
A
n!/r!(n-r)!
7
Q
(a+b)^n=
A
Σn/r=0 (n choose r)a^n-rb^r
8
Q
binomial coefficient identities
A
n choose 0 = n+r choose o
n choose r = n choose (n-r)
n+1 choose r = (n choose r)(n choose r-1)
9
Q
set partitions
A
a collection of subsets such that each element of S lies in one of the subsets
10
Q
multinomial coefficients
A
total number of ordered partitions of S into subsets of sizes r1,…,rk
(n choose r1,…rk) = n!/r1!r2!…rk!
eg: 6 friends splitting into two teams of 3 = 6!/3!3!=20
11
Q
unordered selections, no repetition
A
n choose r
12
Q
unordered selections, repetition allowed
A
n+r-1 choose r
=n+r-1 choose n-1
13
Q
union
A
AUB
A and B subsets of universal set
either in A,B or both
(fully shaded venn diagram)
14
Q
intersection
A
AnB
the set of elements in both A and B
(overlap in venn diagram)
15
Q
disjoint
A
intersection is the empty set
16
Q
distributivity law
A
An(BUC)=(AnB)U(AnC)
AU(BnC)=(AUB)n(AUC)
17
Q
difference
A
A-B
denotedA\B
in A but not in B
(take away full circle from venn diagram so crescent moon shape left)
18
Q
complement
A
complement of A in S is S-A
set of all elements of S that are not in A
i.e. what’s been taken away
19
Q
cartesian product of A and B
A
set AxB = {(a,b)|a e A and b e B}
20
Q
R^3
A
RXRXR
consists of all triples of real numbers
21
Q
finite set
A
finite number of elements
22
Q
cardinality
A
|s|=n
s has n elements
n is the cardinality of s
23
Q
inclusion-exclusion principle
A
A and B finite subsets
|AUB|=|A|+|B|-|AnB|
picture visually to remember. i.e. full venn diagram is one circle plus another take away the overlap
24
Q
in general |A1U…UAn|=
A
c1-c2+c3-…+(-1)^n-1Cn
25
Euler-φ-function
counts positive integers up to n that are coprime to m
eg: φ(12)=4=|{1,5,7,11}|
26
euler function in terms of prime factors
φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)
27
powerset of s
set of subsets of s
28
cardinality of the powerset
|P(s)|=2^|s|
if s has n elements then P(s) has 2^n elements
29
unions and intersections in the powerset
the powerset is closed under taking unions and intersections
30
reflexive
for all s in S, (s,s) are in R
i.e. for all s in S we have s∼s
31
symmetric
s,t in S then (s.t) in R implies (t,s) in R.
i.e. s∼t if and only if t∼s
32
transitive
s,t,u in S then (s,t) in R and (t,u) in R implies that (s,u) in R
i.e. s∼t and t∼u implies s∼u
33
equivalence relation
needs to be reflexive, symmetric and transitive
34
equivalence classes cl(s)
{t in s|(s,t) in R}
equivalence classes of R are subsets cl(s) for s in S
in equivalence class of 1 if a number before 1 in bracket. i.e. (3,1) 3 is related to 1
35
if cl(s) and cl(t) are not disjoint...
they are equal
36
equivalence classes with respect to ∼ form...
a partition of s
37
poset
partially ordered set
a set with relation R that is reflexive, transitive and antisymmetric
38
antisymmetric
if A is a subset of B and B is a subset of A then A=B
39
examples of posets
P(s) with relation subset
R with relation less than or equal to
40
codomain
what may possibly come out
41
image/range
what actually comes out
42
onto/surjective
for every t in T, there exists an s in S with f(s)=t
everyone chosen but multiple people can pick same person
SURjective=SURplus
43
one-to-one/injective
distinct elements of S to distinct elements of T
INjective=INdividual
everyone gets to pick but nobody picks one person
44
bijective
both injective and surjective
i.e. perfect pairing, everyone has a partner, nobody left out
45
for S and T finite sets, if F is surjective
|S|≥|T|
46
for S and T finite sets, if F is injective
|S|≤ |T|
47
for S and T finite sets, if F is bijective
|S|=|T|
48
Let S and T be finite sets
|S|≥|T|≥0
There is...
a surjection f that maps S to T
49
pigeonhole principle
if we put n+1 pigeons into n pigeonholes, at least one pigeonhole must contain more than one pigeon
more generally: if we put mn+1 objects into n boxes, at least one box must contain more than m objects
50
compositions of functions
if f maps s to t, g maps t to u, then g(f(x)) maps s to u
51
if f ang g are both injective
gf is injective
52
if f and g are both surjective
gf is surjective
53
if f and g are both bijective
gf is bijective
54
if gf is injective
f injective
55
if gf surjective
g surjective
56
inverse function
f maps s to t, a bijection
for f^-1, maps t to s such that f^-1(f(x))=f(f^-1(x))=identity
57
counting functions
|s|=m
|T|=n
number of functions that map s to t = n^m
58
if |S|=m and less than |T|=n, the number of injective functions s to t is
n(n-1)...(n-m+1)
59
permutation of s
a bijection that maps s to s
60
if f and g are permutations of s then
so is the composition of f and g
"product" fg
set of permutations closed under composition
61
set of permutation of a set {1,...,n} denoted
Sn
62
i or id
identity permutation
63
number of permutations of {1,...,n} is
n!
i.e. |Sn|=n!
64
computing products
for gf, put g under f and take out middle row
for fg, f under g
65
inverse permutation
there exists a permutation f^-1 of s such that f^-1f=i=ff^-1
66
cycle notation
eg: (12)(345)(6)
67
length of cycle
k "k-cycle"
68
collection of cycles are disjoint if
no two share an element
69
a k cycle can be written
in k ways
(each starting with a different element)
70
a k cycle is a product of
k-1 cycles of length 2
71
multiplying permutations
**order matters** fg does not equal gf
for disjoint cycles, product is the same both ways
72
for a k cycle, f^k=
identity
73
for a k cycle, f^-1=
(i1,ik,ik-1,..i2)
74
every f in Sn can be expressed as
a product of disjoint cycles
75
cycle shape
eg: (1)(2)(3)(4)(5)
cycle shape is (1,1,1,1,1)=(1^5)
76
order of f
least integer greater than xero such that f^r=identity
77
order in cycle notation
lcm of lengths of cycles
78
sgn(f)
even permutation
1
79
sgn(f)
odd permutation
-1
80
properties of the signature
sgn of identity is even
sgn(gf)=sgn(g)sgn(f)
sgn(g)=sgn(g^-1)
sgn of any 2-cycle is -1
81
sgn of any r-cycle in Sn is
(-1)^r-1
82
for cycle shape (r1,...,rk)
sgn(f)=
(-1)^r1-1(-1)^r2-1...(-1)^rk-1
83
closure
closed under * if for any a,b in G, a*b in G
eg: multiplication is not closed on the set of -ve integers (-1x-2=2 is +ve)
84
Associativity
for all s,t,u in S we have (s * t) * u=s * (t * u)
if (S, *) associative and T is a subset of S. If T is closed under *, then (T, *) is associative.
85
identity
identity element for * on S if for all s in S
e * s = s * e = s
identity element is unique
86
inverses
(s, *) has inverses if, for every s in S there exists an s^-1 in S with
s * s^-1 = e = s^-1 * s
each element has a unique inverse
87
a group (G, *)
a set with binary operation * such that closure, associativity, identity and inverses hold
88
axioms of groups
closure
associativity
identity
inverse
89
(G, *) is abelian if
a * b = b * a
90
group table
entry in row of g and column of h is g * h
rows and columns have no repeats
row has |G| entries so each element of G appears
(think sudoku)
91
checking axioms in group tables - closure
is every entry in the table in S
92
checking axioms in group tables - identity
row of e is same order as header
93
checking axioms in group tables - inverses
does e appear in every row and every column
94
sub group in group table
A subset H is a subgroup if H is a group under operation *
95
conditions for subgroup
the identity element needs to be in H
if x,y in H then x * y in H
if x is in H, x^-1 in H
96
two easiest subgroups
itself and {e}
97
subgroup of (C, x)
roots of unity
98
powers of an element
form a subgroup
100
order of an element
smallest possible integer K such that a^k=w
o(a)
101
if there isn't a k such that a^k=e,
a has infinite order
103
a in G such that o(a) finite, a^n=e if and only if
o(a)|n
104
let P be prime, and denote Z*p=Zp - {0},
(Z*p,x) is a group
it is abelian and has size p-1
105
Lagrange's theorem
let G be a finite group, H a subset of G
|H| is a divisor of |G|
G a finite group, a in G.
o(a) is finite and a divisor of |G|
106
Fif G a finite group
a^|G|=e
107
what follows from Lagrange's theorem?
Fermat's little theorem
108
if |G| is prime,
G is cyclic
109
a bar in Zm. A solution x bar in Zm for ax bar = 1 bar exists if and only if
hcf(a,m)=1
eg: In Z6, only 1 bar and 5 bar have multiplicative inverses
110
(U(Zm),x)
a group
its is abelian and has φ(m) elements
111
proving lagrange's theorem
sort elements of G into piles of size |H|
for x in G, |Hx|=|H| so all cosets have same size
x in Hx, so each element of G is in a coset
for x,y in G Hx=Hy or intersection is empty set so distinct cosets are disjoint
right cosets of H in G form a partition of G
112
cosets
G group, H subgroup, g in G
set Hg={hg|h in H} is right coset of H
113
partition of G into right cosets of H corresponds to equivalence relation
x∼y if and only if xy^-1 in H
114
left cosets
work exactly the same
gH={gh|h in H}
115
normal subgroups
subgroups where the partition of G into left cosets is the same as the partition of G into right cosets
116
Mersenne prime
if 2^n -21 is prime, n is prime
set N=2^p -1
if q is a divisor of N, then p|q-1
117
perfect number
if the sum of all positive divisors of N in 2n
eg: 6=1+2+3
118
let 2^p -1 be prime. Then 2^(p-1)(2^p - 1) is
perfect
119
if N is an even perfect number then
N=2^(p-1)(2^p -1)
where 2^p-1 is a (mersenne) prime
120
let P be a prime. The period length of the decimal expansion of rational 1/p is
a divisor of p-1
eg: p=3
1/3=0.3
period length=1 and 1|3-1
eg2: p=7
1/7=0.142857
period length =6 and 6|7-1
