#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:
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.
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
= 5.4.3
= 60
#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