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