Notes
Bijective proof: convert that counting problem into a easy problem by putting them into a 1:1
correspondence
For easy problem number of solution is n
and there is 1:1 correspondence
sol 1=sol1
if we can create a bijection then number of solutions of hard problem=number of solutions of
easy problem.
Eg:
Problem 1: select one person
Problem 2: reject three person
There is 1:1 correspondence.
If you select a: solution for problem 1.
Similar solution = bcd
solution of problem 2: a
No
Acd is
So b will be solution for problem 1
I can say that every solution in problem 1 will have a unique image in problem 2
Whatever solution you take in problem 2 then this will have exactly one mapping in problem 1
If we have answer for problem 2 then we have answer for problem 1
Which of them is easier?
Counting bit strings
These 2 problems are actually similar.
Set (4)
How many subset i can create from this set?
I will create subsets and another problem
Problem 1: subset problem
Problem 2: 4 length bit string
Problem 2 has 1:1 correspondence with problem 1
Set order does not matter so i can fix order
I am fixing order abc
12345 fixed
And i create subset
Then i will not write 21
It is subset but the order isn’t same here so i will write like this:
12 is a subset
So if fix order:
Subset can think as 1100
We have taken a,b and not taken c,d
Fixing the order because order does not matter in set.
We will get unique string.
If i get a string then we will get a unique subset
Number of subsets possible of size four=number of four length bit string=2power4.
Whenever order doesn’t matter we can fix the order.
Distribution objects into boxes
Objects: abcd
And we have two boxes
Dodb.
So how many ways we have?
For every object either they can go to b1 or b2
For every object either they can go to b1 or b2
So for every object we have 2 choices
2 power 4
In this problem what matters?
I will take identical objects but boxes are different.
Now only number will matter. Identical objects but boxes are different.
Identical objects but different boxes:
Only number matters, what number you are putting to b1.
But in non-identical both number and which element matters.
Next:
DOIB
Objects are different but boxes are identical.
Because our boxes are same these two things become same.
Friends going on a trip and these R are rooms in a hotel.
This means ab are together cd are together.
dc cd is also same because this is distribution and in distribution order doesn’t matter.
Order of element doesn’t matter when you are putting objects into boxes.
a bcd
b acd
are different
because a is alone and b is alone.
in this scenario a will die and in other scenario b will die.
IOIB
Identical objects identical boxes
In this situation both are same.
a | aaa is same ss aaa | a because objects and boxes are same.
Now nothing else is possible.
DODB:
Most simple template
Normal product rule with combination
We have total 52 cards
4 boxes
Trash
To trash we are giving 32 cards
Can i say order matters when giving 5 cards to A?
No.
5 cards AAAAA
5 cards consider BBBBB
because order doesn’t matter
So every card i can mark A..
Note: DODB most common mistake.
Total elements: ABCDEF
Total Boxes: 3
I want to give 2 items to each.
What is wrong with this logic? From 3 people i select one person to whom i give two elements
From three people i select on person to whom i give two elements
From the remaining 2 people i select one person i give 2 elements
Most common mistake in DODB.
What is mistake? Overcounting:
XYZ
This case we have counted
1. Way 1: from three people we are selecting one person (select X and give two cards)
2. From remaining ZY, we choose Z and give 2 cards
3. From Y we are giving 2 cards
Count 2: Z, give cards
From rem 2 people i can select one person 2 cards
We have counted this case 3! Times
These distributions are same.