COUNTING

                                                                  
i) Describe each of the basic principles in counting:

-Explain the Multiplication Principle and give 1 example question with solution for this principle

def:  Multiplication Principle states: If an event occurs in m ways and another event occurs independently in n ways, then the two events can occur in m × n ways.

Example -1: A college offers 7 courses in the morning and 5 in the evening. Find the possible number of choices with the student if he wants to study one course in the morning and one in the evening.

Solution: The student has seven choices from the morning courses out of which he can select one course in 7 ways.

For the evening course, he has 5 choices out of which he can select one in 5 ways.

Hence the total number of ways in which he can make the choice of one course in the morning and one in the evening =   7 × 5 = 35.

-Explain the Addition Principle and give 1 example question with solution for this principle

Def: If one experiment has n possible outcomes and another has m possible outcomes, then there are (m + n) possible outcomes when exactly one of these experiments is performed.

 In other words, if a job can be done by n different methods and for the first method there are a1 ways, for the second method there are a2 ways and so on . . . for the nth method, an ways, then the number of ways to get the job done is (a1 + a2 + ... + an).

Example :  A college offers 7 courses in the morning and 5 in the evening. Find the number of ways a student can select exactly one course, either in the morning or in the evening.

Solution:  The student has seven choices from the morning courses out of which he can select one course in 7 ways.

For the evening course, he has 5 choices out of which he can select one course in 5 ways.

Hence he has total number of 7 + 5 = 12 choices.

 -Explain the combining principle (multiplication &addition) and give 1 example question with solution for this principle

Example:

-4+9x+4 > -10x+7

Solution:

Combine like-terms on the left side:

9x > -10x+7

Add 10x to both sides:

9x+10x > -10x+7+10x

19x > 7

Divide both sides by 19:

19x/19 > 7/19

x > 7/19

ii)Permutation -give a definition, formula and 1 example question with solution

def: An arrangement is called a Permutation. It is the rearrangement of objects or symbols into distinguishable sequences. When we set things in order, we say we have made an arrangement. When we change the order, we say we have changed the arrangement. So each of the arrangement that can be made by taking some or all of a number of things is known as Permutation.

Formula:

Example:

 It is required to seat 5 men and 4 women in a row so that the women occupy the even places. How many such arrangements are possible?

Solution:

We are given that there are 5 men and 4 women.

(i. e) there are 9 positions.

The even positions are , 2nd, 4th, 6th and the 8th places

These four places can be occupied by 4 women in P(4, 4) ways = 4 !

= 4 . 3. 2. 1

= 24 ways

The remaining 5 positions can be occupied by 5 men in P(5,5) = 5!

= 5.4.3.2.1

= 120 ways

Therefore, by the Fundamental Counting Principle,

Total number of ways of seating arrangements = 24 x 120

= 2880

iii)Combination - give a definition, formula and 1 example question with solution

def: A Combination is a selection of some or all of a number of different objects. It is an un-ordered collection of unique sizes.In a permutation the order of occurence of the objects or the arrangement is important but in combination the order of occurence of the objects is not important.

 Formula:

n = the number of objects to choose from

k = the number of objects selected

Example:

 The number of possible combinations with repetition of   objects from   is

solution 

iv) Pigeon Hole Principle - give a definition, formula and 1 example question with solution.

def:

The pigeonhole principle is one of the most used tools in combinatorics, and one

of the simplest ones. It is applied frequently in graph theory, enumerative combinatorics

and combinatorial geometry. Its applications reach other areas of mathematics,

like number theory and analysis, among others. In olympiad combinatorics

problems, using this principle is a golden rule and one must always be looking for

a way to apply it.

Formula:

The statement above is a direct consequence of the Pigeonhole Principle:

(1)          If m pigeons are put into m pigeonholes, there is an empty hole iff there's a hole with more than one pigeon.

Variously known as the Dirichlet Principle, the statement admits an equivalent formulation:

