Chap 7: Counting (Part 2)

Combining Principle:

DEFINITION

•       Using both multiplication and addition principle in solving a complicated counting problems.

•       Mostly used to solved problem in programming.

Example 1

•       The name of a variable is a string of one or two alphanumeric characters, where uppercase and lowercase letters are not distinguished. (An alphanumeric character is either one of the 26 English letters or one of the 10 digits.) Moreover, a variable name must begin with a letter and must be different from the five strings of two characters that are reserved for programming use. How many different variable names are there in this version of BASIC?

•       Solution: Let V equal the number of different variable names in this version of BASIC. Let V1 be the number of these that are one character long and V2 be the number of these that are two characters long. Then by the sum rule, V = V1 + V2. Note that V1 = 26, because a one-character variable name must be a letter. Furthermore, by the product rule there are 26 · 36 strings of length two that begin with a letter and end with an alphanumeric character. However, five of these are excluded, so V2 = 26 · 36 − 5 = 931. Hence, there are V = V1 + V2 = 26 + 931 = 957 different names for variables in this version of BASIC.

Chap 7: Counting (Part 1)

Multiplication Principle (Product Rule):

DEFINITION

If each of m and n is a positive integer, a is an m-element set, and b is an n-element set, then |a × b| = m.n
or restated, |a × b| = |a||b|.

Example 1:

A person wants to go from station A to station C via station B. There are three routes from A to B and four routes from B to C. In how many ways can he travel from A to C?

           Solution: 

                               A –> B in 3 ways

              B –> C in 4 ways

              => A –> C in 3 × 4 = 12 ways

Chapter 6: Graphs and Trees (Part 2)

Euler Path:

}   Let G be a graph, and let a and b be two distinct vertices of G. An Euler Path from a to b is a sequence of adjacent edges and vertices that starts at a, ends at b, passes through every vertex of G at least once, and traverses every edge of G exactly once.

}   Let G be a graph, and let a and b be two distinct vertices of G. There is an Euler path if and only if G is connected, a and b have odd degree, and all other vertices of G have positive even degree.

Fleury Algorithm:

Fleury's algorithm works by simply constructing a path, starting at an arbitrary vertex (or at an odd one if there are any) and picking any of its incident edges, with a single caveat: any edge is permissible but those that leave the remaining graph disconnected. (For a connected graph, an edge whose removal affects the connectivity of the graph is called a bridge.)

Practice: http://www.cut-the-knot.org/Curriculum/Combinatorics/FleuryAlgorithm.shtml

Chap 3: Mathematical Induction (II)

STRONG MATHEMATICAL INDUCTION:

Almost similar to ordinary mathematical induction, however in strong mathematical induction, the basis step may contain proofs for several initial values, and in inductive step the truth of the predicate P(n) is assumed and not just for one value of n but for all from a through k and then the truth of P(k+1) is proved.

Principle of Strong Mathematical Induction:

Let P(n) be a property that is defined for integer n, and let a and b be fixed integer with a≤b.

Suppose the following 2 statements are true:

①    P(a), P(a+1), … and P(b) are all tue (BASIS)

②    For any integer k≥b, if P(i) is true for all int I from a through k, then P(k+1) is true. (INDUCTIVE STEP)

Then, the statement “for all integer n≥a, P(n) is true.”

(The supposition that P(i) is true for all integer i from a through k is called the inductive hypothesis.)

(Another way to state the inductive hypothesis is to say that P(a), P(a+1),…, P(k) are all true)

Note: Any statement that can be proved by ordinary mathematical induction can be proved by strong induction too.

Chap 3: Mathematical Induction (I)

PRINCIPLE OF MATHEMATICAL INDUCTION:

To prove that P(n) is true for all positive integers n, where P(n) is a propositional function by 2 steps:

Basis      : We verify that P(1) is true @ show that an initial value is true for all Z⁺ of the propositional function.

Inductive  : We show that the conditional statement∀k (P(k) → P(k+1)) is true for all Z⁺ of k.

Similarly, we can say that mathematical induction is a method for proving a property defined that the property for integer n is true for all values of n that are greater than or equal to some initial interger.

                   P(1)^∀k(P(k) → P(k+1))) → ∀nP(n)

METHOD OF PROOF:

The proofs of the basis and inductive steps shown in the example illustrate 2 different ways to show an equation is true

p Transforming LHS and RHS independently until they seem to be equal.

p Transforming one side of equation until it is seen to be the same as the other side of the equation.

Chapter 3: Sequences and Mathematical Induction (I)

Presentation week. All notes are available in slides. You can download this slide at this link:
Chapter 3: Sequences and Mathematical Induction (I)