Permutations and Combinations are described on many web sites (e.g.,
The Math Forum).
This article focuses on permutations and combinations with duplicates (multiples) --
as compared to unrestricted repetitions. The audience is high school mathematics
students or first year college algebra students.
First, the differences between duplicates and unrestricted repetitions for the purposes here.
An example of permutations with unrestricted repetitions is assigning letters and
numbers to automobile license plates.
For three letters and three digits in the English alphabet, the number of permutations is
26 x 26 x 26 x 10 x 10 x 10 = 17,576,000
since any letter or digit can be selected more than once.
An example of permutations with duplicates is arranging the letters in a word, such as
DAFFODIL. If all (eight) letter permutations is the goal, the number of permutations is
8! / (2! x 2!) = 10,080
However, if the count of four letter permutations is the goal, the answer is not
P(8, 4) / (2! x 2!) =
420 incorrect
The actual answer is
606
A simple counterexample to the formula above is the count of
two permutations with duplicates of the
letters in the word BABY.
Simple manual enumeration yields: AB, AY, BA, BB, BY, YA, YB -- seven total.
The formula P(4, 2) / 2! yields 6, which is not the correct answer.
This is the primary reason for this article -- in order to dispel this
misconception.
The solution involves enumerating generating functions -- beyond the scope of high
school algebra textbooks.
References: "Introduction to Combinatorial Analysis" by John Riordan,
though he doesn't use the duplicate terminology used here.
In combinatorial analysis these are now called permutations of
multisets.
See also
The Math Forum -
Four-Letter Combinations.
(Though the formula P(8, 7) / (2! x 2!) does work for seven letter permutations of DAFFODIL
also which gives the false impression that this is a general formula.)