Basics of Discrete Mathematics
In this article, we will be discussing some basic things about Discrete mathematics, so let’s start.
The whole article will be more like a conversation between two friends, the article will revolve around two friends Cyra and Rahul.
Cyra is very good at mathematics and logic building. She will ask questions to Rahul and will teach Rahul in the whole article.
Cyra: Rahul, have you solved Rubik’s Cube yet?🤔
Rahul: No, why are you asking this?
Cyra: Can you solve it, without knowing the Algorithms of solving it?
Rahul: I think, I can, by exhausting all possible configurations…
Cyra: So, if you are going to exhaust all possible configurations of 3 X 3 Rubik’s cube then you must live more than the age of the Universe.😂 Interesting isn't it. let me ask you something else…
Cyra: If you have given a very large sheet of paper, what you have to do is, to tear it in two halves then gathering them, again tearing them in two halves and repeating it, you have to do it 40 times, how much will be the height of the pile of paper at the end?
Think of it…
Rahul: I don’t know, maybe somewhat like the size of my iPhone screen…
Cyra: Let me tell you it will be that much, if you will stand on it, you will be able to touch the moon.
Rahul: If I don’t know, it doesn’t mean, will believe you blindly.🙄
Cyra: I know, it is not possible practically, but theoretically.
How this all is related to discrete Mathematics, In Computer Science, we often count how much time an algorithm takes, to present output, so we must understand counting…
So we will be discussing the following things.
2. Factorial.
3. Proof of n!.
6. Difference between Permutations and Combinations.
7. Combination with Repetitions.
Rule of Sum and Rule of Product
Cyra: Suppose you are given three different pizzas and three different burgers.
Rahul: Yes, I am hungry, I will eat all!🤤
Cyra: Wait motu, let me complete. You have to choose only one item from them, in how many ways you can do this?
Rahul: This is easy, let me tell you. There are 3 burgers and 3 pizzas so I can choose a pizza or a burger. there would be precisely 6 ways. This goes by the Rule of Sum.
[Cyra thinking, I thought he is dumb, but he isn’t, At least not in terms of food.]
Cyra: Yes, you are correct. Let me change this question a bit, Now, you have to choose exactly two items one from the pizzas and one from the burgers so, in how many ways you can do this?
Rahul: This is also simple, see I can take the first burger and first pizza, first burger, and second pizza, similarly there can be more.
So, you can choose from 3*3 that is 9 ways. This goes by the Rule of Product.
[Cyra thinking, let me ask him a hard one!]
Factorial
Cyra: In how many ways you can capture a picture of two children in a frame?
Rahul: Precisely 2 ways.
Cyra: In how many ways you can capture a picture of three children in a frame?
Rahul: This is the calculative one, I don’t know…
Cyra: Precisely 6 ways, how?
let’s name children A, B, C. They can stand like ABC, ACB, BAC, BCA, CAB, CBA. so there will be 6 ways.
Similarly, for four children, it will be 24 ways. so what is this??
This is Factorial, nice, isn’t it?
Proof of n!
[No conversations here, just simple straight proof!😉]
Let’s stick with that photograph-taking analogy.
In how many ways 2 children can be captured in a frame?
In the above picture, we have fixed d in different places to get the total number of ways.
Let’s fix d in the first place so now, we have to fix a, b, c. we have seen that we can fix a,b,c in 6 ways or more precisely factorial 3 ways which is the answer of placing 3 objects.
And, we do this every time, we change d’s position, like this…
d a b c [d in 1st place, number of ways in which we can arrange a,b,c is 3! ]
a d b c [d in 2nd place, number of ways in which we can arrange a,b,c is 3! ]
a b d c [d in 3rd place, number of ways in which we can arrange a,b,c is 3! ]
a b c d [d in 4th place, number of ways in which we can arrange a,b,c is 3! ]
The Answer of 4 objects = 4 * (3!)
=> Answer of 4 objects = 4 * (Answer of 3 objects)
So, In general n! = n * (n-1)!
Permutations
Cyra: In how many ways, from a group of 5 friends, 3 come forward and 2 steps back each time, to take a picture?
In how many ways they can take pictures, taking care of order…?
Rahul: I don’t know!😒, I need to check each case!
Cyra: No, you don’t have to check each case. So, here come permutations in the picture. Permutations are basically the arrangement of objects and the formula for Permutations is nPr and now what is this nPr ?
nPr is number of ways in which we can arrange r objects from a set of n objects.
nPr = n!/(n-r)!
So, when 3 friends come forward to take a picture, here r = 3 and n = 5
5P3 = 5!/(5–3)! => 5!/2! => 60 ways.
[Cyra thinking, how smart am i😛]
[Rahul thinking, she is really smart! 🙄]
Combinations
Cyra: I am changing this question a bit, Think of it this way, now, the friends are thinking, let’s not take the picture in every order of 3 people, if 3 are in the pic it must be done, and then we must switch to next pic having different people, in how many ways can you do this?
Rahul: I know the answer will not be the same, it will be less than the earlier, but how much it will be, I don’t know!😕😕
Cyra: Here Combinations come into the picture. Combinations are basically, in how many ways you can choose r objects from a set of n objects, without taking care of every order and the formula is given as:
nCr = nPr/r!
because, nPr included every order, and we don’t want every order, it can be written as.
nCr = n!/((n-r)! * r!)
So, in how many ways 3 friends can come forward to take the picture?
5C3 = 5!/((5–3!)*3! => 5!/(2!*3!) => 10 ways.
Quite interesting isn’t it?
Computer Science is fascinating and Mathematics too, we just need to change the way, we look at problems.
Difference between Permutations and Combinations.
[Again, just some simple differences😉]
Combination with Repetitions
Cyra: Suppose you are an Ice Cream Vendor…
Rahul: But, wait I am not, why do I suppose to be a vendor…😤
Cyra: Wait na, listen to me.
Rahul: Ok tell me!
Cyra: Suppose you are an Ice Cream Vendor having 3 different Ice-Cream flavors, namely, Vanilla, Chocolate, Mango, and there came 10 kids to buy ice cream, how you will sell ice-creams to these 10 kids??
Rahul: Maybe, 10C3! am I correct?
Cyra: If you are thinking 10C3, then it is wrong, you don’t want to choose 3 from 10 instead you want to sell ice-creams among these 10 kids with 3 flavors, I will tell you how…
[Rahul thinking, she is really smart.]
There can be the following possibilities…
1V 2C 7M | 8V 1C 1M | 10V 0C 0M
There can be many possibilities…
How we will solve this problem?
We will take 12 partitions and 2 sticks and divide the partitions into 3 parts!
Rahul: But, why 3 parts?
Cyra: Because you have 3 ice cream flavors!
Rahul: oh ha! yes, vanilla, chocolate, and mango.
Cyra: So you have to separate 10 partitions into 3 parts, remember this, we have included two more partitions just because for separating something in 3 parts You have to use 2 sticks, isn’t it? think of it…there can be many ways of separating them, but I have shown you a few only. So the solution will be 12C2, in these number of ways you can divide ice-creams among the kids
so in general formula is (n+r-1)Cr.
I hope you have understood, liked, and enjoyed the article!😊
Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer
