TASK 7

#Additional Principle

Def: If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 is the same of the set of n2 ways, then there are n1+n2 ways to do the task.

n1≠n2

Hence,

                P =          n1 + n2

Examples:

1.                   Ahmad needs to deliver a parcel from KT to KL.

2.                   Suppose variable names in a programming language can be either a single uppercase letter or an uppercase letter followed by a digit. Find the number of possible variable names.

Solution: Use additional & Multiplication Principle

 26 + 26 .10 = 286

#Multiplication Principle

1.                  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:

Jersi                 : Kelantan, Terengganu

Colour             : red, white

Brand shoes    : ADIDAS, NIKE, BATA

How many total choices?

You  can show in a “tree”diagram:

You can count choices too:

2 x 2 x 3 = 12

#Permutation Definition

Factorial: The product of first n natural numbers can be denoted in the form n! (or) which is read as "n-Factorial"

Permutation Formula

Theorem 1: Permutations of n Objects

The number of permutations of n objects, denoted by Pn,n , is given by

Pn,n  =  n . (n-1). ……. . 1 = n!

Theorem 2: The above permutation can be expressed using factorial notation as follows.

P (n, r) = ⁿP_r = n (n-1) (n-2) . . . . . . . . (n - r + 1)         1 ≤ r ≤ n

            OR

P (n, r) = ⁿP_r =              0 ≤ r ≤ n

                

Example

Question 1 :

 Find the value of ⁵P₃

Solution: 

⁵P₃ = 5. 4. 3 = 60

Question 2 :

 In how many ways three digits numbers can be formed using the digits, 3, 4, 5, 7 and 9.
Solution: 

We have 5 digits, 3, 4, ,5, 7 and 9.
The number of three digit numbers that can be formed is permutation of five things taken three at a time.

 ₅P₃

 = 5 (5 – 1) (5 - 2)  [ by Formula , ⁿP_r = n (n-1) (n-2) . . . . . . (n - r + 1)]
 = 5.4.3 
 = 60

There will be 60 three digit numbers that can be formed.

#Combination

Example : Consider the set S = {1,2,3,4,5}

The set {2,5} is a 2-combination of S

There are 10 different 2-combinations of S.They are:

{1,2} , {1,3} , {1,4} , {1,5},

{2,3} , {2,4} , {2,5}

{3,4} , {3,5},

{4,5}

Formula for the number of r-combination

Combination:Examples

 Combination :An identity

We can also give a combinatorial proof that is used to prove that both sides of the identity count the same objects but in different ways or a proof that is based on showing that there is a bijection between the sets of objects counted by the two sides of the identity.

Conclusion: Any two finite sets having a bijection between them must have exactly same number of elements.

#THE PIGEONHOLE PRINCIPLE 

If k is a positive integer and k + 1 or more objects

are placed into k boxes, then there is at least one box containing two or more of the objects.

Example:In any group of 27 English words, there must be at least two that begin with the same letter, because there are 26 letters in the English alphabet.

THE GENERALIZED PIGEONHOLE PRINCIPLE 

If N objects are placed into k

boxes, then there is at least one box containing at least éN/kùobjects .

Example:A bowl contains 10 red and 10 yellow balls. How many balls must be selected to ensure 3 balls of the same color?

Solution:

Via generalized pigeonhole principle

How many balls are required if there are 2 colors, and one color must have 3 balls?

number of boxes: k = 2

We want  éN/kù = 3

What is the minimum N?

N = 5

task 6

EULER PATH	EULER CIRCUITS
Definition : A path in a multigraph that includes exactly once all the edges and has different first and last vertices.	Definition : A circuit that includes exactly once all the edges and has same initial and end vertex.
Example : Different start and ending points. Edges: A: 2    B: 5   C: 3   D:4   E: 2 All even degree except two with odd degree Properties : all vertices have even degree edges and 2 vertices have odd degree of edges.	Example : Same starting and ending points Edges: A: 2   B: 6   C: 4   D: 4   E: 2 All have even degree Properties : all vertices have even degree of edges.

Fluery’s algorithm

To find an Euler path or an Euler circuit:

            1.         Make sure the graph has either 0 or 2 odd vertices.

     2. If there are 0 odd vertices, start anywhere. If there are 2

         odd vertices, start at one of them.

     3. Follow edges one at a time. If you have a choice between

        a bridge and a non-bridge,(always choose the non-bridge).

     4. Stop when you run out of edges.

Hamilton Path

-a path that includes each vertex of the graph once and only once.

Example of Hamilton Path                                                     

                                                     

 

Hamilton Circuit

-a circuit that include each vertex of the graph once and only once.(at the end,the circuit must return to the starting vertex).

Example of Hamilton Circuit

                                       

                                   

Properties that differentiate between Hamilton path and Hamilton Circuit

Hamilton Path	Hamilton Circuit
A simple path in a graph G that passes through every vertex exactly once.	A simple circuit in a graph G that passes through every vertex exactly once except begin/end vertex
Hamilton Path ⇒Hamilton Circuit	Hamilton circuit →Hamilton path
Begin and end vertex always be different	Begin and end vertex must be same
Example: (1,2,3,4,5,6,7,8,9,1)-Hamilton Path	Example: (1,2,3,4,5,6,7,8,9,1)-Hamilton Circuit
	-A graph with a vertex of degree one cannot have a Hamilton circuit. -If a vertex in a graph has degree two, then both edges that are incident to this vertex must be part of any Hamilton circuit.
	Once a vertex is part of the Hamilton circuit ,all other edges of that vertex can be removed
	A Hamilton circuit cannot contain a smaller circuit within it.

algorithm or step by step to determine Hamilton Path and Hamilton Circuit


To determine existence of Hamilton circuit and Hamilton path is

1.  Graph with a vertex of degree one cannot have a Hamilton circuit, because in a    Hamilton      circuit,   each vertex is incident with two edges in the circuit.
2.  If a vertex in the graph has degree two, then both edges that are incident with this vertex must be part of any Hamilton circuit.
3. DIRAC’S Teorem - If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit.
4.  If G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit.