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