PERMUTATION AND COMBINATION

ii)Permutation

Definition : arrangement that can be made by taking some or all of a number of things,

Formula :nP ͬ = n!/(n-r)!

n,r : non negative integers (r <= n)

r : size of the each permutation

n : size of set from which elementsare permuted

! : factorial operator

 Question :

If you have 6 new year greeting cards and you want send them to 4 of your friends, in how many ways can this be done?

Solution :

We have to find number of permutation of 4 objects out of 6 objects. This number is 6P4 = 6(6-1)(6-2)(6-3) = 6*5*4*3 = 360

Therefore, cards can be sent in 360 ways

6P4 = 6! / (6-4)!

iii)Combination

Definition :

 A combination is a selection of some or allof a numberof different object. It is an un-ordered collection of unique sizes,

Formula : nC ͬ = nP ͬ /r!

n,r : non negative integers (r <= n)

r : size of the each permutation

n : size of set from which elementsare permuted

! : factorial operator

 Question :

In a box, there are 5 black pens, 3 white pens and 4 red pens. In how many ways can 2 black pens, 2 white pens and2 red pens can be chosen?

Solution :

No of ways of choosing 2 black pens from 5 black pens

5C2=5P2/2!=5*4/1*2=10

No of ways of choosing 2 white pens from 3 white pens

3C2=3P2/2!=3*2/1*2=3

No of ways of choosing 2 red pens from 4 red pens

4C2=4P2/2!=4*1/1*2=6

Therefore, it can be chosen by 10*3*6=180 ways

Addition principle

 

If we have a ways of doing something and b ways of doing another thing and can not do both at the same time, then there are a + b ways to choose one of the actions.

 

Example

A woman has decided to shop at one store today, either in the north part of town or the south part of town. If she visits the north part of town, she either shop at a mall, a furniture store, or a jewelry store (3 ways). If she visits the south part of town, then she either shop at a clothing store or a shoe store (2 ways).

 

There are 3+2=5 possible shops the woman could end up shopping at today.

 

 

Multiplication Principle

 

If there are a ways of doing something and b ways of doing another thing, then  a · b ways of  doing both actions.

 

Example

 

When you order pizza, first choose the type of crust: thin or deep dish (2 choices). Next, choose the topping: cheese, pepperoni, or sausage (3 choices).

 

Using the rule of product, you know that there are 2 × 3 = 6 possible combinations of ordering a pizza.

 

 

Example 2

How many different license plates can be made if each plate contains a sequence of three

uppercase English letters followed by three digits?

 

There are 26 choices for each of the three uppercase English letters and ten choices for
each of the three digits. There are a total of 26 • 26 • 26 • 10 • 10 • 10 = 17,576,000 possible license plates.

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

a) Euler Path

     -Euler Path is a path in the graph that passes each edge only once.

       Example:

 

 

    b) Euler Circuit

     -Euler Circut is a path in the graph that passes each edge only once and return back to its original position.

Example :

 

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

         -Degree of Nodes: Number of Edges on a vertex

          -Euler Path existence: not have more than 2 vertices of odd-degree nodes exist in the graph.

          -Euler Circuit existence: no odd-degree nodes exist in the graph.

 

3) What are the algorithm or step by step to determine (a) and (b) in    Question 1

        -Choose a random vertex

        -Pick an arbitrary edge joined to another vertex and mark the edge.

       -Marked edges cannot be passed again. The above procedure is repeated until all edges are  covered.

 

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

           a) Hamilton Path

                -A path visits each vertex of a graph once and only once.

            Example :

 

           

  b) Hamilton Circuit

                  -Hamilton circuit is a cycle in an undirected graph which visits each vertex exactly once and   also returns to the starting vertex.

Example :

 

 

Question 5.

Hamilton Path – a simple path that passes  through EVERY VERTEX ONCE.

Hamilton Circuit – a simple circuit that passes through EVERY VERTEX EXACTLY ONCE.

 

Question 6.

Nearest Neighbor Algorithm

 1. Choose a starting vertex. (Let take D as starting vertex)

2. The next vertex chosen is the one “nearest” (smallest weight) that has not been visited.  If tie choose one.  Mark the edges covered as they are added to the path.

3. If all vertices have not been visited then repeat step 2 otherwise return to the start.   

     

 

4. a) Hamilton Path  is  a  simple path in a graph that passes

        through every vertex exactly once.

 

Example:

G₁ has a Hamilton path, a, b, c, d

 

 

b) Hamilton Circuit  is a simple circuit in a graph that passes    through every vertex exactly once.

 

Example:

G₂ has a Hamilton circuit: a, b, c, d, e, a

 

 

Graph Theory

1. a) An Euler path is a trail in a graph which visits every edge exactly once.

 

Example:

The graph G₁ has an Euler path, a, c, d, e, b, d, a, b.

 

 

 

 

 

 

 

 

 

 

 

b) An Euler circuit is a trail which starts and ends on the

     same vertex.

 

Example:

The graph G₂ has an Euler circuit, a, e, c, d, e, b, a.

 

 

What do you show in the basis step and what do you show in the inductive step when you use (ordinary) mathematical induction to prove that a property involving an integer n is true for all integers greater than or equal to some initial integer?

• Basis step
• Show that p(n) is true
• Inductive step
• Show that any integer k greater or equal n0, if P(k) is true, then P(k+1) is true

Example

• Prove that for any natural number n,   0 + 1 + ... + n = n( n + 1 )/2
• Basis step:
• If n = 0, then LHS = 0, RHS = 0 * (0+1) = 0
• LHS (0) = RHS (0)

• Inductive step:
• LHS à n + 1 = 0 + 1 + … + n + (n + 1) = (0 + 1 + … + n) + (n + 1)
• n(n + 1)/2 + (n + 1) – using induction hypothesis
• (n + 1)(n + 2)/2 – factoring (n + 1)
• LHS = RHS for n + 1

What is the inductive hypothesis in a proof by (ordinary) mathematical induction?

• Inductive hypothesis is the assumption in inductive step that statement hold for some n.

• In order to perform the inductive step, one must assumes the inductive hypothesis and then uses this assumption to prove the statement for n + 1.

• Inductive hypothesis indicates in three ways:
• by explicit mention in the text
• by inserting acronym IH over an equal sign or a sign for an inequality
• by specify the inductive hypothesis as the reason for a step in a multi-line display

Use (ordinary) mathematical induction to construct proofs involving various kinds of statements such as formulas, divisibility properties and inequalities

Formulas:

Show that if n is a positive integer,

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

Solution:

Let P(n) be the proposition that the sum of the first n positive integers, 1+2+…+n=n(n+1)/2. We must do two things to prove that P(n) is true for n = 1, 2, 3, . . .

Show that P(1) is true and that the conditional statement P(k) implies P(k + 1) is true for k = 1, 2, 3,…..

BASIS STEP:

P(1) is true, because 1 =  1(1+1)
                                                 2

INDUCTIVE STEP:

1 + 2+· · ·+k =  k(k+1)
                               2

Show that P(k + 1) is true,

1 + 2+· · ·+k + (k + 1) = (k+1)[(k+1)+1]
                                                    2
                                         
                                     = (k+1)(k+2)
                                                2

Add k + 1 to both sides of the equation in P(k),

1+2+....+k+(k + 1)= k(k+1)
                                   2       +(k+1)
                            

                            = k(k+1)+2(k+1)
                                         2
                            = (k+2)(k+1)
                                       2

This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step. We have completed the basis step and the inductive step, so by mathematical induction we know that P(n) is true for all positive integers n.

 1 + 2+· · ·+n =n(n + 1)/2 for all positive integers n have proven.

Divisibility properties

Proposition:

For any integer n≥1, 7ⁿ - 2ⁿ is divisible by 5.        

Proof :

1) Basis step:

The statement is true for n=1:                                                      

                                   7¹ – 2¹ = 7 - 2 = 5 is divisible by 5.

2) Inductive step:

Assume the statement is true for some k≥1                              

                                                            (inductive hypothesis) ;

P(k):                7^k - 2^k is divisible by 5.                                                 

            Then 7^k - 2^k = 5a   for some aÎZ .                                

 We need to show:

P(k+1):7^k+1 - 2^k+1 is divisible by 5.                                                                

             7^k+1 - 2^k+1 = 7·7^k - 2·2^k = 5·7^k + 2·7^k - 2·2^k

                                    = 5·7^k + 2·(7^k - 2^k)  =  5·7^k + 2·5a           

                                    = 5·(7^k + 2a) which is divisible by 5.                         

Show that it is true for k+1.                                                     

P(n) is true by induction.   

Inequalities

Theorem:

 For all integers n≥5,    n² < 2ⁿ.                         

Proof (by induction):

1) Basis step:

                        The statement is true for n=5:                             

                                                            5² =25 < 32 = 2⁵.

2)Inductive step:

Assume the statement is true for some k≥5 ;                        

P(k):                          k² < 2^k.                                              

We need to show:  

P(k+1):                 (k+1)² < 2^k+1.                                                              

             (k+1)² = k²+2k+1 < k² +2^k                

                                           < 2^k + 2^k                        

                                           = 2·2^k  = 2^k+1.

                                   

Show that it is true for k+1 .                                          

Thus, P(n) is true by induction.