Permutations

Advertisements

Topics

  • Sets and Relations
  • Functions
  • Complex Numbers 33
  • Sequences and Series
    • Concept of Sequences
    • Geometric Progression (G.P.)
    • General Term Or the nth Term of a G.P.
    • Sum of the First n Terms of a G.P.
    • Sum of Infinite Terms of a G. P.
    • Recurring Decimals
    • Harmonic Progression (H. P.)
    • Types of Means
    • Special Series (Sigma Notation)
  • Locus and Straight Line
    • Locus
    • Equation of Locus
    • Line
    • Equations of Lines in Different Forms
    • General Form Of Equation Of Line
  • Determinants
    • Determinants
    • Properties of Determinants
    • Application of Determinants
    • Cramer’s Rule
    • Consistency of Three Linear Equations in Two Variables
    • Area of a Triangle Using Determinants
    • Collinearity of Three Points
  • Limits
    • Definition of Limit of a Function
    • Algebra of Limits
    • Evaluation of Limits
    • Direct Method
    • Factorization Method
    • Rationalization Method
    • Limits of Exponential and Logarithmic Functions
  • Continuity
    • Continuous and Discontinuous Functions
    • Continuity of a Function at a Point
    • Definition of Continuity
    • Continuity from the Right and from the Left
    • Properties of Continuous Functions
    • Continuity in the Domain of the Function
    • Examples of Continuous Functions Whereever They Are Defined
  • Differentiation
    • The Meaning of Rate of Change
    • Definition of Derivative and Differentiability
    • Derivative by the Method of First Principle
    • Rules of Differentiation (Without Proof)
    • Applications of Derivatives
  • Partition Values
    • Concept of Median
    • Partition Values
    • Quartiles
    • Deciles
    • Percentiles
    • Relations Among Quartiles, Deciles and Percentiles
    • Graphical Location of Partition Values
  • Measures of Dispersion
    • Measures of Dispersion
    • Range of Data
    • Quartile Deviation (Semi - Inter Quartile Range)
    • Variance and Standard Deviation
    • Standard Deviation for Combined Data
    • Coefficient of Variation
  • Skewness
    • Skewness
    • Asymmetric Distribution (Positive Skewness)
    • Asymmetric (Negative Skewness)
    • Measures of Skewness
    • Karl Pearson’S Coefficient of Skewness (Pearsonian Coefficient of Skewness)
    • Features of Pearsonian Coefficient
    • Bowley’s Coefficient of Skewness
  • Bivariate Frequency Distribution and Chi Square Statistic
    • Bivariate Frequency Distribution
    • Classification and Tabulation of Bivariate Data
    • Marginal Frequency Distributions
    • Conditional Frequency Distributions
    • Categorical Variables
    • Contingency Table
    • Chi-Square Statistic ( χ2 )
  • Correlation
    • Correlation
    • Concept of Covariance
    • Properties of Covariance
    • Concept of Correlation Coefficient
    • Scatter Diagram
    • Interpretation of Value of Correlation Coefficient
  • Permutations and Combinations
    • Introduction of Permutations and Combinations
    • Fundamental Principles of Counting
    • Concept of Addition Principle
    • Concept of Multiplication Principle
    • Concept of Factorial Function
    • Permutations
    • Permutations When All Objects Are Distinct
    • Permutations When Repetitions Are Allowed
    • Permutations When All Objects Are Not Distinct
    • Circular Permutations
    • Properties of Permutations
    • Combination
    • Properties of Combinations
  • Probability
  • Linear Inequations
  • Commercial Mathematics
    • Percentage
    • Profit and Loss
    • Simple and Compound Interest (Entrance Exam)
    • Depreciation
    • Partnership
    • Goods and Service Tax (GST)
    • Shares and Dividends
  • Permutation
  • Permutation of repeated things
  • Permutations when all the objects are not distinct
  • Number of Permutations Under Certain Restricted Conditions
  • Circular Permutations

Definition

A permutation is an arrangement in a definite order of a number of objects taken some or all at a time.

Notes

We are actually counting the different possible arrangements of the letters such as ROSE, REOS, ..., etc. Here, in this list, each arrangement is different from other. In other words, the order of writing the letters is important. Each arrangement is called a permutation of 4 different letters taken all at a time. Now, if we have to determine the number of 3-letter words, with or without meaning, which can be formed out of the letters of the word NUMBER, where the repetition of the letters is not allowed, we need to count the arrangements NUM, NMU, MUN, NUB, ..., etc. Here, we are counting the permutations of 6 different letters taken 3 at a time. The required number of words = 6 × 5 × 4 = 120 (by using multiplication principle). If the repetition of the letters was allowed, the required number of words would be 6 × 6 × 6 = 216.

Theorem

Permutations when all the objects are distinct:

Theorem: The number of permutations of n different objects taken r at a time, where 0 < r ≤ n  and the objects do not repeat  is n ( n – 1) ( n – 2). . .( n – r + 1), which is denoted by `"^n P_r`.
Proof: There will be as many permutations as there are ways of filling in r vacant the n objects. The first place can be filled in n ways; following which, the second place can be filled in (n – 1) ways, following which the third place can be filled in (n – 2) ways,..., the rth place can be filled in (n – (r – 1)) ways. Therefore, the number of ways of filling in r vacant places in succession is n(n – 1) (n – 2) . . .   (n – (r – 1)) or n ( n – 1) (n – 2)
... (n – r + 1). 
This expression for `"^n P_r`  is cumbersome and we need a notation which will help to reduce the size of this expression. The symbol n! (read as factorial n or n factorial ) comes to our rescue. In the following text we will learn what actually n! means.

Notes

Factorial notation:The notation n! represents the product of first n natural numbers, i.e., the product 1 × 2 × 3 × . . . × (n – 1) × n is denoted as n!. We read this symbol as ‘n factorial’.
1 = 1 ! 
1 × 2 = 2 ! 
1× 2 × 3 = 3 ! 
1 × 2 × 3 × 4 = 4 ! and so on.
We define 0 ! = 1 
We can write   5 ! = 5 × 4 ! = 5 × 4 × 3 ! = 5 × 4 × 3 × 2 !  = 5 × 4 × 3 × 2 × 1! 
Clearly, for a natural number n     
n ! = n (n  –  1) ! 
= n (n  –  1) (n  –  2) !                       [provided (n ≥ 2)]
= n (n  –  1) (n  –  2) (n  –  3)!   [provided (n ≥ 3)] 
and so on.

Notes

Derivation of the formula for `"^n P_r`:
`"^n P_r= (n!)/(n-r)!` , 0 ≤ r ≤ n
Let us now go back to the stage where we had determined the following formula: 
 `"^n P_r`= n (n – 1) (n – 2) . . .  (n – r + 1)
Multiplying numerator and denomirator by (n – r) (n – r – 1) . . . 3 × 2 × 1, we get
 `"^n P_r`= [n (n – 1) (n – 2) . . .  (n – r + 1)(n-r) (n-r-1)... 3xx2xx1]/[(n-r) (n-r-1)... 3xx2xx1]
                   = n!/ (n-r)!
Thus `"^n P_r= (n!)/ (n-r)!`, where 0 < r ≤ n

Theorem

Theorem: The number of permutations of n different objects taken r at a time, where repetition is allowed, is `n^r`. 
The number of 3-letter words which can be formed by the letters of the word
NUMBER = `"^6 P_3= (6!)/(3!)`= 4*5*6= 120. Here, in this case also, the repetition is not
allowed. If  the repetition is allowed,the required number of words would be `6^3` = 216. 
The number of ways in which a Chairman and a Vice-Chairman can be chosen from amongst a group of 12 persons assuming that one person can not hold more than one position, clearly
`"^12 P_2= (12!)/(10!)`= 11*12= 132.

Notes

 Permutations when all the objects are not distinct objects:  Suppose we have to find the number of ways of rearranging the letters of the word INSTITUTE. In this case there are 9 letters, in which I appears 2 times and T appears 3 times. 
Temporarily, let us treat these letters different and name them as `I_1, I_2, T_1,  T_2, T_3`. The number of permutations of 9 different letters, in this case, taken all at a time is 9 !. Consider one such permutation, say, `I_1 NT_1 SI_2 T_2 U E T_3`.  Here if `I_1, I_2` are not same and `T_1, T_2, T_3` are not same, then `I_1, I_2` can be arranged in 2! ways and `T_1, T_2, T_3 `can be arranged in 3! ways. Therefore, 2! × 3! permutations will be just the same permutation corresponding to this chosen permutation `I_1NT_1SI_2T_2UET_3`. Hence, total number of different permutations will be `9!/(2!3!)`

Theorem

Theorem: The number of permutations of n objects, where p objects are of the
same kind and rest are all different = `(n!)/(p!)`.
In fact, we have a more general theorem.

Theorem

Theorem: The number of permutations of n objects, where p1 objects are of one kind, p2 are of second kind, ..., pk are of kth kind and the rest, if any, are of different kind is 
`(n!)/(p_1!p_2!...p_k!)`

If you would like to contribute notes or other learning material, please submit them using the button below.

Shaalaa.com | Theorem of permutation and combination

Shaalaa.com


Next video


Shaalaa.com


Theorem of permutation and combination [00:07:51]
S
Series:
0%


Advertisements
Share
Notifications



      Forgot password?
Use app×