Permutations and Combinations - Anubhav Sehgal

[anubhav_sehgal]

Concept 1 : Geometrical Arrangement

We look to position the first object and consider all possible distinct orientations. After choosing that, we arrange rest of them simply by permutation.
So,
Square has only 2 distinct positions denoted by different colors
Hence 2 * 7!
Similarly,
Equilateral triangle : 3 * 8!
Rectangle : 5 * 9!

By orientation what we mean is if we position ourselves at that spot then how would our left right and surrounding seem to us. So , we look for such distinct oriented positions.

Try this : Isosceles Triangle. Positions have been marked for you but try to see them for yourself as to how they are distinct.

Ans is 8 x 7!
Assume yourself in the purple spot,then to your right you have two objects and to your left you have the vertex followed up by three objects. While if you place yourself in the mustard yellow spot you would have a different right and left side.

Permutations for n distinct objects to be arranged around a circle is (n - 1)! and now you know how :slight_smile:

The logic follows from the earlier orientations' explanation.
All positions are same orientation wise when taken around a circle.
Hence 1*(Permutate the remaining (n-1) objects. Hence 1*(n - 1)!

Concept 2 : DISTRIBUTION AND ARRANGEMENT

Case 1 :
6 distinct letters to be put in 4 different envelopes [ When order to place objects not important ]
Each letter has 4 different options. Hence 4 * 4 * 4 * 4 * 4 * 4 = 4^6
6 rings to be put on 4 fingers [Here the order in which rings goes onto a finger matters.
So first ring has 4 options[the 4 fingers], second ring has 5 options[the 4 fingers and above/below the already placed ring] and so on.
OR
We simply say, 9c3 * 6! = 9p6 permutations.
The logic to 9c3 will be seen in Case 2.

Case 2 : Letters are IDENTICAL and envelopes are DIFFERENT.
Let the envelopes be named as e1,e2,e3, and e4
So we need to just allocate letters(identical) to these 4 envelopes.
e1 + e2 + e3 + e4 = 6
=> C(6 + 4 - 1, 4 - 1) non negative integral solutions = C(9,3) ways
NOTE : This is under the assumption that an envelope may or may not be empty hence we took the non negative integral solutions.

Case 3 : Letters are DIFFERENT and envelopes are IDENTICAL
example : 5 different letters , 3 identical envelopes
Standard procedure :
5,0,0 : C(5,5) = 1 way
4,1,0 : C(5,4) * C(1,1) = 5 ways
3,2,0 : C(5,3) * C(2,2) = 10 ways
3,1,1 : C(5,3) * C(2,1) * C(1,1) /2 = 10 ways [ We divide by 2 as envelopes are identical so the selection amongst last two letters is nullified as it doesn't matter whether letter L4 goes into envelope 2(E) and L5 in envelope 3(E) OR letter L4 goes into envelope 3(E) and so on..as all envelopes are identical i.e. E(say)
2,2,1 : C(5,2) * C(3,2) * C(1,1) /2 = 15 ways
41 ways total
Alternate methods : Stirling and integral equations. But let's leave that for some other day.

Case 4 : Both letters and envelopes are IDENTICAL
Just count the manual cases possible of the Case 3. Like for 5 letters and 3 envelopes we will have :
(5,0,0) ; (4,1,0) ; (3,2,0) ; (3,1,1) ; (2,2,1) : 5 ways total.

Case 5 : Both envelopes and letters are DIFFERENT with the condition that none of the envelope is empty.
Here we apply the inclusion exclusion principle :
4^6 - C(4,1) * 3^6 + C(4,2) * 2^6 - C(4,3) * 1^6 + C(4,4) * 0^6
Arrange all as distinct. From that we remove cases where one envelope is empty. But that also removes cases where two were empty when we take 3^6 for rest. So we add the cases where 3 envelopes are empty..and so on until set is exhausted.

Concept 3 :Number of routes problem

A : 0,0
X : 3,2
B : 6,4
Total paths(A to B ) = (6 + 4)!/6!4! = 10!/6!4!
Paths from A to X = (3 + 2)!/3!2!
Paths from X to B : (3 + 2)!/3!2!
Hence number of valid paths(if red region is considered not to be crossed) = Total - (5!/3!2! * 5!/3!2!)
As A->X->B is not a valid path.
Number of paths from point (x1,y1) to (x2,y2) is given by
[(x2 - x1) + (y2 - y1)]! / (x2 - x1)! * (y2 - y1)!
Alternate method : Numbering grid points[Leaving it for some other day]

Concept 4 : De arrangement Principle

To arrange items into containers such that none of the items goes into its designated container.
D(n) = n!(1 - 1/1! + 1/2! - 1/3! ... 1/n!) for n items
example : Number of ways to put 4 letters into 4 envelopes such that none of them goes into its correct one is given by :
D(4) = 4!(1 - 1/1! + 1/2! - 1/3! + 1/4!) = 9 ways
D(1) = 0 ; D(2) = 1 ; D(3) = 2 ; D(4) = 9 ; D(5) = 44
These are some important values you could remember.

Concept 5 : Number of squares and rectangles in a m x n matrix

Case 1 : m = n = k(say)
Squares = 1^2 + 2^2 + .. + k^2 = k(k + 1)(2k + 1)/6
Rectangles = 1^3+ 2^3 + .. + k^3 = [k(k + 1)/2]^2

Case 2 : m != n
Squares = mn + (m - 1)(n - 1) + (m - 2)(n - 2) + .. + 0
Rectangles = (1 + 2 + 3 + .. + m)(1 + 2 + .. + n) = m(m + 1)n(n + 1)/4

Concept 6 : Sum of all numbers formed by given digits

Case 1 : No digit repeated
Digits : 2,3,4,5,6 ; Sum of all 5 digit numbers such that no digit repeated.
Sum = (Sum of digits) * 11...n times for n digits numbers * (n - 1)!
Here, sum = (2 + 3 + 4 + 5 + 6) * 11111 * (5 - 1)!

Case 2 : Repetition is allowed
Sum = (Sum of digits) * 11...n times for n digits numbers * n^(n - 1)

Case 3 : When digits to be used includes 0(zero)
example : Digits : 0,2,3,4
Find sum of all 4 digit numbers formed by the given digits such that no digit repeated.
Sum = (0 + 2 + 3 + 4) * 1111 * (4 - 1)! - (2 + 3 + 4) * 111 * (3 - 1)!
i.e Total sum minus sum of all numbers with digits other than zero as zero cannot be at first place.