Concept: Permutation & Combination

CONTENTS

• Introduction
• Basic Principles of Counting
• Formulae
• Arrangements
• Linear Arrangements
• Circular Arrangements
• Necklace/Garland
• Selection
• Distribution of Objects in Groups of Defined Sizes
• Distribution of Similar Objects in Different Groups
• Number of terms in the Expansion of (a + b + ...)ⁿ
• Geometry Based
• Matrix
• Figures

 

Permutation means arrangement while Combination means selection

 

If A or B (exactly 1 of A or B) are two tasks that must be performed such that A can be performed in 'p' ways and B can be performed in 'q' ways, then A or B can be performed in p + q ways

If A and B are two tasks that must be performed such that A can be performed in 'p' ways and for each possible way of performing A, say there are 'q' ways of performing B, then the two tasks A and B can be performed in p × q ways

 

Number of ways arranging r people out of n in a row = n × (n-1) × (n-2) ... × (n-r+1) = ⁿP_r

ⁿP_r = $\frac{\mathrm{n!}}{\mathrm{(n-r)!}}$

Number of ways selecting r people out of n = (No of ways of arrangement) ÷ r! = (n × (n-1) × (n-2) ... × (n-r+1)) ÷ r! = ⁿC_r

ⁿC_r = $\frac{\mathrm{n!}}{\mathrm{(n-r)!\; \times \; r!}}$

 

Number of ways of arranging 'n' distinct items in a line is given by

n! ways

Number of ways of arranging 'n' items out of which `p' are alike, 'q' are alike, 'r' are alike in a line is given by

$\frac{\mathbf{n}\mathbf{!}}{\mathbf{p}\mathbf{!}\mathbf{\times }\mathbf{q}\mathbf{!}\mathbf{\times }\mathbf{r}\mathbf{!}}$ ways

 

Number of ways of arranging 'n' distinct items around a circle is given by (n - 1)! ways

 

Number of ways of arranging 'n' distinct items around a circle is given by $\frac{\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}}{\mathbf{2}}$ ways

 

Out of 'p' distinct objects of type I, 'q' distinct objects of type II and 'r' distinct objects of type III, number of ways of selecting

• any number of objects = 2^p × 2^q × 2^r = 2^p+q+r

• at least one object = 2^p+q+r - 1

• at least one object of each type = (2^p - 1) × (2^q - 1) × (2^r - 1)

Out of 'p' similar objects of type I, 'q' similar objects of type II and 'r' similar objects of type III, number of ways of selecting

• any number of objects = (p + 1) × (q + 1) × (r + 1)

• at least one object = (p + 1) × (q + 1) × (r + 1) - 1

• at least one object of each type = p × q × r

 

• The number of ways of dividing (p + q + r) distinct items into three groups containing p, q and r items respectively is (p ≠ q ≠ r) = $\frac{\mathbf{(}\mathbf{p}\mathbf{+}\mathbf{q}\mathbf{+}\mathbf{r}\mathbf{)}\mathbf{!}}{\mathbf{p}\mathbf{!}\mathbf{\times }\mathbf{q}\mathbf{!}\mathbf{\times }\mathbf{r}\mathbf{!}}$

• The number of ways of dividing 2p distinct items into two equal groups of p each

• when the two groups have distinct identity, is $\frac{\mathbf{\left(}\mathbf{2}\mathbf{p}\mathbf{\right)}\mathbf{!}}{{\mathbf{(}\mathbf{p}\mathbf{!}\mathbf{)}}^{\mathbf{2}}}$
• when the two groups don't have distinct identity, is $\frac{\mathbf{\left(}\mathbf{2}\mathbf{p}\mathbf{\right)}\mathbf{!}}{\mathbf{2}\mathbf{!}\mathbf{\times }{\mathbf{(}\mathbf{p}\mathbf{!}\mathbf{)}}^{\mathbf{2}}}$

• The number of ways of dividing 3p distinct items into three equal groups of p each

• when the three groups have distinct identity, is $\frac{\mathbf{\left(}\mathbf{3}\mathbf{p}\mathbf{\right)}\mathbf{!}}{{\mathbf{(}\mathbf{p}\mathbf{!}\mathbf{)}}^{\mathbf{3}}}$
• when the three groups don't have distinct identity, is $\frac{\mathbf{\left(}\mathbf{3}\mathbf{p}\mathbf{\right)}\mathbf{!}}{\mathbf{3}\mathbf{!}\mathbf{\times }{\mathbf{(}\mathbf{p}\mathbf{!}\mathbf{)}}^{\mathbf{3}}}$

 

No of ways of distributing 'n' similar objects in r distinct groups = ^n+r-1C_r-1

No of ways of distributing 'n' similar objects in r distinct groups such that each group gets at least one object = ^n-1C_r-1

• Number of terms in the expansion of (a + b)ⁿ = ⁿ⁺¹C₁ = n + 1

• Number of terms in the expansion of (a + b + c)ⁿ = ⁿ⁺²C₂

• Number of terms in the expansion of (a + b + c + d)ⁿ = ⁿ⁺³C₃

 

• Number of ways of selecting a square from a n × n square matrix is:

1² + 2² + 3² + ... + n²

• Number of ways of selecting a rectangle from a m × n matrix is:

^mC₂ × ⁿC₂

• Number of ways of traveling from lower left corner to upper right corner of a m × n square matrix when you can travel only in east and north direction

$\frac{\mathbf{(}\mathbf{m}\mathbf{+}\mathbf{n}\mathbf{)}\mathbf{!}}{\mathbf{m}\mathbf{!}\mathbf{\times }\mathbf{n}\mathbf{!}}$

Number of unique lines that can be formed by joining any 2 points out of ‘p’ points of which ‘c’ points are collinear (c < p) = ^pC₂ - ^cC₂ + 1

Number of unique triangles that can be formed with three vertices from ‘p’ points out of which ‘c’ points are collinear (c < p) = ^pC₃ - ^cC₃