Discrete Mathematics I

Front 1

Arrangement

Back 1

Finite list of items that may be repeated where order is important.

Front 2

Permutations

Back 2

A permutation of S is a list of elements ∈ S where each element is used exactly once and order matters.

Front 3

Combination

Back 3

A combination from S is an unordered selection of elements ∈ S used any no. times.

Front 4

How many arrangements of length k can be made from elements of a set, S, of size |S|=n?

Back 4

nᵏ

Front 5

How many arrangements of length k with no repeats can be made from elements of a set S of size |S| = n?

Back 5

n!/(n-k)! for k≤n

Front 6

How many arrangements are there of a list of (potentially repeated) objects?

Back 6

n!/(n₁!n₂!···nᵣ!) where nᵢ is no. of object i.

Front 7

How many k-combinations with repetitions from n objects are there in which each object is chosen at least once?

Back 7

C(k-1,n-1)

Front 8

Given a set of n objects, how many k-combinations can be chosen if objects may be selected more than once?

Back 8

C(k+n-1,n-1)=C(k+n-1,k)

Front 9

Pascal′s Theorem

Back 9

C(n,r) = C(n-1,r-1) + C(n-1,r)

1≤r≤n-1

Front 10

Inclusion-Exclusion Formula

Back 10

|A₁∪A₂∪···∪Aₙ| = ⁿ∑ⱼ₌₁(−1)ʲ⁺¹Sⱼ,

where Sⱼ = ∑|Ai₁∩Ai₂∩···∩Aiⱼ|

and i₁<i₂<...<iⱼ.

Front 11

How do you solve an homogeneous recurrence relation?

Back 11

-Solve characteristic eqⁿ with roots αᵢ.

-If distinct then aₙ=g(n)=ʳ∑ᵢ₌₁dᵢαᵢⁿ

-If α=α₁=α₂=...=αⱼ use (e₁+...+eⱼnʲ⁻¹)αⁿ

-Apply initial conditions.

Front 12

How do you solve an inhomogeneous recurrence relation?

Back 12

-Solve homogeneous case without initial conditions, g(n).

-Find p(n):

Anʳ try ʳ∑ᵢ₌₀Bᵢnⁱ

Aqⁿ try B₀qⁿ (if qⁿ∈g(n) or 1 is a root, try nᵏqⁿ for lowest possible k)

Anqⁿ try (B₀+B₁n)qⁿ

-GS = g(n) + p(n), apply initial conditions.

Front 13

Lemma 7.1

Back 13

ⁿ∑ₖ₌₀xᵏ = (1-xⁿ⁺¹)/(1-x)

∞∑ₖ₌₀xᵏ = 1/(1-x)

∞∑C(n+k-1,k)xᵏ = 1/(1-x)ⁿ

(∞∑ₖ₌₀aₖxᵏ)(∞∑ₖ₌₀bₖxᵏ) = ∞∑ₖ₌₀cₖxᵏ

where cₖ = ᵏ∑ⱼ₌₀aⱼbₖ₋ⱼ

Front 14

Partition

Back 14

A partition of a positive integer, n, is an expression of n as an unordered sum of positive integers.

Front 15

How do you find no. of partitions of n, ie. p(n)?

Back 15

Generating function:

∞∑ₙ₌₀xⁿp(n) = ∞Πₖ₌₁(1-xᵏ)⁻¹

Front 16

If aₙ has GF f(x)=∞∑ₙ₌₀aₙxⁿ, then what is the GF of bₙ=naₙ?

Back 16

xf′(x)

Front 17

If f(x) is the GF of aₙ then what is the GF of sₙ = ⁿ∑ₖ₌₀aₖ?

Back 17

f(x)/(1-x)

Front 18

Principle of upper negation

Back 18

C(-n,k)=(-1)ᵏC(k+n-1,k)

Front 19

The pigeon-hole principle.

Back 19

If n envelopes are distributed among m pigeon-holes, and n>m, then at least one pigeon-hole contains more than one envelope.

Front 20

Simple graph

Back 20

Pair of sets G = (V,E) where each element of E is a two-element subset of V.

Front 21

Leaf

Back 21

Vertex of degree 1.

Front 22

What are Nₘ, Kₘ, Sₘ, Wₘ, Qₙ?

Back 22

Nₘ = Null graph, m vertices with no edge.

Kₘ = Complete graph, m vertices with (ᵐ₂) edges between each pair of vertices.

Sₘ = Star graph, m-1 leaves each with an edge to central hub vertex.

Wₘ = Wheel graph, star graph with cycle around non-hub vertices.

Qₙ = n-cube, n vertices with binary strings, edges join vertices where binary differ by one digit.

Front 23

Handshaking

Back 23

∑ d(v) = 2|E|

No. odd degree vertices is always even.

Front 24

Isomorphic

Back 24

Two simple graphs G1 = (V1,E1) and G2 = (V2,E2) are isomorphic if ∃ a bijection ϕ : V1 → V2 that preserves adjacency, i.e., xy ∈ E1 ⇔ ϕ(x)ϕ(y) ∈ E2.

Front 25

Complement and subgraphs

Back 25

If G=(V,E), then G₁=(V₁,E₁) is a subgraph of G if V₁⊆V,E₁⊆E

and if G is simple the complement is ⃗G⃗=(V,F) where F={uv:u,v∈V and uv∉E}.

Front 26

Walks, trails and circuits.

Back 26

A walk of length n-1 is a sequence of vertices and edges alternately (v₁e₁...vₙ₋₁eₙ₋₁vₙ). If v₁ = vₙ, the walk is closed. A trail is a walk with no edge repeated and a circuit is a closed trail.

Front 27

Paths and cycles

Back 27

A path is a walk with no vertex repeated. A cycle is a closed path, an n-cycle is a cycle of n vertices. If every vertex has degree > 1 then G contains a cycle.

Front 28

Connectedness

Back 28

A graph G = (V,E) is connected if ∀ v,w ∈ V ∃ a path from v to w. Otherwise it has two or more connected components.

Front 29

Bridge

Back 29

A bridge is an edge whose removal would increase the number of connected components, e is a bridge ⇔ e is not part of a cycle.

Front 30

Euler Circuit

Back 30

An Euler circuit is a circuit using each edge exactly once. A graph with an Euler circuit is called Eulerian. G has an Euler circuit ⇔ all vertices of G have even degree.

Front 31

Bipartite Graphs

Back 31

A graph G=(V,E) where V=V₁∪V₂ and V₁∩V₂=∅. A complete bipartite graph, Kₘ,ₙ has |V1| = m, |V2| = n.

Front 32

Planar Graphs

Back 32

A graph G is planar if it can be drawn in the plane so that no edges meet except at their endpoints. Such a drawing is a planar representation of G.

Front 33

Faces and Boundaries

Back 33

A planar representation divides the plane into faces. The boundary of a face is a closed walk (of length b(f)) around it. ∑b(f) = 2|E|.

Front 34

Euler′s Formula

Back 34

Let G = (V,E) be a planar graph, with set of faces F, and k connected components. Then |V|−|E|+|F| = k+1.

⇒ For simple G with |V|≥ 3, then |E|≤3|V|−6.

Front 35

Girth

Back 35

The girth, g, of G is the shortest length of a cycle in G. If G has no cycles, then g = 0.

|E|≤g(|V|−2)/(g−2).