Permutation and Combination Basics

0
461
permutations and combinations

Permutation and combination basics with all the concepts and their difference are clearly explained below with examples.

What is Permutation?

Every one of the various courses of action which can be made by taking a few or the majority of a given number of things or articles one after another or objects at a time is called permutation.

Permutation Formula with Example

Let us consider letters x, y, and z
In different ways these letters can be arranged together taken all at a time is xyz, xzy, yxz, yzx, zxy, and zyx.
That is in 6 ways these 3 letters are arranged and 6 is equal to 3!
So, the permutation of ‘n’ different things of them ‘r’ taken at a time is given by npr  .
\begin{align*}
p\left( n,r\right) =\dfrac {n!}{\left( n-r\right) !}
\end{align*}

What is Combination?

Every one of the various groups or selections which can be made by taking a few or the majority of various things (regardless of order) is called the combination.

Factorial Notation

The product of first n natural numbers is a factorial of ‘n’. It is represented by n!.
n!=1×2×3×4×………×(n-1)×n

Example of Factorial Notation

What is the value of 5!
5!= 5 × 4 × 3 × 2 × 1
=120

Note:
0!=1
n!=n × (n-1)!
(2n)!= 2n×(n!)×[1×3×5×……….×(2n-1)]

What is the difference between Permutation and Combination in Basics?

Permutation deals with arranging things. While arranging the things the order of their arrangement is taken into consideration.
A combination deals with a selection of things and while selecting the things their order of selection has no importance.

Fundamental Principles of Counting Permutation and Combination Basics

There are 2 fundamental principles of counting that are base on permutation and combination.
1. Multiplication Principle
2. Addition Principle
These two principles can be extended to an infinity number of events.

Multiplication Principle

If an event can happen in ‘m’ distinct ways following which another event can happen in ‘n’ distinct ways at that point the total number of occurences of event in the given order is m×n.

Example:

Lucky has 5 pairs of shoes and 3 pairs of socks. How many different pairs of shoes and socks can he wear with?
solution:

Here, Lucky has 5 ways of choosing shoes because he has 5 pairs of shoes.
In the same way he can choose 3 pairs of socks.
For every pair of shoes he choose, there are 3 choices of pairs of socks.
Therefore, there are 5×3=15 pairs of shoes and socks lucky can choose.

Addition Principle

If an event can happen in m distinct ways, and another event is independent of first event can happen in ‘n’ distinct ways. Then, total number of occurences of events is in (m+n) ways.

Example:

Suppose there are 4 doors to a room, two on one side and two on other side. Pappulu has to go out of the room?
Solution:

He can go out from any of the 4 doors. 
The total number of ways he can go out is 4 ways.
That is on one side he can go in 2 ways and on other side he can go in 2 ways.
Then total number of ways he can go is 2+2 =4 ways.

Permutation with Repetition

Let us consider n things, taken all at a time, If this ‘n’ things consits of ‘q’ things alike of one type and ‘r’ things alike of another type and rest of all the things are different.
Then the number of permutations of n things is 
\begin{align*}
\dfrac {n!}{q!r!}
\end{align*}

Example:

Find number of ways VINEETH can be written.
Solution:

Total number of letters in VINEETH is 7
2 letters are repeting ‘E’
∴ number of permutation of words is 7! ⁄ 2!
Here for repition of things or letters of different kinds permutation is calculated by factorial of total letters or things divided by factorial of individual number of repeted thing or letters factorial.

Permutation of n different things taken r at a time and each thing may be repeated any number of times is given by nr.
Example:

Consider 6 numbers {1, 2, 3, 4, 5, and 6}
we have to choose a 3 digit number from them.
This can be done in 6×6×6   (3 times)
Permutation = 63

Permutation without Repetition

Permutation of n different things taken r at a time and each thing not repeated again is given by 
\begin{align*}
\dfrac {n!}{\left( n-r\right) !}
\end{align*}
Example:

Let us consider the same above example for better undersating  with
6 numbers {1, 2, 3, 4, 5, and 6}
Here choosing 3 digits without repetition from 6 numbers.
This can be done in 6×5×4 =120 ways. 
By formula of permutation without repetition ,it is 6!⁄(6-3)!
⇒ 6!⁄ 3!
⇒120. 

Example problem of permutation with and without repetition

