If the first task can be completed in M different ways and the second in N different ways, and if these cannot be performed simultaneously, then there are M + N ways of doing either task.

**Fundamental principles of counting**

**1. The Sum Rule**: Let us
consider two tasks which need to be completed. If the first task can be
completed in M different ways and the second in N different ways, and if these
cannot be performed simultaneously, then there are M + N ways of doing either
task. This is the sum rule of counting.

**2. The Product Rule: ** Let us suppose
that a task comprises of two procedures. If the first procedure can be
completed in M different ways and the second procedure can be done in N
different ways after the first procedure is done, then the total number of ways
of completing the task is M × N

**3. The Inclusion-Exclusion Principle:** Suppose two tasks A and B can be
performed simultaneously. Let n(A) and n(B) represent the number of ways of
performing the tasks A and B independent of each other. Also let n(A ∩ B) be
the number of ways of performing the two tasks simultaneously. We cannot use
the sum rule to count the number of ways of performing one of the tasks as that
would lead to over counting. To obtain the correct number of ways we add the
number of ways of performing each of the two tasks and then subtract the number
of ways of doing both tasks simultaneously. This method is referred to as the
principle of inclusion - exclusion. Using the notation of set theory we write
it as

n(A ∪ B) = n(A) + n(B) − n(A ∩ B).

Suppose we have to find the
number of positive integers divisible by 2 or 7 (but not both), upto 1000. Let
n(A) denote the number of integers divisible by 2, n(B) denote the number of
integers divisible by 7 and n(A ∩ B) the number of integers divisible by both 2
and 7. Then the number of positive integers divisible by 2 or 7 is given by

n(A ∪ B) = n(A) + n(B) − n(A ∩ B) = 500 + 142 − 71 = 571.

(Note that n(A) will include all
multiples of 2 upto 1000, n(B) will include all multiples of 7 upto 1000 and so
on.)

**Tree Diagrams:** Tree diagrams are often helpful in representing the
possibilities in a counting problem. Typically in a tree the branches represent
the various possibilities. For example, suppose a person wants to buy a Car for
the family. There are two different branded cars and five colours are available
for each brand. Each colour will have three different variant on it namely
GL,SS,SL. Then the various choices for choosing a car can be represented
through a tree diagram as follows:

Another concept which is an
essential tool in a counting process which is stated as follows:

In order to understand the
Permutation and Combinations we need a concept called “Factorials” which will
be discussed in the next section.

Tags : Solved Example Problems, Exercise | Mathematics , 11th Mathematics : UNIT 4 : Combinatorics and Mathematical Induction

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

11th Mathematics : UNIT 4 : Combinatorics and Mathematical Induction : Fundamental principles of counting | Solved Example Problems, Exercise | Mathematics

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.