COUNTING

                                                                  
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.

 -Explain the combining principle (multiplication &addition) and give 1 example question with solution for this principle

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.