Counting Information



Packet #6: Counting & Graph Theory

Applied Discrete Mathematics

Table of Contents

Counting Pages 1-8

Graph Theory Pages 9-16

Exam Study Sheet Page 17

Counting Information

I. Product Rule: |A×B×C| = |A|*|B|*|C|

II. Union Rule: |A∪B| = |A| + |B| - |A∩B|

III. Inclusion/Exclusion Principle:

The Union Rule applied inductively to: |A[pic]∪A[pic]∪…∪A[pic]|

IV. Selection with Replacement

A. Permutations: n[pic]

B. Combinations: C(n+r-1,r) or C(n+r-1,n-1)

V. Selection without Replacement

A. Permutations: P(n,r)

B. Combinations: C(n,r)

VI. Pigeonhole Principle

If (k+1) or more objects are placed in k boxes, then there is at least one box containing two or more objects.

Counting

Product Rule

|A×B×C| = |A|*|B|*|C|

Examples

Example 1: A = {1,2,3} B = {a,b} C = {a,b,g,d}

How many 3-character words with 1st character from A, 2nd from B, 3rd from C?

Answer: |A|*|B|*|C| = 3*2*4 = 24

Example 2: 3 Independents, 2 Democrats, 4 Republicans

How many ways to form 3-person committee with one member from each party?

Method: Count number of triples

Answer: 3*2*4 = 24

Union Rule

|A∪B| = |A| + |B| - |A∩B|

Example S = {a,b,c}

How many 3-letter words in S[pic] start with a or end in b?

Method:

Let A = 3 letter words starting with "a"

Let B = 3 letter words ending with "b"

Find: |A∪B|

Answer:

|A| = (1) (3) (3) = 1*3*3 = 9

|B| = (3) (3) (1) = 3*3*1 = 9

|A∩B| = (1) (3) (1) = 1*3*1 = 3

|A∪B| = 9 + 9 - 3 = 15

Inclusion/Exclusion Principle

To calculate |A[pic]∪A[pic]∪…∪A[pic]|,

1. Calculate size of all possible intersections

2. Add results from ∩ of odd numbered sets.

3. Subtract results from ∩ of even numbered sets.

Ie. |A[pic]∪A[pic]∪A[pic]| = |A[pic]| + |A[pic]| + |A[pic]| - |A[pic]∩A[pic]| - |A[pic]∩A[pic]| - |A[pic]∩A[pic]| + |A[pic]∩ A[pic]∩ A[pic]|

Example:

How many integers in {1,…,1000} are divisible by either 2, 3, or 5?

A = divisible by 2

B = divisible by 3

C = divisible by 5

Find: |A∪B∪C|

|A| = |{2,4,…,1000}| = 500

|B| = |{3,6,…,999}| = 333

|C| = |{5,10,…,1000}| = 200

|A∩B| = |{6,12,18,…,996}| = 166

|A∩C| = |{10,20,…,1000}| = 100

|B∩C| = |{15,30,…,990}| = 66

|A∩B∩C| = |{30,60,…,990}| = 33

So, |A∪B∪C| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734

Selection with Replacement

Permutations (Order Matters), with replacement: n[pic]

Choose r times from a set of n items with replacement and order matters.

Drawing with replacement (sequence can repeat items):

If there are n distinct objects and we draw r times. Each drawing

has n distinct possibilities. If order matters, then by the product

rule we have n x n x ... x n possibilities = n[pic].

Examples

Example 1: Create a sequence of 10 numbers by rolling a die 10 times. How many possible sequences?

Method: Choose 10 times from a set of 6.

Answer: 6[pic]

Example 2: S = {0,1,…,7}

How many strings of length 5 are there in S[pic]?

Method: Choose 5 times from a set of 8.

Answer: 8[pic]

Combinations (Order Does Not Matter), with replacement: C(n+r-1,r)

Choose r times from a set of n items with replacement and order does not matter.

The number of possible outcomes is written as C(n+r-1,r).

Combinations are discussed in more detail later.

Example:

You have 4 different kinds of cookies. How many different ways can 6 cookies be chosen?

Method: Choose 6 times from a set of 4 with replacement and order does not matter.

Answer: C(4+6-1,6) = C(9,6) = [pic] = 84

Selection without Replacement

Permutations (Order Matters): P(n,r)

Choose r times from a set of n items without replacement and order matters.

If we do not have replacement but order matters:

Then first drawing has n possibilities; the second drawing has (n-1), the third has

(n-2), etc. By the product rule we have: n x (n-1) x (n-2) x ... x (n-r+1) = [pic].

This is usually called permutations of n things taken r at a time. The number of possible outcomes is P(n,r) = [pic]

Examples

Example 1: Six CD's with 57 songs. CD player can be programmed to play any 20 songs in any order. How many ways can 20 different songs be played?

Method: Choose 20 from 57 without replacement, order matters

Answer: P(57,20) = [pic]

Example 2: Given n integers x[pic], x[pic],…, x[pic], all distinct. How many sorted arrangements are possible (i.e. how many permutations of x[pic]… x[pic]?) Method: Choose all n items from n, without replacement, order matters

Answer: P(n,n) =[pic] = [pic] = n!

Example 3: S = {a,b,c,d,e,f}

How many 3-letter words are in S[pic] which have no character repeated?

Method: Choose 3 from 6 without replacement and order matters.

Answer: P(6,3) = [pic] = 6*5*4 = 120

Combinations (Order Does Not Matter) without replacement: C(n,r)

Choose r times from a set of n items without replacement and order doesn't matter.

If order does not count and there is no replacement, then we must

determine how many of the permutations are the same objects but only differ in order. That is: In how many orders can n distinct objects be arranged?

P(n,n) = [pic] = n!. Therefore, if order does not matter and we do not have replacement, the number of possibilities for n objects taken r at a time is [pic] = [pic]. This is usually referred to as combinations of n things taken r at a time = C(n,r).

There is another important type of combination, combinations

with replacement. The sequence can repeat, but order does not

matter. (Discussed Earlier)

Number of ways to choose r from n is C(n,r) = [pic]

Example

How many ways can you choose a committee of 5 from 7 people?

Answer: C(n,r) = [pic]= [pic]= 21

Summary of Permutations and Combinations

|Type (n things, r times) |Order Counts |Replacement |Symbol |Expression |

|Permutations w/ repl. |Yes |Yes |None |nr |

|Permutations - no repl. |Yes |No |P(n,r) |n! |

| | | | |(n-r)! |

|Combinations - no repl. |No |No |C(n,r) |n! |

| | | | |(n-r)! r ! |

|Combinations - w/ repl. |No |Yes |C(n+r-1,r) |(n+r-1)! |

| | | | |r ! (n-1)! |

More Examples

Example 1: Place n indistinguishable objects into r distinguishable boxes. Number of possible outcomes is C(n+r-1,r-1).

[pic]

0 0 1 0 0 0 1 0 0 0 1 0

(n+r-1) bits, (r-1) ones: C(n+r-1,r-1)

0 0 0 1 1 0 0 1 0 0 0 0

[pic]

Example 2: 12 identical flyers are to be placed into 4 mailboxes. How many ways can this be done?

Answer: C(12+4-1,4-1) = C(15,3) = [pic] = [pic] = 455

What if each mailbox must receive at least 2 letters?

Method: Put 2 letters in every box. Then, how many ways are there to distribute remaining 4 among 4 mailboxes?

Answer: C(4+4-1,4-1) = C(7,3) = [pic] = [pic] = 35

Example 3a: 15 basketball players are to be drafted by 3 professional teams (A,B,C). Each team will draft 5 players. In how many ways can this be done?

Method: Choose 5 from 15 for A: C(15,5), 5 from remaining 10 for B: C(10,5), C has remaining 5: C(5,5) = 1 (multiply all three together). This determines all the ways we can partition the players where A chooses first, B second, and C last.

Answer: C(15,5)*C(10,5)

Example 3b: Now, if we cannot tell which team is which, we say the teams are indistinguishable. If this is the case, how many ways can 15 players be partitioned into 3 teams of 5 each? (i.e. - we want to know how many different sets {A,B,C} there are. In 3a, we could have one division with

(A,B,C) = ({1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}) and another with

(A,B,C) = ({6,7,8,9,10},{1,2,3,4,5},{11,12,13,14,15}).

But these two examples divide the fifteen players up into the same groups.)

Answer: [pic] (since the teams are indistinguishable)

Example 4: In how many ways can 2n people be divided into n pairs without replacement and order does not matter?

Answer: [pic]

Example 5: In how many ways can 10 boys and 5 girls stand in a line if no 2 girls can stand next to each other?

