AMS 301 : Finite Mathematical Structures

K5 and K3,3
Chapter 1 Section 1 Graphs
Path
A sequence of distinct vertices x1-...-xn
Circuit
A Path with x1-...-xn-x1
Connected
Graph w/ a Path between each V pair
Section 2 Isomorphism
Subgraph
Contains a subset of (the vertices and edges)
Not Isomorphic
Planar & NonPlanar
Section 3 Counting
Theorem 1
Σ D = 2 E
Handshaking Lemma
The # of V's of odd degree is even
Section 4 Connected Planar
Euler's Formula
r = e - v + 2
Corollary
e <= 3v - 6
Bipartite
e <= 2v - 4
Chapter 2 Section 1 Euler
Trail
A sequence of distinct edges, v = x1-...-xn
Cycle
A Trail with x1-...-xn-x1
Euler Cycle
A Cycle that hits each edge
Theorem 1
Euler Cycle ↔ connected and each v has even d
Section 2 Hamilton
Hamilton Path
A Path that hits each v
Hamilton Circuit
A Circuit that hits each v
Section 3 Coloring
Chromatic Number
The # of colors needed to color a graph
Wheel Odd
3 color
Section 4 Coloring Theorem
Theorem
Pk(G) = Pk(G-xy) - Pk(Gx=y)
Chapter 3 Trees Section 1 Trees
#Leaves
1 + (arity - 1)*(# internal nodes)
Balanced Tree
Height = ⌈Log arity #Leaves⌉
Section 2 Spanning Trees
Spanning Tree(G)
Subgraph(G) that's a tree w/ all of G's V's
Chapter 4 Networks Section 1 Shortest Path
Method
Dijkstra. SPT(A)≠SPT(B)
Section 2 Minimum Spanning Trees
Kruskel's Method
Choose the cheapest edge not in the tree
Prim's Method
Choose the cheapest edge connected to the tree
Chapter 5 Counting Section 2 Simple
P(n,r)
r-permutation=n!/(n-r)!
C(n,r)
r-combination=P(n,r)/r!=(ⁿᵣ)
Section 3 Repetition
P(n;r₁,...,rm)
# of dist of n obj if ∃ rn of type n
((ⁿᵣ))
C(r+n-1,r)
Section 4 Distributions
((ⁿᵣ))
  1. # of ways to select r obj w/ rep from n dif types
  2. # of ways to distribute r id objects into n dif boxes
  3. # of nonnegative integer solutions to x₁+...+xn=r
 ArrangementCombination
No repetitionP(n,r)(ⁿᵣ)FermionCommitteeCards
Unlimited repetitionnr((ⁿᵣ)) = BosonNonconsDice
Restricted repetitionP(n;r₁,...,rm) Dorms. Mississippi1
Chapter 6 Section 1 Generating Functions
ar
The # of ways to select r objects.
Section 2 Calculating
(1-xm+1)/(1-x)1/(1-x)1/(1-x)ⁿ
1+x+...+xmΣᵣ xᴿΣᵣ ((ⁿᵣ))xᴿ
Section 3 Partitions
g(x)
1/(1-x)(1-x²)(1-x³)...
Section 4 Exponentials
aᵣ
Coefficient of xᴿ/r!
Section 5 Summation
ₒΣᴿai
h*(x) = h(x)/(1-x)
Chapter 7 Section 1 Recurrence
an
f(a,n)
Section 2 Divide & Conquer An = C * An/k + f(n)
cc=1c=kc>2c=2
f(n)dddndn
And⌈logkn⌉ + AA·n - d/(k-1)A·nlogkc+nkd/(k-c)dn(⌈logkn⌉ + A)
Section 3 Linear: Homogen.
Substitute
an = αⁿ
Section 4 Linear: Inhomogen.
General Solution
Homogeneous + Particular
Section 5 Generating Function
g(x)
Σanxⁿ
Chapter 8 Section 2 Formula
Theorem
N(A̅1A̅2...A̅n) = N - S1 + S2 ... (-1)kSn
Corollary
N = S1 - S2 + S3 - ...