Monday 20 May 2013

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) = nPr = n (n-1) (n-2) . . . . . . . . (n - r + 1)         1 ≤ r ≤ n

            OR
P (n, r) = nPr =              0 ≤ r ≤ n
                
Example
Question 1 :
 Find the value of 5P3
Solution: 
5P3 = 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.

 5P3
 = 5 (5 – 1) (5 - 2)  [ by Formula , nPr = 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