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))