(2)          If n > m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.

A more formal statement is also available:

(3)          Let |A| denote the number of elements in a finite set A. For two finite sets A and B, there exists a 1-1 correspondence f: A->B iff |A| = |B|.

Example:

Consider a chess board with two of the diagonally opposite corners removed. Is it possible to cover the board with pieces of domino whose size is exactly two board squares?

Solution

No, it's not possible. Two diagonally opposite squares on a chess board are of the same color. Therefore, when these are removed, the number of squares of one color exceeds by 2 the number of squares of another color. However, every piece of domino covers exactly two squares and these are of different colors. Every placement of domino pieces establishes a 1-1 correspondence between the set of white squares and the set of black squares. If the two sets have different number of elements, then, by the Pigeonhole Principle, no 1-1 correspondence between the two sets is possible.

GRAPH THEORY

GRAPH THEORY

1) Give the definition and example for each of the following term:
 
    a) Euler Path:
        Euler Path is a path that use every edge of a graph exactly once. The starting and ending points need   
        not be the same.

        example:

     

     (E,C,A,C,D,A,B,D)

 

    b) Euler Circuit:
        Euler Circuit is a circuit that use every edge of the graph exactly once. The starting and ending points
        must be the same.
     
         example:

   (D,E,C,B,A,F,D)
 

2) Determine what are the properties that differentiate between (a) and (b) in question 1?
    a) If a graph only vertices of odd degree, then it cannot have on Euler Circuit.
    b) If a graph is connected and and every vertex have even degree, then it has at least one Euler Circuit  
        (usually more).

3) What are the algorithm or step by step to determine (a) and (b) in Question 1?
    a) Make sure the graph has either 0 or 2 odd vertices.
    b) If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of them.
    c) Follow edges one at a time. If you have a choice between a bridge and non-bridge always choose the
        non-bridge.
    d) Stop when you run out of edges.

4) Give the definition and example for each of the following term:

   a) Hamilton Path:
       Hamilton Path is a path that passes through all the vertices of the graph, each vertex exactly once.

     example:

  G2= (a,b,c,d)

  b) Hamilton Circuit:
      Hamilton Circuit is a circuit that start at one vertex that visits every other vertex in the graph exactly once
      and return to its starting point.

      example:

G1= (a,b,c,d,e,a)

5) Determine what are the properties that differentiate between (a) and (b) in Question 4?

    a) Any Hamilton Circuit can be converted to the Hamilton Path by removing one of its edge but a
        Hamilton Path can be extended to Hamilton Circuit only of its ending points are adjacent.

      - Hamilton Circuit:

• n ≥3 vertex
• degree of every vertex is at least n/2
• degree u and v  ≥  n for every pair of nonadjacent  vertices u and v in the graph.

6) What are the algorithm or step by step to determine (a)and (b) in Question 4:

• List edges in increasing order.
• Choose edge of least weight and mark edge.
• Choose next edge of least weight if the edge does not complete a circuit before all vertices have been visited or does not result in 3 marked edges at a vertex.
• Continue step 3 until  Hamilton Circut is form.

CHAPTER 3:SEQUENCES

SEQUENCES

A discrete structure used to represent an ordered list.

example:

Let an be a sequence that satisfies the recurrence relation an = an-1 +3 for n = 1, 2. 3, .... and suppose that
                                   a0 = 2. What are a1 ,a2, a3 ?

solution:

We see from the recurrence relation a1 = a0 + 3 = 2 + 3 = 5. It then follows that a2 = 5 + 3 = 8 and a3 = 8 + 3 = 11

Types Of Sequence:

1) Arithmetic Progression

 A sequence of the form a, a+d, a+2d, .....a+nd,.... where the initial term, a and common    difference, d are real number.

Example of arithmetic progression:

Find the sum of the first 10 terms of the following series:
3, 8, 13, 18, 23, 28, 33, 38, 43,...

Solution: 

