Simple Multiplication Rule for Permutations

Suppose that a task involves a sequence of k choices. Let n1 be the number of ways the first stage or event can occur and n2 be the number of ways the second stage or event can occur after the first stage has occurred. Continuing in this way, let nk be the number of ways the kth stage or event can occur after the first k - 1 stages or events have occurred.
Then the total number of different ways the task canoccur is: n1.n2.n3.n4….nk.





To understand this concept, assume that there are 4 roads from city A to city B and 3 roads from city B to city C. The total number of ways by which a person can reach from city A to city B is 4x3 = 12.

Let us look at a simple illustration.

Illustration: A dhaba has a lunch special which consists of a sandwich, soup, dessert and drink for Rs 99. They offer the following choices:
Sandwich: chicken salad, ham, and tuna, and roast beef
Soup: tomato, chicken noodle, vegetable
Dessert: cookie and pie
Drink: tea, coffee, coke, diet coke and sprite
How many lunch specials are there?

Let’s use the basic counting principle:
There are 4 stages or events: choosing a sandwich, choosing a soup, choosing a dessert and choosing a drink. There are 4 choices for the sandwich, 3 choices for the soup, 2 choices for the dessert and 5 choices for the drink. Putting that all together we get, 4x3x2x5 = 120. So there are 120 lunch specials possible.

Now, Let us look at another more complicated illustration.

Illustration: A company places a 6-symbol code on each unit of product. The code consists of 4 digits, the first of which is the number 5, followed by 2 letters, the first of which is NOT a vowel. How many different codes are possible?

Let’s use the basic counting principle: There are 6 stages or events: digit 1, digit 2, digit 3, digit 4, letter 1, and letter 2. In general there are 10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The first digit is limited to being the number 5, so there is only one possibility for that one. There is no restriction on digits 2 - 4, so each one of those has 10 possibilities.
In general, there are 26 letters in the alphabet. The first letter, cannot be a vowel (a, e, i, o, u), so that means there are 21 possible letters that could go there. The second letter has no restriction, so there are 26 possibilities for that one.
Putting that all together we get: 1x10x10x10x21x26 = 546000.

The sides of triangles

You would have often seen the the equation which states that any given side in a triangle is shorter than the sum of other two sides. Have you ever wondered why ?
The answer is simple:
Consider a straight line AC with B being a point on AC. Now, to make this a triangle let us bend AB and BC around B and join AC. Clearly AC will now be shorter than what it was earlier ie. , AC is shorter than AB+BC. So basically the triangle whose one side is equal to the other two will have and area = 0.

Lets try some problems to learn this better.
Problem: What is number of distinct triangles with integral valued sides and perimeter as 14 ?
a) 6 b) 5 c) 4 d) 3 [ CAT 2000 ]
This is a beautiful CAT problem testing both logical thinking and conceptual knowledge. Let us see the approach to this problem :
If a,b,c are sides of such a triangle then given that a+b+c =14.
The first thing to infer here is that any of the sides cannot be 7 or more as the sum of the other two sides should be larger than the third side. Therefore the largest side of such a triangle is 6. Let the smallest side be 1. So the other two sides add up to 13.
Cleary this is not possible as no side is 7 or more.
Let the smallest side be 2.
We can now have a triangle with sides (2,6,6). No other triangle is possible with smallest side 2.
Let the smallest side be 3.
We can now have a triangle with sides (3,5,6). No other triangle is possible with smallest side 3.
Let the smallest siden now have be 4.
We can now have a triangle with sides (4,5,5) & (4,4,6). No other triangle is possible with smallest side 4.

No other triangles are possible with smallest sides 5 or 6. Therefore a total of four triangles are possible with integer sides and perimeter 14.

Problem: There are 10 points in a plane. Except for 4 points , which are collinear, no 3 points are in a straight line. The number of triangles that can be formed with vertices as these points are
a) 120 b) 80 c) 119 d) 116
This is a problem of permutations involving simple concept of triangles. The idea of giving this problem here is to emphasise the fact that no topic can be viewed in isolation in CAT and concepts from different topics are often combined to create problrms that appear in CAT.
The appoach here is to identify that any 3 points can form a triangle.
Therefore 10 points will give 10C3 = 10x9x8 ∕ 6 = 120 triangles.

Now, the 4 points can form 4C3 = 4 triangles.
But 4 collinear points cannot form any triangle.So we have counted 4 triangles extra. Therefore the number of triangles are 120 – 4 = 116 triangles.

A note on factorials

Factorials are very simple things. They're just products, indicated by an exclamation mark. For instance, "four factorial" is written as "4!" and means 1×2×3×4 = 24. In general, n! ("enn factorial") means the product of all the natural numbers from 1 to n; that is, n! = 1×2×3×...×n.
The most common factorials are:
1! = 1
2! = 2 x 1 = 2
3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120
6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
Did you notice any pattern by any chance? 6! = 6 x 5!. Likewise 4! = 4 x 3!. Isn’t that an interesting observation? In general, we can write:
(n + 1)! = (n + 1) x n!.

What if we put n = 0 here?
1! = 1 x 0!
Or, 0! = 1
In fact I have seen many otherwise intelligent people making the fundamental error of assuming 0! = 0.
We can probably formulate a question like: If A and B are numbers such that A! = B! and A ≠ B, then how many such ordered pair of (A, B) exists?
Obviously two, as A and B can only have values 0 and 1 since only for these values we have 0! = 1!.

What if we have to simplify the expression given below?
p = 1 + 2x2! + 3x3! + ….10x10!

How do we approach these problems?
See that the nth term here, say Tn = nxn!.
But we have learnt that (n+1)n! = (n+1)!.
So, let’s now write nxn! as (n + 1 –1)xn! = (n+1)n! –n!.
Or, Tn = (n+1)! – n! ; T1 = 2! – 1! ; T2 = 3! – 2! and so on.
Obviously every other term will get cancelled in the sum and we would be left with 11! – 1!

By the way we just solved a 2 mark question in a very recent CAT. Half a dozen of such questions and the cut-off needed to clear CAT would be through.