Boy1 Boy2 ... Boy10

Method: Choose one slot for each girl (Select 5 slots from 11, without replacement and order matters.).

Answer: There are 10! ways to place the boys and P(11,5) ways to place the girls, so by the product rule the answer is 10! * P(11,5).

Example 6: In how many ways can 2 distinct numbers be selected from 1,2,...,100 so that their sum is even?

Answer: (2 Odds) C(50,2) + (2 Evens) C(50,2) = 50*49

Example 7: In how many ways can 2 distinct numbers be selected from 1,2,...,100 so that their sum is odd?

Answer: Choose 1 even and 1 odd = C(50,1) *C(50,1)= 50*50

Pigeonhole Principle

If (k+1) or more objects are placed in k boxes, then there is at least one box containing two or more objects.

Examples

Example 1: If you have a group of 367 people, there must be at least two people who have the same birthday (there are only 366 possible birthdays).

Example 2: If you have a group of 27 English words, there must be at least two words that begin with the same letter (there are only 26 possible letters in the English language).

Graph Information

I. Basic Definitions

II. Euler Circuit and Fleury's Algorithm

III. Hamilton Cycle

IV. Kruskal's Algorithm

V. Matrix Representation of Graphs

VI. Hasse Diagrams

Graphs

Basic Definitions

path: (way of getting from one vertex to another via edges) - sequence of vertices in which successive vertices are joined by an edge

length of path: number of edges in path

Example

[pic]

paths: uvwxy (length 4)

uxy (length 2)

uxwustxzy (length 8)

closed path: first vertex = last vertex

cycle: closed path in which all vertices are distinct, except first = last

acyclic graph: graph with no cycle

Example

[pic]

closed path: xyztx also cycle

closed path: swxtzyxs not cycle

closed path: uvwvu not cycle

acyclic graph:

[pic]

A graph is connected if every pair of vertices is joined by a path.

Example

Connected Not connected

[pic] [pic]

The degree of a vertex is the number of edges touching the vertex. (loops count twice)

Example

[pic]

Vertex Degree

u 2

v 2

x 4

y 4

z 4

Euler Circuit and Fleury's Algorithm

Euler circuit: closed path which uses each edge exactly once

Can show there is an Euler circuit if and only if every vertex has even degree. ("easy" to find)

Fleury's algorithm will always find Euler circuit in connected graph if every vertex has even degree.

Fleury's Algorithm

Start at any vertex v

While (still more edges incident with v) do

- if possible choose edge vw which does not disconnect

- else choose only vw and delete v

- delete edge vw

- v := w

end do

Example of Fleury's Algorithm

[pic] [pic] [pic]

[pic] [pic] [pic]

[pic] [pic] [pic]

[pic] etc.

Euler circuit: 23215341452

Hamilton Cycle

Hamilton cycle: cycle which uses each vertex once

"hard" problem (version of Traveling Salesman Problem)

Example

[pic]

Hamilton cycle: uvtwxysu

Kruskal's Algorithm

Minimum cost network to connect sites.

Given sites and link costs

Kruskal's Algorithm

Start with no edges.

Examine edges in non-decreasing order of weight.

If an edge does not create a cycle, add it.

Example of Kruskal's Algorithm

[pic]

[pic]

Matrix Representation of Graphs

Label vertices v[pic], v[pic],…, v[pic]

Adjacency matrix M: nxn matrix with M[x,y] = number of edges joining v[pic]and v[pic].

Examples of Adjacency Matrices

[pic]

[pic]

Graph isomorphism: Graphs G and H are isomorphic if there is some way to label the vertices of H so that H is G (ie, has same adjacency matrix).

Examples

[pic]

[pic]

Suppose M is the adjacency matrix of a graph G. Can prove by induction:

M[pic][i,j] = number of length-k paths joining i and j

Reachability Matrix R

[pic]

Fourth Hour Exam Study Sheet

I. Counting

A. Basic Rules (Product, Union, Inclusion/Exclusion)

B. Selection with Replacement (Permutations, Combinations)

C. Selection without Replacement (Permutations, Combinations)

D. Pigeonhole Principle

II. Graphs

A. Basic Definitions

B. Euler Circuit and Fleury's Algorithm

C. Hamilton Cycle

D. Kruskal's Algorithm

E. Matrix Representation of Graphs

F. Hasse Diagrams

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download