MATH 240 QUESTIONS AND CORRECT
ANSWERS
When is x invertible mod m (x,m∈∈ℤ)? ✅✅ANSW-xy ≡ 1 (mod m) ⟺ gcd(x,m) = 1
Permutations ✅✅ANSW-A permutation of a set X of size n is a bijection f: X → X. X has are n!
permutations.
k-subset of an n-set ✅✅ANSW-Ordered: n(n-1)...(n-k+1) = n!/(n-k)!
Unordered: Given a k-set, there are k! ways of ordering it. Thus, (# ordered sets)/(# orderings/set) =
# unordered. (n!/(n-k)!)/k! = n!/(k!(n-k)!)
How many ways are there to arrange an n-set around a circle? ✅✅ANSW-n!/n = (n-1)!
Principle of Inclusion-Exclusion ✅✅ANSW-|∪Ai| = ∑|Ai| - ∑|Ai∩Aj| + - ... + (-1)ⁿ⁻¹|A₁∩A₂...∩An|
Erdos-Ko-Rado Theorem ✅✅ANSW-If F is an intersecting family of k-subsets of [n], n ≥ 2k, |F| ≤
(n-1)!/((k-1)!(n-k)!)
What is the largest intersecting family of an n-set? ✅✅ANSW-The collection of all subsets
containing some fixed element, F. |F| = 2ⁿ⁻¹
Given n people, where everyone shakes hands with everyone else exactly once, how many
handshakes occur? ✅✅ANSW-Let each person be a node, and each handshake be an edge. Then
this is a complete graph on n vertices, Kn, so there are n(n-1)/2 handshakes.
Walk ✅✅ANSW-Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge
Path ✅✅ANSW-Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge, vi ≠ vj if i ≠ j
Closed walk ✅✅ANSW-Sequence v₀,v₁,....vk of vertices such that vi, v(i+1) share an edge, and v₀ =
vk
ANSWERS
When is x invertible mod m (x,m∈∈ℤ)? ✅✅ANSW-xy ≡ 1 (mod m) ⟺ gcd(x,m) = 1
Permutations ✅✅ANSW-A permutation of a set X of size n is a bijection f: X → X. X has are n!
permutations.
k-subset of an n-set ✅✅ANSW-Ordered: n(n-1)...(n-k+1) = n!/(n-k)!
Unordered: Given a k-set, there are k! ways of ordering it. Thus, (# ordered sets)/(# orderings/set) =
# unordered. (n!/(n-k)!)/k! = n!/(k!(n-k)!)
How many ways are there to arrange an n-set around a circle? ✅✅ANSW-n!/n = (n-1)!
Principle of Inclusion-Exclusion ✅✅ANSW-|∪Ai| = ∑|Ai| - ∑|Ai∩Aj| + - ... + (-1)ⁿ⁻¹|A₁∩A₂...∩An|
Erdos-Ko-Rado Theorem ✅✅ANSW-If F is an intersecting family of k-subsets of [n], n ≥ 2k, |F| ≤
(n-1)!/((k-1)!(n-k)!)
What is the largest intersecting family of an n-set? ✅✅ANSW-The collection of all subsets
containing some fixed element, F. |F| = 2ⁿ⁻¹
Given n people, where everyone shakes hands with everyone else exactly once, how many
handshakes occur? ✅✅ANSW-Let each person be a node, and each handshake be an edge. Then
this is a complete graph on n vertices, Kn, so there are n(n-1)/2 handshakes.
Walk ✅✅ANSW-Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge
Path ✅✅ANSW-Sequence v₀,v₁,... of vertices such that vi, v(i+1) share an edge, vi ≠ vj if i ≠ j
Closed walk ✅✅ANSW-Sequence v₀,v₁,....vk of vertices such that vi, v(i+1) share an edge, and v₀ =
vk