Consider a 10 digit number (0, 1, 2, 3,…….9). How many 3-digit numbers can be formed from them.
With Repetition:

10×10×10 = 103
(or) 
Since, nr here n=10 and r=3

Without Repetition:

10×9×8 = 720
(or)
Since, n!/(n-r) = npr
= 10! / (10-3)!
= 10! / 7!
=720

Permutations with Restrictions Formulas

For ‘n’ different things, taken all at a time 

  • When ‘p’ specific things always come together, then
    number of permutations of ‘n’ different things is p!(n-p+1)!
  • When ‘p’ specified things never come together, then
    number of permutations of ‘n’ different things is (p!-m!)×(n-p+1)!

For ‘n’ different things, taken ‘r’ at a time,

  • When  a particular thing is always included in each grouping, then
    number of permutations of ‘n’ different things is n-1pr-1.
  • When a particular thing is never taken in grouping, then
    permutation of ‘n’ different things is  n-1pr.
  • When ‘p’ particular things are always included in each grouping then
    total number of permutations of ‘n’ different things is [r-(s-1)]× n-spr-s.

Combinations Formula

Let us consider alphabets x, y, and z taken 2 at a time xy, yz and zx.
Here order of selection is not important.
So, here selection of 2 letters at atime is done in 3 ways. i,e 3!/(3-2)!2!.
Thus, number of combination of ‘n’ things taken ‘r’ at a time is given by ncr.
\begin{align*}
n_{C_{r}}=\dfrac {n!}{\left( n-r\right) !r!} \ \ where \ \left( 0\leq r\leq n\right)
\end{align*}

Relation between Permutation and Combination Basics

 

\begin{align*}
n_{C_{r}}=\dfrac {n_{\Pr }}{r!}
\end{align*}
if r>n, then  ncr=0.

Combination with Restrictions

For ‘n’ different things taken ‘r’ at a time 

  • When ‘p’ specific things are always then
    number of combination of n things is n-pcr-p.
  • When ‘p’ specific things are never included then
    number of combination of ‘n’ things is n-pcr
  • When ‘p’ specified things are not together in any selection then
    number of cobination of n things is ncrn-pcr-p.

Number of selection of zero or more things

  • Out of n different things is  nc0nc1nc2+ ………..+ncn = 2n.
  • Out of n alike things is n+1.

Some more Combinations with Restrictions

  • Number of selection of one or more things out of ‘n’ alike things is ‘n’.
  • Number of selection of ‘r’ things out of ‘n’ alike things is 1.
  • Number of combination of ‘n’ different things selecting at least one of them is
    nc0nc1nc2+ ………..+ncn = 2n -1.
  • For p+q different things in two groups holding p and q things respectively,
    total number of combinations is p+qcp.
    \begin{align*}
    \dfrac {\left( p+q\right)!}{p!r!}
    \end{align*}
  • For p+q+r different things in three groups holding p, q and r things respectively, 
    total number of combinations of (p+q+r) things is
    \begin{align*}
    \dfrac {\left( p+q+r\right)!}{p!q!r!}
    \end{align*}
  • For p+q+r things where p are alike of one kind, q are alike of second kind and r are alike of third kind then
    number of combination of things is [(p+1)(q+1)(r+1)-1].

Some important formulas of Combinations

  • nCr = nCn-r
  • nC0 = nCn = 1,
  • nC1=n
  • nCr + nCr-1 = n+1Cr
  • nC0 + nC2 + nC4 +………. = nC1 + nC3 + nC5 +………… = 2n-1
  • Greatest value of nCr when n is even is nCn⁄2
  • Greatest value of nCr when n is odd is nCn+1 ⁄2 or nCn-1 ⁄2
  • \begin{align*}
    n_{C_{r}}=\dfrac {n!}{\left( n-r\right) !r!}
    \end{align*}

Circular Permutation and Combination Basics

For n different things number of circular arrangements is (n-1)!
Example:

Let us consider 5 persons A, B, C, D and E sitting in a circle facing each other.
Fix ‘A’ at one position and the number of ways in remaining persons are arranged is (5-1)! =4! =24.

For the above examples, when observations is made from both sides that is clockwise and anti clockwise then, number of circular arranements is reduced to ½ × (n-1)!
i,e 
½ × (5-1)! = 4!/2! =12.

 

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here