i) Describe each of the basic principles in counting:
-Explain
the Multiplication Principle and give 1 example question with solution for this
principle
def: 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 -1: A college offers 7 courses in the morning and 5
in the evening. Find the possible number of choices with the student if he
wants to study one course in the morning and one in the evening.
Solution: The student has seven choices from the morning
courses out of which he can select one course in 7 ways.
For the evening course, he has 5 choices out of which he can
select one in 5 ways.
Hence the total number of ways in which he can make the
choice of one course in the morning and one in the evening = 7 × 5 = 35.
-Explain
the Addition Principle and give 1 example question with solution for this
principle
Def: If one experiment has n possible outcomes and another
has m possible outcomes, then there are (m + n) possible outcomes when exactly
one of these experiments is performed.
In other words, if a
job can be done by n different methods and for the first method there are a1
ways, for the second method there are a2 ways and so on . . . for the nth
method, an ways, then the number of ways to get the job done is (a1 + a2 + ...
+ an).
Example : A college
offers 7 courses in the morning and 5 in the evening. Find the number of ways a
student can select exactly one course, either in the morning or in the evening.
Solution: The student
has seven choices from the morning courses out of which he can select one
course in 7 ways.
For the evening course, he has 5 choices out of which he can
select one course in 5 ways.
Hence he has total number of 7 + 5 = 12 choices.
Example:
-4+9x+4 > -10x+7
Solution:
Combine like-terms on the left side:
9x > -10x+7
Add 10x to both sides:
9x+10x > -10x+7+10x
19x > 7
Divide both sides by 19:
19x/19 > 7/19
x > 7/19
ii)Permutation
-give a definition, formula and 1 example question with solution
def: An arrangement is called a Permutation. It is the
rearrangement of objects or symbols into distinguishable sequences. When we set
things in order, we say we have made an arrangement. When we change the order,
we say we have changed the arrangement. So each of the arrangement that can be
made by taking some or all of a number of things is known as Permutation.
Formula:
Example:
It is required to
seat 5 men and 4 women in a row so that the women occupy the even places. How
many such arrangements are possible?
Solution:
We are given that there are 5 men and 4 women.
(i. e) there are 9 positions.
The even positions are , 2nd, 4th, 6th and the 8th places
These four places can be occupied by 4 women in P(4, 4) ways
= 4 !
= 4 . 3. 2. 1
= 24 ways
The remaining 5 positions can be occupied by 5 men in P(5,5)
= 5!
= 5.4.3.2.1
= 120 ways
Therefore, by the Fundamental Counting Principle,
Total number of ways of seating arrangements = 24 x 120
= 2880
iii)Combination
- give a definition, formula and 1 example question with solution
def: A Combination is a selection of some or all of a number
of different objects. It is an un-ordered collection of unique sizes.In a
permutation the order of occurence of the objects or the arrangement is
important but in combination the order of occurence of the objects is not
important.
Formula:
n = the number of objects to choose from
k = the number of objects selected
Example:
The number of
possible combinations with repetition of
objects from is
solution
iv)
Pigeon Hole Principle - give a definition, formula and 1 example question with
solution.
def:
The pigeonhole principle is one of the most used tools in
combinatorics, and one
of the simplest ones. It is applied frequently in graph
theory, enumerative combinatorics
and combinatorial geometry. Its applications reach other
areas of mathematics,
like number theory and analysis, among others. In olympiad
combinatorics
problems, using this principle is a golden rule and one must
always be looking for
a way to apply it.
Formula:
The statement above is a direct consequence of the
Pigeonhole Principle:
(1) If m
pigeons are put into m pigeonholes, there is an empty hole iff there's a hole
with more than one pigeon.
Variously known as the Dirichlet Principle, the statement
admits an equivalent formulation:
(2) If n >
m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.
A more formal statement is also available:
(3) Let |A|
denote the number of elements in a finite set A. For two finite sets A and B,
there exists a 1-1 correspondence f: A->B iff |A| = |B|.
Example:
Consider a chess board with two of the diagonally opposite
corners removed. Is it possible to cover the board with pieces of domino whose
size is exactly two board squares?
Solution
No, it's not possible. Two diagonally opposite squares on a
chess board are of the same color. Therefore, when these are removed, the
number of squares of one color exceeds by 2 the number of squares of another
color. However, every piece of domino covers exactly two squares and these are
of different colors. Every placement of domino pieces establishes a 1-1
correspondence between the set of white squares and the set of black squares.
If the two sets have different number of elements, then, by the Pigeonhole
Principle, no 1-1 correspondence between the two sets is possible.
