Combining
Principle:
DEFINITION
•
Using
both multiplication and addition principle in solving a complicated counting
problems.
•
Mostly
used to solved problem in programming.
Example 1
•
The
name of a variable is a string of one or two alphanumeric characters, where
uppercase and lowercase letters are not distinguished. (An alphanumeric
character is either one of the 26 English letters or one of the 10 digits.)
Moreover, a variable name must begin with a letter and must be different
from the five strings of two characters that are reserved for programming use.
How many different variable names are there in this version of BASIC?
•
Solution:
Let V equal the number of different variable names in this version of BASIC.
Let V1 be the number of these that are one character long and V2 be the
number of these that are two characters long. Then by the sum rule, V =
V1 + V2. Note that V1 = 26, because a one-character variable name must be a
letter. Furthermore, by the product rule there are 26 · 36 strings of length
two that begin with a letter and end with an alphanumeric character. However,
five of these are excluded, so V2 = 26 · 36 − 5 = 931. Hence, there are V =
V1 + V2 = 26 + 931 = 957 different names for variables in this version of
BASIC.
Permutation:
DEFINITION
² A permutation of a set of distinct object
is an ordered arrangement of these objects.
² r-permutation is an ordered arrangement of r element
of a set.
² The number of r-permutation of a set
with n elements is denoted by P(n ,r).
FORMULA
The number
of r-permutation of a set with n distinct elements:-
P(n ,r) = n (n - 1) (n - 2)…..(n –
r + 1)
Note: P(n
,n)=n!
P(n ,0)=1
EXAMPLE
1
How many
ways are there to select a 1st prize winner, a 2nd prize,
and a 3rd prize winner from 100 different people who have entered a
contest?
Solution:
n=100, r=3
P(100,3)= 100(100-1)(100-2)
=100(99)(98)
=970200
Combinations:
DEFINITION
The number of
subsets of size r (or r-combinations) that can be chosen from a set of n elements
(
), is
given by the formula
C(n, r) = P(n, r)/P(r, r)
= n!/(n – r)!/(r!/(r – r)!)
= n!/(r!(n – r)!)
where n and r are nonnegative integer with r≤n.
EXAMPLE 1:
Suppose the group of twelve consists of
five men and seven women.
How many five-person teams can be chosen
that consist of three men and two women?
Solution:
To answer this question, think of
forming a team as a two-step process:
Step 1:Choose the men.
Step 2:Choose the women.
There are (
)ways to
choose the three men out of the five and (
)ways to
choose the two women out of the seven. Hence, by the product rule,
Permutation (Ordered Selection) vs
Combination (Unordered Selection)
In an ordered
selection (Permutation), it is not only what elements that are chosen but also
takes account in the order of the particular items chosen.
In an unordered
selection (Combination), it is only the identity of the chosen element that
matters.
The Pigeonhole
Principle:
DEFINITION
A function from one finite set to a smaller
finite set cannot be one-to-one: There must be a least two elements in the
domain that have the same image in the co-domain.
EXAMPLE 1:
If there are 11 players in a soccer team
that wins 12-0, there must be at least one player in the team who scored at
least twice.
GENERALISED PIGEONHOLE PRINCIPLE:
For any function f from a finite set X with
n elements to a finite set Y with m elements and for any positive integer k, if
k<n/m, then there is some y∈Y such that y is the image of at leastk+1
distinct elements of X.
EXAMPLE 1:
In our 60-student class, at least 12
students will get the same letter grade (A, B, C, D, or F).
No comments:
Post a Comment