# AMS 301 : Finite Mathematical Structures Chapter 1 Chapter 2 Section 1 Graphs PathA sequence of distinct vertices x1-...-xn CircuitA Path with x1-...-xn-x1 ConnectedGraph w/ a Path between each V pair Section 2 Isomorphism SubgraphContains a subset of (the vertices and edges) Not IsomorphicPlanar & NonPlanar Section 3 Counting Theorem 1Σ D = 2 E Handshaking LemmaThe # of V's of odd degree is even Section 4 Connected Planar Euler's Formular = e - v + 2 Corollarye <= 3v - 6 Bipartitee <= 2v - 4 Section 1 Euler TrailA sequence of distinct edges, v = x1-...-xn CycleA Trail with x1-...-xn-x1 Euler CycleA Cycle that hits each edge Theorem 1Euler Cycle ↔ connected and each v has even d Section 2 Hamilton Hamilton PathA Path that hits each v Hamilton CircuitA Circuit that hits each v Section 3 Coloring Chromatic NumberThe # of colors needed to color a graph Wheel Odd3 color Section 4 Coloring Theorem TheoremPk(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 - ...