Notes Flashcards
What is the formula for lcm(a, b)
ab / gcd(a,b)
What can be said about the gcd and lcm of a, b?
The gcd * lcm = a * b
What is the size of the cartesian product equal to?
The size of A x B equals size A * size B
Difference between () and {} in counting.
() means order is important.
{} means order is not important.
Formula for the amount of subsets of length k from a set A. (Repetitions are allowed!!!)
=|A|^k
where |A| is the number of different elements in A
and k is the length of the subsets.
How many subsets of the set {1,2…n} are there?
Powerset of A = 2^n
When does a bijection exist between two sets X and Y?
If X and Y are two finite sets, then there exists a bijection between X and Y iff |X| = |Y|
Formula for choosing k events from n outcomes where order matters and repetition is allowed.
n^k
where n is the number of outcomes
and k is the number of events to be chosen
Formula for choosing k events from n outcomes where order matters and repetition is not allowed.
n! / (n-k)!
Formula for choosing k events from n outcomes where order doesn’t matter and repetitions are allowed.
(n + k -1
k)
Formula for choosing k events from n outcomes where order doesn’t matter and repetitions are not allowed.
n! / (n-k)!k!
Formula for the binomial identity of equal chooses.
(n) ( n )
(k) = (n-k)
Formula for binomial identity splitting (n)
(k)?
(n) = (n-1) + (n-1)
(k) (k) (k-1)
Formula for binomial identity (n) (k)
(k) (r)?
(n) (n-r)
(r) (k-r)
What is multiplicity in a multiset?
The number of times a certain element appears in a multiset.
Define a multiset A with three 5’s and two 2’s.
{2,2,5,5,5} (stars around list)
What are multisets?
Sets where the order doesn’t matter and repetitions are allowed.
Formula for binomial theorem.
(Sum from k=0 up to n) (n choose k) * x ^ n-k * y^k
Formula to resolve: (x1 + x2 + … xn)^k for multisets.
(Sum of i1 … in)(k choose i1,i2…in) x^ i1x^i2…*x^in
where in is number of xn’s.
Define congruent modulo n?
a equivls b (mod n) if n | a-b
What is zero divisor rule for primes in modular arithemtic?
If n is prime, then ab equivls 0 mod n means that a equivls 0 mod n or b equivls 0 mod n.
Condition in modular arithmetic to check if there is a solution.
ax + by = d (ax equivls d (mod b)) has a solution iff gcd(a, b) | d
How do we know if the inverse exists in the equation ax equivls d (mod n)? How do we find it?
if gcd(a,n) = 1
find the value of x when d = 1. This is the inverse as a * a^-1 = 1
What is the constant rule for modular arithmetic?
ca equivls cb (mod n)
a equivls b (mod n / gcd(c,n))
How do we know how many solutions there are and how much there are separated for the equation. ax equivls b (mod n)
There are gcd(a, n) solutions separated by n / gcd(a,n)
Let p and q be different primes. How many integers in the set {1…pq} are not divisible by p or q?
(p - 1)(q -1)
T or F. If two primes divide a number than their product doesn’t neccesarily also divide the same number.
False. The product always divides aswell.
If n and k are positive integers, the number of integers in {1…n} divisible by k is what
⌊ n / k ⌋
What is φ?
Function that returns the number of positive integers less than the input that are relatively prime to the input.
What is φ(pq) when p and q are distinct primes?
(p - 1)(q - 1)
Give the principle of inclusion/exclusion for 3 sets A,B,C.
|A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
Formulas for simplifying φ(n).
If n is prime. φ(n) = n - 1
φ(n) = φ(k^p) = (k^(p - 1))(p - 1) where p>= 1
φ(mn) = φ(m) x φ(n) where gcd(n, m) = 1.
Define the Pigeonhole Principle.
If we have n objects distributed among k boxes, then there exists at least one box containing at least ⌈n/k⌉ objects.
Formula for counting permutations.
|Sn| = n!
Sn is the number of permutations of size n
|| is the number/length of function
n is the number of choices
Are compositions of permutations always commutative?
No.
p1 ◦ p2 != p2 ◦ p1
Define the composition of two permutations p1 and p2 in S(X).
(p1 ◦ p2)(x) := p1(p2(x))
Formula to calculate permutations with repeated elements.
n! / k1! x k2! … x kn!
How do you calculate the inverse of a permutation?
Switch the order of the rows, and re-order the columns using the new first row as an index.
pi . pi^-1? pi^-1^-1?
=id
=pi
What is the symmetric group?
The set of permutations on the set {1, …, n} is denoted by Sn and is called the symmetric group.
What is a group? What are it’s properties?
A group is a set G with an operation ◦.
Properties:
- If pi and sigma are in G, then pi ◦ sigma is also in G.
- Associativity holds for elements in G.
- All pi in G multiplied by id = pi.
- All pi in G multiplied by pi^-1 = id
Define a cycle?
A cycle maps some elements around in a cyclic fashion and leaves ALL other elements unchanged.
What does a product of disjoint cycles represent? What is a disjoint cycle?
Product of cycles can represent a permutation that is not a cycle.
A cycle used as part of this representation.
If C1 and C2 are disjoint cycles are they commutative?
Yes
C1C2 = C2C1
What is a consequence of a pair of cycles being disjoint?
They share no elements.
How many times must a permutation mapping occur for the identity to be reached?
the order of the permutation times
Define order of pi?
o(pi) = l where pi^l = id
How is the order of a cycle found?
lcm of lengths of cycles in disjoint cycle form.
Define a transposition.
A cycle of length 2.
Can all cycles be written as a product of transpositions?
All cycles of length k can be written as the product of k - 1 transpositions.
What can be said about the parity of the product of transpositions of a cycle?
The parity is constant, we can write the product of transpositions differently but the parity will always be the same.
Define the sign of a permutation.
sign(pi) := (-1)^k where k is the number of transpositions.
What is an even permutation?
A permutation with sign +1.
Is the sign function multiplicative.
Yes.
sign(pi * sigma) = sign(pi) * sign(sigma)
What is the sign of a cycle of length l?
sign = (-1)^(l - 1)
sign(pi) = +1. What is sign(pi^-1)?
+1
How many odd/even permutations are there?
number of even = number of odd = n! / 2
What us the set of even permutations known as?
the alternating group
What is the cycle type of a permutation?
If a1…ak are pairwise disjoint cycles with the length of ai being li then we define the cycle type of pi to be xl1xl2….xlk.
I.e. : x sub length of disjoint cycle
What is the dihedral group?
The group of symmetries.
How many rotations and reflections in D sub n?
n * 2
What can you say if pi and sigma are both elements of D sub 4? (2)
pi * sigma elements of D4 and sigma * pi elements of D4
pi ^ - 1 is an element of D4
What is a subgroup?
A nonempty subset G of Sn where if pi is an element of G than pi^-1 is an element of G, and if pi and sigma are elements of G than pi * sigma is an element of G.
What is the cyclic group?
Rotations only no reflections.
Cn = {id, p, p^2, …, p ^ n -1}
What is the cycle index?
For a group G subset of Sn, cycle index is.
Z sub G = 1 / |G| * (Sum of cycle types for each permutation)
What is a colouring?
A colouring is a function from a set of n objects X to a set of k
colours C.
Define Polya’s Colouring Theorem
Suppose we have n objects, with equivalence defined by a
group of permutations G. Let ZG be the cycle index of the
group G. Then the number distinct colourings using k colours
is given by ZG(k, k, … , k)
How many different bracelets can we make using four beads which can be three colors if (a) no restrictions are imposed (b) rotations are the same (c) rotations and reflections are the same (d) all permutations with the same amount of each color are the same, explain your reasoning for each?
(a) 3^4 (number of colours with four possible places)
(b) 24 (4 P 3)
(c) 21 (Cycle index calc)
(d) 20 (3 + 4 - 1 C 3) (No repetition, order matters)
What is the sequence and sum for the closed form function 1 / 1 - x?
Sequence:
1 + x + x^2 + x^3 +…
n=0 sum infinity (x^n)
n=0 sum infinity (x^n) What is the closed form?
1 / 1 - x
What is the sequence and sum for the closed form function 1 / 1-ax?
1 + ax + a^2x^2 + …
n=0 sum infinity(a^n * x^n)
n=0 sum infinity(a^n * x^n) What is the closed form?
1 / 1 - ax
What is the sequence and sum for the closed form 1 / 1 + x?
1 - x + x^2 - x^3 + …
n=0 sum infinity(-1^n * x^n)
n=0 sum infinity(-1^n * x^n) What is the closed form?
1 / 1 + x
What is the sequence and sum for the closed form 1 / 1 - x^k?
1 + x^k + x^2k + x^3k + …
n=0 sum infinity x^(k*n)
n=0 sum infinity x^(k*n) What is the closed form?
1 / 1-x^k
What is the sequence and sum for the closed form 1 / (1 - x)^2?
(1 + x + x^2 + …)(1 + x + x^2 + …)
n=0 sum infinity
( (n+1) * x^n)
n=0 sum infinity
( (n+1) * x^n) What is the closed form?
1 / (1-x)^2
F(x) = 1 / (1+x)(1-x)^2. How is partial fractions done?
F(x) = A / 1+x + (B+Cx) / (1 - x)^2
What must be watched when adding formal power series?
The powers must match x^n for both or equivalent.
The limits must match, 0 to infinity.
A(x) = n=0 sum infinity (ai * x^n)
B(x) = n=0 sum infinity (bi * x^n).
What is A(x)B(x)?
n=0 sum infinity(
i=0 sum n (
ai * bn-i
)
*
x^n
)
What is the convolution rule?
Let A(x) be the generating function for selecting items from a set A and let B(x) be the generating function for selecting items from a set B disjoint from A. The generating function for selecting items from the union A U B is the product A(x)B(x)
Homogenous recursion relation formula for (a) distinct roots (b) equal roots?
an = A(r1)^n + B(r2)^n
an = A(r^n) + Bn(r^n)
Non homogenous recursion relation explain how to solve.
- an = a + B where a is homogenous solution and B is non homogenous solution.
- a is found in the usual way by treating non-homogenous part as 0
- B is found by replacing an with the correct format depending on the expected answer, and solving for c, d, r and/or e.
- Simply add a and B for an.
What are the different formats for B?
If non homogenous part is constant than replace an with c
If non homogenous part is linear than replace an with cn + d
If non homogenous part is n^2 than replace an with cn^2 + dn + e
If non homogenous part is r^n than replace an with cr^n.
If (x, y) is an element of A x (B ∩ C)?
x ∈ A and y ∈ B ∩ C
If Sp is prime what does that mean for the cycle index when only rotations are allowed?
Cycle Index = 1/p (x^p + (p-1)xsubp )
Every rotation will be a cycle of length p, and the identity is p cycle of length 1.
Formula for splitting n objects in k groups of different sizes namely n1, n2 … nk?
n! / n1! * n2! *… * nk!
State fermat’s little theorem. What is a^40 (mod 100)? Why?
a^(p-1) equivls 1 (mod p). If p is prime.
- phi(100) = 40.
What is the formula for distributing n identical objects into k distinct containers?
(n + k - 1)
(k - 1)
(x + y + z + a)^8 what is the coeffiecient of a^3x^2yz^2
( 8
3, 2, 1, 2)
= 8! / 3! * 2! * 1! * 2!
Formula for phi(n) with prime factors.
phi(n) = n (1 - 1 / prime factor 1)(1 - 1 / prime factor 2)…(1 - 1 / prime factor n)
