DM-1- Combinatorics - Sum rule and Product rule

This lecture describes how to count sets using some simple rules called sum rule and product rule

[sandeepmandrawadkar]

Simplest and coolest way of teaching a topic considered to be horror to many. Hats off to you Sir. Unable to trace your name. Please let us know. A genius should never be hidden from the world.

[morningstar]

Outstanding teaching! Everything was understandable. Tysm sir

[shethnisarg]

Hey friends, I have made notes of this lecture and I am sharing it with you all:


S = S1 U S2 => |S| = |S1| + |S2| iff S1 int S2 = null set;

We have a task T and we know how to do it but what is unknown is total number of ways of doing it.
Product rule:
=> A person has 5 shirts and 5 pants, he knows how to wear the dress i.e first he will wear a shirt and then jeans, so the problem here is in how many ways can he wear the dress?
Ans. we break task T in smaller and smaller sub problems T1-->T2, -->Tn such that each of them is mutually independent then total number of ways of completing task T will be:
|T| = |T1|*|T2|*|T3|...|Tn|;
In this case task sequence of smaller sub problems will be: Ts (wear a shirt) --> Tj (wear a jeans)
so |T| = 5 * 5 = 25 ways he can wear dress
Note that here if he chooses the first shirt then on that shirt he can wear 5 jeans, now if he chooses the second shirt, then on that shirt also he can wear 5 jeans, so choosing different shirts does not affect the number of ways of wearing jeans, so this kind of tasks are known mutually independent tasks and we can apply product rule there.

Q. The number of binary sequences of length n?
A. let say n =3, then the task sequence here would be to fill the positon 1, then fill position 2, and then fill 3rd position, T1-->T2-->T3, and filling position 1 does not affect the filling of other positions so they are mutually independent, so we can apply the product rule here.
we can fill any position with 0 or 1. so no. of ways is 2.
So |T| = |T1|*|T2|*|T3|
= 2*2*2
=2^3.
for n, 2^n.

Q. The numbers between 0 - 9999 which contains exactly one 5?
A. Before solving the question, in order to understand the task sequence take a example and try to find the task sequence.
first of all we need 4 positions in order to form a number between 0-9999.
e.g. one such number is 4591, so first we write 5 in any one of the positions, and then fill the remaining 3 positions without 5,
so task sequence will be T5-->Tremaining 3 positions without 5.
now |T5| = 4 as we can fill 5 in either of position 1, 2, 3 or 4.
|Tremaining 3 positions without 5| = 9*9*9 as we can fill any one of those positions with 0, 1, 2, 3, 4, 6, 7, 8, 9. and we have 3 such positions, (not 4 positions, as one position will be filled with 5).
so |T| = 4*9*9*9.

Q. n couples are invited for the party with the condition that every husband accompanied by his wife. However a wife need not to be accompanied by her husband. The number of different gatherings at the party is?
A. Now lets take an example of couple, X, Y. where x is husband and y is wife, then the possibilites for one gathering will be:
1. if x wants to go, y must come with him
2. y can go alone.
3. none of x and y go to party.
so one gathering can be done in 3 ways.

here task sequence is do the gatherings at the party,
so |T| = 3*3*3...n times
= 3^n.
Q. numbers between 0 - 9999 which contain exactly one 5 and one 6?
A. there will be 4 positions to form a number between 0 - 9999.
here task sequence will be fill any one position with 5, --T5
fill position other than that with 6 -- T6.
And fill the remaining positions other than above 2 with the numbers except 5 and 6 -- Tr.

SO, |T5| = 4, as we can fill 5 in any one of the positions.
|T6| = 3 as we can fill 6 any 3 positions as one position is filled with 5.
|Tr| = 8*8 as we can fill one of the remaining position with 0, 1, 2, 3, 4, 7, 8, 9 and we have 2 such positions.

|T| = 4*3*8^2.

Q. Numbers of palindromes of length 7 with english alphabets?
A. So, here we have 7 positions.
Task sequence will go like this:
fill the first position with english alphabet. T1.
fill the seventh position with the same letter as first position. T7.
fill the second position with english alphabet. T2.
fill the sixth position with the same letter as second position. T6.
fill the third position with english alphabet. T3.
fill the fifth position with the same letter as third position. T5.
fill the fourth position with english alphabet. T4.

|T1| = |T2| = |T3| = |T4| = 26 as we can fill them with a, b, c..z
|T7| = |T6| = |T5| = 1 as they have to be filled with the same letter as T1, T2, T3 resp.
so,
|T| = 26*26*26*26*1*1*1
= 26^4.

[ShashankKomuroju]

Kiran
I'm glad you put your vids online.
I took these classes in Gate Forum in live.
I'm listening them again here :)

[Rohittt]

Sir, I was aware of sql queries but it was tough for me to form query if randomly problems/conditions are given to me.But when I attended your DBMS lectures at institute I got to know how to form queries in simple way from Relational algebra to SQL queries.By using this way, now I am able to make any query very quickly. Thank you so much, Sir. You made my life simpler. Hope this combinatorics will also be that much simpler.

[bhagavathyr]

Really helpful to understand from the basics. I am an MCA student, very useful for clearing Discrete Maths paper. Thank you. You are an inspiration for teaching Maths.

[vinayaksuresh]

Truly, you are an amazing teacher!
I wish I could attend your DBMS classes again!

[ABHISHEKKUMAR-nsom]

Sir, I love your way of teacing that too on traditional white board... which is really good and easy to follow....

[AshwiniManoj]

Sir, i was one of your many students and i know you wont remember me. You are an amazing teacher!!! I wish to be as intelligent and insightful as you one day :)

[sruthigopi]

Finally I got examples which I want.. . .thank u so much

[zafarhussain]

Thank you Sir .. for such a productive contents 🙏

[amaanahmad]

sir you're great and extraordinary and yeah please please please please keep teaching like that

[nishanisha]

U lecture was amazing
Isn't it ☺️

[nikhilprasad]

I will remember your teachings sir.... RAJU, RANI AND VANI....

[aasawarisahasrabuddhe]

sir, your videos are amazing n I request for more lectures for other subjects esp operating system.

[NikhilVerma-jkng]

Is this complete set of DM is fine for gates preparation ?

[RAVIKUMAR-rziz]

Really outstanding explanation..thanks sir...

[Adityarksht]

Generating functions and recurrence relations are not covered in these lectures. In 2017 a question of generating function came and in 2016 a question of recurrence relations appeared.

[AdeelKhan-jsnu]

Where can i get handwritten notes forthese lectures

[mitaligupta]

really helpfull videos ..thanks alot sir