If you observe the above series, you noticed that there is a fixed difference of 5 between successive terms and is it so an Arithmetic Series. Therefore i=3, d=5, n=10

S= (n/2)[2i+(n-1)d] = 5[6+9(5)]=255
S10=255


2) Geometric Progression

A sequence of the form a, ar, ar²,….,arⁿ,…. where the initial term, a and common difference, d are real number.

Example of geometric progression:

Find the number of terms in geometric progression 6, 12, 24, 34,...1536

Solution: 

a1=6, a2=12, a3=24, an=1536
r=a2/a1=12/6=2
1536=(6)(2)^n-1
256=2^n-1
2^8=2^n-1
8=n-1
8+1=n
n=9
hence, 1536 in 9th term


Example sequences use in computer programming

Sequences of the form a1,a2,a3...are often used in computer  sciences.
These  finite sequences also called strings.The sring is also denoted by a1,a2,a3...The length of a string is the number of terms in this string.The empty string, denoted by λ, is the string that no terms.The length zero.

example:

                     The string abcd is the string of length four

Mathematical Induction

Principle of Mathematical Induction

to prove that P(n) is true for all positive integers n, where P(n) is a propositional function, we complete two steps:

• Basic Step : we verify that P(1) is true.
• Inductive Step: we show that the conditional statement P(k) → P(k + 1) is true for all positive integers k.

In the induction step, the assumption that P(n) holds is called the Induction Hypothesis.In more formal notation, this proof technique can be stated as 

      In the induction step, the assumption that P n holds is called the Induction Hypothesis

(IH). In more formal notation, this proof technique can be stated as

                                        (P(1) ˄  ∀k( P(k) → P(k +1))) → ∀n P(n)

EXPLAIN THE PROOF OF MATHEMATICAL INDUCTION

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers (positive integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.

A more precise definition of the principle of induction can be stated in terms of propositions about the natural numbers. A proposition P(i) about the natural numbers is a statement that for is either true or false each natural number i. For instance, P(i) could be "i is an even number". In that case P(4) would be true, but P(7) would be false. In these terms, induction is usually defined in the following manner.

The Principle Of Induction

If P(1) is true, and if whenever P(i) is true, we can infer the truth of P(i+1), then P(i) is true for all natural numbers i.

This makes sense because, if P(1) is true, then we know we can infer the truth of P(1+1) = P(2), which in turn means we can infer the truth of P(2+1) = P(3), and so on into infinity. Hence, we arrive at the most important fact about induction: if we can count, we probably use induction!

Example problem that use Mathematical Induction 

1)  Prove that   1 + 3 + 5 + … + (2n-1) = n² , for all n Î P.

Ans:

        Basic Step:

        Take n=1, LHS =2(1) –1 =1.           RHS=1²=1 , Therefore LHS=RHS

        Take n=2, LHS =1 + [2(2) –1] =4.  RHS=2²= 4 , Therefore LHS=RHS

       

         Inductive Step:

          p(n) ®  p(n+1) is true for all n Î P.

          p(n) : 1 + 3 + 5 + … + (2n-1) = n²  is true for all n Î P , then we have to prove

          p(n+1) : 1 + 3 + 5 + … + (2n-1) + [2(n+1)-1]= (n+1)²  is true for all n Î P .

      

          Proof:

           1 + 3 + 5 + … + (2n-1) + [2(n+1)-1] = 1 + 3 + 5 + … + (2n-1)  + [2n+2-1]

                                                                      = 1 + 3 + 5 + ...  + [ 2n +1 ]

                                                                      = n² + 2n  + 1

                                                                      = n²  + 2n  + 1

                                                                      = ( n + 1 )² = RHS   - proved.

 2) Prove that   1 + 2 + 3 + …. + n = [n(n+1)] / 2   , for all n Î P.

