Discrete Mathematics Counting Theory - Discrete Mathematics

What is Discrete Mathematics Counting Theory?

It is essential to understand the number of all possible outcomes for a series of events. The different ways in which 10 lettered PAN numbers can be generated in such a way that the first five letters are capital alphabets and the next four are digits and the last is again a capital letter. This can be calculated by using the mathematical theory of Counting. The fundamental counting rule, permutation rule and the combination rule is used by Counting.

What are the rules of Sum and Product?

In order to decompose the difficult counting problems into simple problems the Rule of Sum and The Rule of Product is used.

The Rule of Sum − If a sequence of taskscan be done inwaysrespectively, then the number of ways to do one of these tasks is

When two disjoint tasks are considered such as A and B then mathematically, |A∪B|=|A|+|B||A∪B|=|A|+|B|.

The Rule of Product − If a sequence of taskscan be done inways respectively and every task arrives after the occurrence of the previous task, then there areways for performing the tasks.

Mathematically, if a task B arrives after a task A, then |A×B|=|A|×|B|

Example

Question – A boy living at X want to go to school which is at Z, for which he first has to reach Y and they from Y to Z. The X to Y route has 3 bus routes and 2 train routes. From Y to Z there are 4 bus routes or 5 train routes. Calculate the number of ways to go from X to Z?

Solution − From X to Y, he can go in 3+2=53+2=5 ways (Rule of Sum). Thereafter, he can go Y to Z in 4+5=94+5=9 ways (Rule of Sum). Hence from X to Z he can go in 5×9=455×9=45 ways (Rule of Product).

What are Permutations?

An arrangement of some of the elements or an ordered combination of elements is known as permutation.

Examples

  • From a set S ={x, y, z} by taking two at a time, all permutations are −xy,yx,xz,zx,yz,zy.
  • A permutation of three digit numbers from he set of numbers S={1,2,3} can be as - 123, 132, 213, 231, 312, 321

Number of Permutations

The number of permutations of ‘n’ different things taken ‘r’ at a time is denoted byPr

npr

where n!=1.2.3.…(n−1).n

Proof − Let there be ‘n’ different elements.

The first place can be filled in n number of ways. Once the first place is filled, (n-1) number of elements is left and the second place can be filled by (n-1) ways. Respectively the third place can be filled in (n-2) number of ways. Hence generalize the number of ways to fill up the r-th place as [n – (r–1)] = n–r+1

So, the total no. of ways to fill up from first place up to r-th-place −

nPr=n(n−1)(n−2).....(n−r+1)

=[n(n−1)(n−2)...(n−r+1)][(n−r)(n−r−1)…3.2.1]/[(n−r)(n−r−1)…3.2.1

Hence,

nPr=n!/(n−r)!

What are the important formulas of permutation?

Some important formulas of permutations are as follows:

  • If there are n elements of whicha1are of some kind, a2are of another kind; a3 are alike of third kind and so on and ar are of rth kind, where

then, number of permutations of these n objects is

  • Number of permutations of n distinct elements taking n elements at a time =
  • The number of permutations of n dissimilar elements taking r elements at a time, when x particular things always occupy definite places =
  • The number of permutations of n dissimilar elements when r specified things always come together is − r!(n−r+1)!
  • The number of permutations of n dissimilar elements when r specified things never come together is − n!–[r!(n−r+1)!]
  • The number of circular permutations of n different elements taken x elements at time =px/x
  • The number of circular permutations of n different things =pn/n

List out some of the illustration problems on permutations.

Problem 1 – In how many ways a bunch of 6 different cards can be permutated?

Solution − As 6 cards are taken at a time from a deck of 6 cards, the permutation will be


6
P

Problem 2 – In how many different ways the letters of the word 'READER' can be arranged?

Solution − There are 6 letters word (2 E, 1 A, 1D and 2R.) in the word 'READER'.

The permutation will be =6!/[(2!)(1!)(1!)(2!)]=180.

Problem 3 – In how many permutations can the word ‘ORANGE’ is arranged in such a manner that the even positions are occupied by the consonants?

Solution – The word ORANGE has three vowels and 3 consonants. The consonants can be arranged among themselves in

The 3 vowels fill the remaining 3 places in

The total number of permutations is 6×6=36.

What are Combinations?

The selection of some of the given elements by not considering the order is known as a combination.

The number of all combinations of n things, taken r at a time is −

Problem 1

Find the number of subsets of the set {1,2,3,4,5,6} having 3 elements.

Solution

The cardinality of the set is 6. As the ordering does not matter, the number of subsets is

Problem 2

Out of 6 men and 5 women in a room, in how many ways can be 3 men and 2 women chosen?

Solution

3 men from 6 men can be chosen in

ways

and 2 women from 5 can be chosen in

ways

Hence, the total number of ways is

Problem 3

From a total number of 9 students, in how many ways can 3 distinct group of 3 students can be chosen?

Solution

The groups are numbered as 1, 2 and 3

The number of ways 3 students can be chosen for the first group is

The number of ways 3 students can be chosen for second group after selecting the first group is

ways.

The number of ways 3 students can be chosen for third group after selecting the first and second group is

ways.

Hence, the total number of ways is -

What is Pascal's Identity?

The number of ways in which k elements can be chosen from n elements is equal to the summation of the ways for choosing (k-1) elements from (n-1) elements and the number of ways to choose elements from n-1 elements.

Mathematically, for any positive integer’s k and n:

Proof

What is Pigeonhole Principle?

If there are fewer pigeon holes than the total number of pigeons and when each pigeon is put in a pigeon home, one pigeon hole sould be more than the pigeon.

In 1834, German mathematician, Peter Gustav Lejeune Dirichlet, stated a principle which he called the drawer principle. Now, it is known as the pigeonhole principle. If n pigeons are put into m pigeonholes where n > m, there's a hole with more than one pigeon.

Example

  • In a class of 30 there must be at least two people whose names start with the same alphabet.

What is the Inclusion-Exclusion principle?

The cardinal number of the union of multiple non-disjoint sets is known as Inclusion-exclusion principle. The principle states for two sets A and B are:

|A∪B|=|A|+|B|−|A∩B|

For three sets A, B and C, the principle states −

|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|

The generalized formula -

Problem 1

From 1 to 50 how many are the multiples of 2 or 3 but not the multiples of both?

Solution

From 1 to 100, there are 50/2=2550/2=25 numbers which are multiples of 2.

There are 50/3=1650/3=16 numbers which are multiples of 3.

There are 50/6=850/6=8 numbers which are multiples of both 2 and 3.

So, |A|=25, |B|=16 and |A∩B|=8.

|A∪B|=|A|+|B|−|A∩B|=25+16−8=33

Problem 2

24 students out of 50 students like cold drinks, 36 like hot drinks and each of them like at least one of the two. How many like both?

Solution

Let X be the set of students who like cold drinks and Y be the set of people who like hot drinks.

So, |X∪Y|=50, |X|=24, |Y|=36

|X∩Y|=|X|+|Y|−|X∪Y|=24+36−50=60−50=10

10 students like both Tea and coffee.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics