Algebra
Textbooks
Boundless Algebra
Combinatorics and Probability
Combinatorics
Algebra Textbooks Boundless Algebra Combinatorics and Probability Combinatorics
Algebra Textbooks Boundless Algebra Combinatorics and Probability
Algebra Textbooks Boundless Algebra
Algebra Textbooks
Algebra
Concept Version 9
Created by Boundless

Permutations of Nondistinguishable Objects

The expression revealing the number of permutations of distinct items can be modified if not all items in the set are distinct.

Learning Objective

  • Calculate the number of permutations of a given set of objects, some being nondistinguishable


Key Points

    • Some sets include repetitions of certain elements. In these cases, the number of possible permutations of the items cannot be expressed by n!n!n!, where nnn represents the number of elements, because this calculation would include a multiplicity of possible states.
    • To correct for the multiplicity of certain permutations, divide the factorial of the total number of elements by the product of the factorials of the number of each repeated element.
    • The expression for number of permutations with repeated elements is: n!n1!n2!n3!...\frac {n!}{n_1!n_2!n_3!... }​n​1​​!n​2​​!n​3​​!...​​n!​​ where nnn is the total number of terms in a sequence and n1n_1n​1​​, n2n_2n​2​​, and n3n_3n​3​​ are the number of repetitions of different elements.

Terms

  • multiplicity

    The number of values for which a given condition holds.

  • permutation

    An ordering of a finite set of distinct elements.


Full Text

Recall that the number of possible permutations of a set of nnn distinct elements is given by n!n!n!:

n⋅(n−1)⋅(n−2)⋯2⋅1\displaystyle n \cdot (n-1) \cdot(n-2) \cdots 2 \cdot 1n⋅(n−1)⋅(n−2)⋯2⋅1

This can be easily tested. The number 111 can be arranged in just one 1!1!1! way. The numbers 111 and 222 can be arranged in two 2!2!2! ways: (1,2)(1,2)(1,2) and (2,1)(2,1)(2,1). The numbers 111, 222, and 333 can be arranged in 3!3!3! ways: (1,2,3)(1,2,3)(1,2,3), (1,3,2)(1,3,2)(1,3,2), (2,1,3)(2,1,3)(2,1,3), (2,3,1)(2,3,1)(2,3,1), (3,1,2)(3,1,2)(3,1,2), and (3,2,1)(3,2,1)(3,2,1). This rule holds true for sets of any size, so long as the elements are all distinct. But what if some elements are repeated?

Repetition of some elements complicates the calculation of permutations, because it allows for there to be multiple ways in which a specific order of elements can be arranged. For example, given the numbers 111, 333, and 333 in a set, there are 2 ways to obtain the order (3,1,3)(3,1,3)(3,1,3).

To correct for the "multiplicity" of certain permutations, we must divide the factorial of the total number of elements by the product of the factorials of the number of each repeated element. This can generally be represented as:

n!n1!n2!n3!...\displaystyle \frac {n!}{n_1!n_2!n_3!... }​n​1​​!n​2​​!n​3​​!...​​n!​​

Where nnn is the total number of terms in a sequence, and n1n_1n​1​​, n2n_2n​2​​, and n3n_3n​3​​ represent the number of repetitions of different elements. 

To understand why we would divide by the number of repetitions, consider that 222elements can be arranged in a total of 2!2!2! distinct ways, 333 elements can be arranged in a total of 3!3!3! distinct ways, and so on. When we encounter multiplicity in a permutation, we must account for it by dividing these possible arrangements out of the total number of permutations that would be possible if all of the elements were distinct.

Example: Consider the set of numbers:

 (15,17,24,24,28)\displaystyle (15, 17, 24, 24, 28)(15,17,24,24,28)

There are five terms, so n=5n=5n=5. However, two of the terms are the same; their value is 242424. Thus, the number of possible distinct permutations in the set is:

5!2!=60\displaystyle{\frac {5!}{2! }=60}​2!​​5!​​=60

The same logic can apply to more complicated systems. 

Example: Consider the set:

(0,0,0,2,4,4,7,7,7,7,7,8,8)\displaystyle (0, 0, 0, 2, 4, 4, 7, 7, 7, 7, 7, 8, 8)(0,0,0,2,4,4,7,7,7,7,7,8,8)

In total, there are 131313 elements. These include many repetitions: 000 is seen 3 times, 444and 888 each are observed twice, and there are 555 instances of the number 777. Thus, the number of possible distinct permutations can be calculated by:

13!2!⋅2!⋅3!⋅5!=2,162,160\displaystyle \frac {13! }{2!\cdot 2!\cdot 3!\cdot 5! }= 2,162,160​2!⋅2!⋅3!⋅5!​​13!​​=2,162,160

This logic can be applied to problems involving anagrams of given words. 

Example: Consider how many distinct ways you can order the letters of the word "waterfall."

The word waterfall consists of 999 letters in total, so n=9n=9n=9. The letter "a" appears twice, giving a value of 222 for n1n_{1}n​1​​. Similarly, the letter "l" appears twice, yielding n2=2n_{2} = 2n​2​​=2. Thus, the number of distinct permutations for the letters in "waterfall" can be calculated as:

9!2!⋅2!=90,720\displaystyle \frac {9! }{2!\cdot 2!}= 90,720​2!⋅2!​​9!​​=90,720

[ edit ]
Edit this content
Prev Concept
Permutations of Distinguishable Objects
Combinations
Next Concept
Subjects
  • Accounting
  • Algebra
  • Art History
  • Biology
  • Business
  • Calculus
  • Chemistry
  • Communications
  • Economics
  • Finance
  • Management
  • Marketing
  • Microbiology
  • Physics
  • Physiology
  • Political Science
  • Psychology
  • Sociology
  • Statistics
  • U.S. History
  • World History
  • Writing

Except where noted, content and user contributions on this site are licensed under CC BY-SA 4.0 with attribution required.