Ans:

        Basic Step:

        Take n=1, LHS= 1             RHS =[1(1+1)] / 2=1(2) /2 =1.   Therefore LHS=RHS

        Take n=2, LHS =1+2=3    RHS =[2(2+1)] / 2=[2(3)] /2 =3. Therefore LHS=RHS

     

         Inductive Step:

          p(n) ®  p(n+1)  is true for all n Î P , then

          p(n) : 1 + 2 + 3 +…. + n=[n(n+1)] / 2 is true for all n Î P. ,then we have to prove

          p(n+1) : 1 + 2 +3 +  … + n + (n+1)= [ (n+1){(n+1)+1 }] / 2  is true for all n Î P.

                                                                  = [ (n+1)(n+2) ] /2  is true for all n Î P.

        Proof:

          1 + 2 +3 +  … + n + (n+1)   = 1 + 2 +3 +  … + n + (n+1)

                                                      =­ 1 + 2 +3 +  … + n + (n + 1)

                                                      =  [n(n+1)] / 2 +  n + 1

                                                      =  [n(n+1)] / 2 + 2( n + 1)/2

                                                      =  [ n(n+1) + 2n + 2] / 2

                                                      =  [ n² +n + 2n + 2 ] / 2

                                                      =  [ n² + 3n + 2 ] / 2

                                                      =  [ (n+1)(n+2) ] /2  = RHS  -- proved.

                                        _n

Summation  Notation.:  å

                                       ⁱ⁼¹  

                    

                                                                                                 _n

Example:  .i) p(1) + p(2) + p(3) + …. + p(n)  can be written as  å  p(n).

                                                                               .                ⁿ⁼¹

                         _n

                    ii)  å  k = 1 + 2 + 3 + ….. + n

 .                 .     ^k=1

                        _n

                   iii) å 2k = 2 + 4 +  6 + ….. + 2n

                       ^k=1

                        _2n

                   iv) å 2k = 2 + 4 +  6 + ….. + 2n + 2(n+1) + ….. + 4n

                       ^k=1

                        _n-1

                    v) å 2k = 2 + 4 +  6 + ….. + 2(n-1)

                        ^k=1

                       _2n-1

                   vi) å 2k = 2n + 2(n+1) +….. …..+ 2(2n-1)

                       ^k=n

Example:        _n

1) Prove that  å (3k – 2 ) = (3n² –n ) /2  for all n Î P.

                     ^k=1 

Ans:

        Basic Step:

        Take k=1, n=1 LHS= 3(1)-2=1 :  RHS =[3(1²)-1]/2= 2 /2 =1. Therefore LHS=RHS

        Take k=1, n=2, LHS =[3(1)-2] + [3(2)-2]=1 + 4 =5  : RHS =[3(2²)-2]/2= 10/2=5 .                                    

                                 Therefore LHS=RHS

         Inductive Step:

        p(n) ®  p(n+1) is true for all n Î P.

                     _n

           p(n):   å (3k – 2 ) = (3n² –n ) /2  is true for all n Î P , then we have to prove

                    ^k=1

                                 _n+1

            p(n+1):   å (3k – 2 ) = [3(n+1)² –(n+1)] /2  for all n Î P.

                         ^k=1

           Proof:

                                _{n+1                        n}

            LHS =  å (3k – 2 ) =  å (3k – 2 )  + [3(n+1) –2]

                        ^{k=1                       k=1}

                                            =  ­_from p(n)_­ + [3n +1]

                                             =  (3n² –n ) /2     + [3n +1]

                                            =  (3n² –n ) /2     +  (2[3n +1])/2

                                             = {(3n² –n )   + 2[3n +1] } / 2

                                             = {(3n² –n  + 6n +2)} / 2

                                             =  [3n² + 5n +2 ] / 2

            RHS = [3(n+1)² –(n+1)] /2

                     = [3(n² +2n +1)–(n+1)] /2

                     = [3n²  + 6n +3 – n-1)] /2

                     =  [3n²  + 5n + 2)] /2                        

           Therefore LHS =  RHS  , proved.