# Concept: Permutation & Combination

CONTENTS

INTRODUCTION

Permutation means arrangement while Combination means selection

BASIC PRINCIPLES OF COUNTING

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

FORMULAE

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

nPr = $\frac{n!}{\left(n-r\right)!}$

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

nCr = $\frac{n!}{\left(n-r\right)! × r!}$

ARRANGEMENTS

LINEAR ARRANGEMENTS

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{×}\mathbf{q}\mathbf{!}\mathbf{×}\mathbf{r}\mathbf{!}}$ ways

CIRCULAR ARRANGEMENTS

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

NECKLACE/GARLAND

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

SELECTION

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 = 2p × 2q × 2r = 2p+q+r

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

• at least one object of each type = (2p - 1) × (2q - 1) × (2r - 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

DISTRIBUTION OF OBJECTS IN GROUPS OF DEFINED SIZES

• 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{\left(}\mathbf{p}\mathbf{+}\mathbf{q}\mathbf{+}\mathbf{r}\mathbf{\right)}\mathbf{!}}{\mathbf{p}\mathbf{!}\mathbf{×}\mathbf{q}\mathbf{!}\mathbf{×}\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{\left(}\mathbf{p}\mathbf{!}\mathbf{\right)}}^{\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{×}{\mathbf{\left(}\mathbf{p}\mathbf{!}\mathbf{\right)}}^{\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{\left(}\mathbf{p}\mathbf{!}\mathbf{\right)}}^{\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{×}{\mathbf{\left(}\mathbf{p}\mathbf{!}\mathbf{\right)}}^{\mathbf{3}}}$

DISTRIBUTION OF SIMILAR OBJECTS IN DIFFERENT GROUPS

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

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

NUMBER OF TERMS IN THE EXPANSION OF (a + b + ...)n
• Number of terms in the expansion of (a + b)n = n+1C1 = n + 1

• Number of terms in the expansion of (a + b + c)n = n+2C2

• Number of terms in the expansion of (a + b + c + d)n = n+3C3

GEOMETRY BASED CONCEPTS

MATRIX

• Number of ways of selecting a square from a n × n square matrix is:
• 12 + 22 + 32 + ... + n2

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

• 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{\left(}\mathbf{m}\mathbf{+}\mathbf{n}\mathbf{\right)}\mathbf{!}}{\mathbf{m}\mathbf{!}\mathbf{×}\mathbf{n}\mathbf{!}}$

FIGURES

Lines

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) = pC2 - cC2 + 1

Triangles

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

## Feedback

Help us build a Free and Comprehensive Preparation portal for various competitive exams by providing us your valuable feedback about Apti4All and how it can be improved.