The Central Idea
In the previous lesson, every selected object could be used at most once. Now suppose a three-character code is formed from the symbols
\[ A,\ B,\ C,\ D \]and repetition is allowed.
Each position has \(4\) choices:
\[ 4\cdot4\cdot4=4^3=64. \]The code
\[ ABA \]is now allowed because \(A\) may be used more than once.
Two Meanings of Repetition
The phrase permutations with repetition is used for two related but different counting situations.
- Repeated selection is allowed: an available symbol or object may be chosen again for another position.
- Repeated objects are already present: some objects are identical, so exchanging identical copies does not create a new arrangement.
These situations use different formulas and should not be confused.
Case 1: Repetition Is Allowed during Selection
Suppose \(n\) symbols are available and \(r\) ordered positions are filled. If each symbol may be reused, every position has \(n\) choices.
By the multiplication principle,
\[ \underbrace{n\cdot n\cdot n\cdots n}_{r\text{ factors}} = n^r. \]Therefore,
\[ \boxed{\text{ordered selections with repetition allowed}=n^r}. \]Why the Count Is \(n^r\)
Without repetition, the number of choices decreases:
\[ n,\ n-1,\ n-2,\ldots \]With repetition allowed, using one object does not remove it from future positions.
Therefore, the number of choices remains
\[ n,\ n,\ n,\ldots,n. \]For \(r\) positions, the product is
\[ \boxed{n^r}. \]Example: Four-Digit PINs
A four-digit PIN uses the digits \(0\) through \(9\), and digits may repeat.
Each of the four positions has \(10\) choices.
\[ 10\cdot10\cdot10\cdot10=10^4. \]Therefore,
\[ \boxed{10^4=10000} \]PINs are possible.
Example: Three-Letter Codes
Suppose a three-letter code is formed from \(26\) letters, and letters may repeat.
Each position has \(26\) choices:
\[ 26^3. \]Therefore,
\[ \boxed{26^3=17576} \]codes are possible.
Example: Outcomes of Repeated Trials
A six-sided die is rolled four times.
Each roll has \(6\) possible outcomes, and a face may occur more than once.
The ordered outcome sequence has
\[ 6^4 \]possibilities.
\[ \boxed{6^4=1296}. \]Example: Binary Strings
A binary string of length \(8\) uses the symbols \(0\) and \(1\).
Each of the eight positions has two choices.
\[ 2^8. \]Thus,
\[ \boxed{2^8=256} \]binary strings of length \(8\) exist.
Repetition Allowed Does Not Mean Order Is Ignored
The sequences
\[ ABC \]and
\[ CBA \]are still different because their orders differ.
Allowing repetition changes which symbols may appear again. It does not remove the importance of position.
Comparing With and Without Repetition
Suppose \(5\) symbols are available for three ordered positions.
Without repetition:
\[ P(5,3)=5\cdot4\cdot3=60. \]With repetition allowed:
\[ 5^3=125. \]Allowing symbols to be reused increases the number of possible outcomes.
Restriction: No Leading Zero
Repetition may be allowed while some positions still have restrictions.
Suppose a three-digit number is formed using the digits \(0\) through \(9\), repetition is allowed, but the first digit cannot be \(0\).
The first position has \(9\) choices.
The next two positions each have \(10\) choices.
\[ 9\cdot10\cdot10=\boxed{900}. \]We do not use \(10^3\) because the first position is restricted.
Restrictions Override the Shortcut
The expression \(n^r\) applies when every one of the \(r\) positions has exactly \(n\) available choices.
If different positions have different numbers of legal choices, use the multiplication principle directly:
\[ c_1c_2c_3\cdots c_r. \]The repeated-choice formula is a convenient special case of that principle.
Example: Password Structure
Suppose a password contains two letters followed by three digits. Repetition is allowed.
Each letter position has \(26\) choices, and each digit position has \(10\) choices.
\[ 26\cdot26\cdot10\cdot10\cdot10. \]Therefore,
\[ \boxed{26^2\cdot10^3=676000}. \]Example: At Least One Position Has a Special Rule
A four-character code uses digits \(0\) through \(9\), repetition is allowed, and the first character must be even.
The first position can be
\[ 0,2,4,6,8, \]so it has \(5\) choices.
Each remaining position has \(10\) choices.
\[ 5\cdot10^3=\boxed{5000}. \]Case 2: Repeated Objects Are Already Present
A different kind of repetition occurs when some objects are identical.
Consider the letters in
\[ \text{BOOK}. \]There are \(4\) positions, but the two \(O\)'s are indistinguishable.
If we temporarily pretend the two \(O\)'s are distinct, we would count
\[ 4!=24 \]arrangements.
But exchanging the two \(O\)'s does not create a new visible word.
Why Identical Objects Cause Overcounting
Label the two identical \(O\)'s temporarily as
\[ O_1,\qquad O_2. \]The arrangements
\[ BO_1O_2K \]and
\[ BO_2O_1K \]are counted separately if the labels are kept.
Once the labels are removed, both become
\[ BOOK. \]Every visible arrangement has therefore been counted \(2!\) times.
The Repeated-Object Formula
Suppose \(n\) objects are arranged, with repeated types occurring in groups of sizes
\[ n_1,n_2,\ldots,n_k, \]where
\[ n_1+n_2+\cdots+n_k=n. \]The number of distinguishable arrangements is
\[ \boxed{\frac{n!}{n_1!n_2!\cdots n_k!}}. \]Why We Divide by Repeated-Object Factorials
If all \(n\) objects were distinct, there would be
\[ n! \]arrangements.
But the first group of \(n_1\) identical objects can be permuted internally in \(n_1!\) ways without changing the visible arrangement.
Likewise, the next repeated group contributes an overcounting factor of \(n_2!\), and so on.
Dividing by all such internal rearrangements gives
\[ \boxed{\frac{n!}{n_1!n_2!\cdots n_k!}}. \]Example: Arrangements of BOOK
The word BOOK has \(4\) letters:
\[ B,\ O,\ O,\ K. \]The letter \(O\) appears twice.
Therefore,
\[ \frac{4!}{2!} = \frac{24}{2} = \boxed{12}. \]There are \(12\) distinguishable arrangements.
Example: Arrangements of LEVEL
The word LEVEL has \(5\) letters.
The letter \(L\) appears twice, and the letter \(E\) appears twice.
Therefore,
\[ \frac{5!}{2!\,2!} = \frac{120}{4} = \boxed{30}. \]Example: Arrangements of MISSISSIPPI
The word MISSISSIPPI contains \(11\) letters.
Their multiplicities are:
- \(M\): \(1\);
- \(I\): \(4\);
- \(S\): \(4\);
- \(P\): \(2\).
Therefore, the number of distinguishable arrangements is
\[ \boxed{\frac{11!}{4!\,4!\,2!}}. \]Numerically,
\[ \frac{39916800}{24\cdot24\cdot2} = \boxed{34650}. \]Example: Colored Objects
Suppose \(7\) tiles are arranged in a row:
- \(3\) red tiles;
- \(2\) blue tiles;
- \(2\) green tiles.
Tiles of the same color are indistinguishable.
The number of distinguishable arrangements is
\[ \boxed{\frac{7!}{3!\,2!\,2!}}. \]Simplifying,
\[ \frac{5040}{6\cdot2\cdot2} = \boxed{210}. \]Example: Two Types of Identical Objects
Suppose \(8\) positions contain \(5\) identical black markers and \(3\) identical white markers.
The number of distinguishable arrangements is
\[ \frac{8!}{5!\,3!}. \]Therefore,
\[ \boxed{\frac{8!}{5!\,3!}=56}. \]Repeated-Object Permutations and Choosing Positions
The previous example can also be interpreted by choosing which \(3\) of the \(8\) positions contain the white markers.
Once those positions are chosen, all remaining positions must contain black markers.
This gives the same count:
\[ \frac{8!}{5!\,3!}=56. \]This connection will become especially important when combinations are introduced.
Repeated Selection versus Repeated Objects
These two models must remain separate.
If \(4\) symbols are available for \(3\) positions and symbols may be reused, the count is
\[ 4^3=64. \]If instead we arrange the multiset
\[ A,A,B,C, \]the count is
\[ \frac{4!}{2!}=12. \]One formula counts repeated choices. The other corrects overcounting caused by indistinguishable objects.
How to Identify the Correct Repetition Model
Ask what the word repetition means in the problem.
- If the same available choice may be selected again for another position, use repeated sequential choices.
- If several objects are already identical, use the distinguishable arrangement formula.
Repeated Choice Formula
When \(r\) ordered positions are filled independently from \(n\) available options, with reuse allowed,
\[ \boxed{n^r}. \]The exponent \(r\) counts the number of positions.
Repeated-Object Formula
When \(n\) total objects are arranged and identical groups have sizes \(n_1,n_2,\ldots,n_k\),
\[ \boxed{\frac{n!}{n_1!n_2!\cdots n_k!}}. \]The denominator removes rearrangements among identical copies.
Example: Three Coin Tosses
A coin is tossed three times.
Each toss has two outcomes:
\[ H,\ T. \]Outcomes may repeat, so the number of ordered sequences is
\[ 2^3=\boxed{8}. \]The eight sequences include
\[ HHH,\ HHT,\ HTH,\ HTT,\ THH,\ THT,\ TTH,\ TTT. \]Example: Exactly Two Heads
Now suppose three coin tosses must contain exactly two heads.
The multiset of outcomes is
\[ H,H,T. \]The number of distinct orderings is
\[ \frac{3!}{2!} = \boxed{3}. \]They are
\[ HHT,\ HTH,\ THH. \]This illustrates how the repeated-choice and repeated-object viewpoints can appear in related problems.
Example: Exactly Three Successes in Five Trials
Suppose a sequence of five trials contains exactly three successes \(S\) and two failures \(F\).
The sequence consists of the multiset
\[ S,S,S,F,F. \]The number of distinct orderings is
\[ \frac{5!}{3!\,2!} = \boxed{10}. \]This structure will later connect directly to binomial coefficients.
Example: Repeated Digits with a Fixed Multiset
How many distinct six-digit strings can be formed using exactly
\[ 1,1,1,2,2,3? \]There are \(6\) total positions, with three \(1\)'s and two \(2\)'s.
Therefore,
\[ \frac{6!}{3!\,2!} = \frac{720}{12} = \boxed{60}. \]Repeated Objects with a Position Restriction
Restrictions can be combined with repeated-object arrangements.
Suppose the letters of BOOK are arranged, but the first letter must be \(B\).
Fix \(B\) in the first position. The remaining letters are
\[ O,O,K. \]Their distinguishable arrangements are
\[ \frac{3!}{2!} = \boxed{3}. \]Example: A Repeated Letter Must Be First
Arrange the letters of LEVEL so that the first letter is \(L\).
After fixing one \(L\), the remaining letters are
\[ L,E,E,V. \]The two \(E\)'s are identical, so the remaining arrangements total
\[ \frac{4!}{2!} = \boxed{12}. \]Example: A Specific Type Cannot Be First
Consider the multiset
\[ A,A,B,B,C. \]How many distinct arrangements do not begin with \(C\)?
Count all arrangements:
\[ \frac{5!}{2!\,2!}=30. \]Count arrangements beginning with \(C\). Fix \(C\), leaving
\[ A,A,B,B. \]These can be arranged in
\[ \frac{4!}{2!\,2!}=6 \]ways.
Therefore,
\[ 30-6=\boxed{24}. \]Repeated Objects and Symmetry
Identical objects create a form of symmetry.
Swapping identical copies changes the temporary labels but not the visible arrangement.
Dividing by the factorial of each repeated multiplicity removes this invisible rearrangement symmetry.
This same idea will reappear later in the section on symmetry and overcounting.
Why the Denominator Is a Product
Suppose there are \(3\) identical red objects and \(2\) identical blue objects.
The red objects can be relabeled internally in
\[ 3! \]ways without changing the visible arrangement.
Independently, the blue objects can be relabeled in
\[ 2! \]ways.
Together, each visible arrangement is overcounted
\[ 3!\cdot2! \]times.
Therefore, we divide \(5!\) by \(3!2!\).
All Objects Identical
Suppose all \(n\) objects are identical.
The formula gives
\[ \frac{n!}{n!}=1. \]This is correct: arranging identical objects cannot produce more than one visible ordering.
\[ \boxed{1}. \]No Objects Repeated
If every object is distinct, every repeated-group size is \(1\).
Since
\[ 1!=1, \]the repeated-object formula becomes
\[ \frac{n!}{1!\,1!\cdots1!}=n!. \]Thus ordinary permutations are recovered as a special case.
Connection to Multinomial Coefficients
The expression
\[ \frac{n!}{n_1!n_2!\cdots n_k!} \]is called a multinomial coefficient when
\[ n_1+n_2+\cdots+n_k=n. \]It counts arrangements of repeated categories and will later connect to multisets and the multinomial theorem.
Connection to Binomial Coefficients
If there are only two object types, with \(r\) objects of one type and \(n-r\) of the other, the formula becomes
\[ \frac{n!}{r!(n-r)!}. \]This is exactly the binomial coefficient
\[ \binom{n}{r}. \]The upcoming combination lesson will explain why these interpretations are equivalent.
Choosing Positions for Identical Objects
Suppose a string of length \(6\) contains exactly two \(A\)'s and four \(B\)'s.
Once the two positions for \(A\) are chosen, every remaining position must contain \(B\).
The number of strings is
\[ \frac{6!}{2!\,4!} = \boxed{15}. \]This is simultaneously a repeated-object permutation and a combination count.
Example: Ternary Strings with Fixed Counts
How many length-\(7\) strings contain exactly three \(0\)'s, two \(1\)'s, and two \(2\)'s?
The total number of positions is \(7\), with multiplicities
\[ 3,\ 2,\ 2. \]Therefore,
\[ \frac{7!}{3!\,2!\,2!} = \boxed{210}. \]Example: Repeated Selections with a Required Symbol
Four-character strings are formed from \(A,B,C\), with repetition allowed. How many begin with \(A\)?
The first position is fixed.
Each of the remaining three positions has \(3\) choices.
\[ 3^3=\boxed{27}. \]Example: Repeated Selections with a Forbidden Symbol
Five-character strings are formed from six symbols, but one particular symbol may not be used.
That leaves \(5\) available symbols for each position.
\[ 5^5=\boxed{3125}. \]Example: Repeated Selections with Different Position Types
A code contains one letter, two digits, and one letter, in that order. Repetition is allowed.
The counts by position are
\[ 26,\ 10,\ 10,\ 26. \]Therefore,
\[ 26^2\cdot10^2 = \boxed{67600}. \]Common Error: Using \(n^r\) for Identical Objects
The expression \(n^r\) counts repeated choices from \(n\) available options across \(r\) ordered positions.
It does not count arrangements of a fixed multiset such as
\[ A,A,B,B. \]For that multiset, the correct count is
\[ \frac{4!}{2!\,2!} = \boxed{6}. \]Common Error: Using the Repeated-Object Formula for Reusable Choices
If a four-digit PIN may use any digit \(0\) through \(9\) repeatedly, there is no fixed number of copies of each digit.
Therefore, the repeated-object formula does not apply.
Each position has \(10\) choices:
\[ \boxed{10^4=10000}. \]Common Error: Forgetting to Divide for Every Repeated Type
The word LEVEL contains two \(L\)'s and two \(E\)'s.
Dividing only by \(2!\) for the \(L\)'s gives
\[ \frac{5!}{2!}=60, \]which still overcounts exchanges of the two \(E\)'s.
The correct count is
\[ \boxed{\frac{5!}{2!\,2!}=30}. \]Common Error: Dividing by the Number of Repeated Types
If three objects are identical, the overcounting factor is not \(3\).
Those three identical copies can be internally permuted in
\[ 3!=6 \]ways.
Therefore, a multiplicity of \(3\) contributes a denominator factor of
\[ \boxed{3!}. \]Common Error: Forgetting Order in Repeated Selection
The strings
\[ AAB \]and
\[ ABA \]are different ordered outcomes.
Repetition allowed does not make order irrelevant.
Common Error: Ignoring Position Restrictions
If a repeated-choice problem includes a position restriction, not every position necessarily has \(n\) choices.
For a three-digit number using digits \(0\) through \(9\), the first position has only \(9\) choices.
Therefore, with repetition allowed,
\[ 9\cdot10\cdot10=\boxed{900}, \]not \(10^3\).
A Reliable Procedure for Repeated Selection
- Identify the ordered positions.
- Determine the number of legal choices for each position.
- Confirm that choices may be reused.
- If every position has the same \(n\) choices, use \(n^r\).
- If position restrictions differ, multiply the actual choice counts.
- Check whether order matters.
A Reliable Procedure for Repeated Objects
- Count the total number \(n\) of objects.
- Identify each group of indistinguishable objects.
- Record the multiplicities \(n_1,n_2,\ldots,n_k\).
- Verify that \(n_1+n_2+\cdots+n_k=n\).
- Start with \(n!\), as though every object were distinct.
- Divide by \(n_i!\) for every repeated group.
- Apply any position restrictions separately.
Example: Full Repeated-Selection Workflow
A five-character code uses \(8\) available symbols, and symbols may repeat.
There are \(5\) ordered positions.
Each position has \(8\) choices.
Therefore,
\[ 8^5=\boxed{32768}. \]Example: Full Repeated-Object Workflow
Count the distinguishable arrangements of
\[ A,A,A,B,B,C,C. \]There are \(7\) total objects.
The repeated multiplicities are
\[ 3,\ 2,\ 2. \]Therefore,
\[ \frac{7!}{3!\,2!\,2!}. \]Simplifying,
\[ \frac{5040}{6\cdot2\cdot2} = \boxed{210}. \]Practice 1: Repeated Digit Choices
How many five-digit strings can be formed from the digits \(0\) through \(9\) if repetition is allowed?
Practice 2: Repeated Letter Choices
How many four-letter strings can be formed from \(6\) available letters if repetition is allowed?
Practice 3: Leading-Zero Restriction
How many four-digit numbers can be formed using the digits \(0\) through \(9\) if repetition is allowed?
Practice 4: Repeated Objects
How many distinguishable arrangements can be formed from
\[ A,A,B,B,C? \]Practice 5: Word Arrangement
How many distinguishable arrangements are there of the letters in
\[ \text{BANANA}? \]Practice 6: Colored Tiles
Eight tiles consist of \(4\) identical red tiles, \(3\) identical blue tiles, and \(1\) green tile. How many distinguishable arrangements are possible?
Practice 7: Fixed Repeated-Choice Position
Five-character strings are formed from \(A,B,C,D\), repetition is allowed, and the first character must be \(A\). How many strings are possible?
Practice 8: Fixed Repeated Object
How many arrangements of the letters in BOOK begin with \(B\)?
Practice 9: Exactly Two Successes
How many length-\(6\) sequences contain exactly two \(S\)'s and four \(F\)'s?
Practice 10: Identify the Model
A student says that the number of distinguishable arrangements of
\[ A,A,B,C \]is
\[ 3^4=81. \]Explain why this is the wrong repetition model and give the correct count.
Practice Answers
Practice 1
Each of five positions has \(10\) choices:
\[ \boxed{10^5=100000}. \]Practice 2
\[ \boxed{6^4=1296}. \]Practice 3
The first digit has \(9\) choices, and the remaining three positions each have \(10\) choices:
\[ 9\cdot10^3=\boxed{9000}. \]Practice 4
There are \(5\) total objects, with two \(A\)'s and two \(B\)'s:
\[ \frac{5!}{2!\,2!} = \frac{120}{4} = \boxed{30}. \]Practice 5
BANANA contains \(6\) letters, with \(3\) \(A\)'s and \(2\) \(N\)'s:
\[ \frac{6!}{3!\,2!} = \frac{720}{12} = \boxed{60}. \]Practice 6
\[ \frac{8!}{4!\,3!} = \frac{40320}{24\cdot6} = \boxed{280}. \]Practice 7
The first position is fixed. Each of the remaining four positions has \(4\) choices:
\[ \boxed{4^4=256}. \]Practice 8
Fix \(B\). The remaining letters are \(O,O,K\):
\[ \frac{3!}{2!} = \boxed{3}. \]Practice 9
Arrange two \(S\)'s and four \(F\)'s:
\[ \frac{6!}{2!\,4!} = \boxed{15}. \]Practice 10
The expression \(3^4\) would count four independent selections from three reusable symbols.
Here the multiset is fixed: \(A,A,B,C\).
There are \(4\) objects with two identical \(A\)'s, so
\[ \boxed{\frac{4!}{2!}=12}. \]What to Remember
Repetition appears in two major forms.
When the same choice may be reused in each of \(r\) ordered positions and every position has \(n\) choices,
\[ \boxed{n^r}. \]When a fixed collection of \(n\) objects contains identical groups with multiplicities \(n_1,n_2,\ldots,n_k\),
\[ \boxed{\frac{n!}{n_1!n_2!\cdots n_k!}}. \]The first formula counts repeated choices. The second removes overcounting caused by indistinguishable objects.
The most important habit is to identify which type of repetition the problem actually contains before choosing a formula.
Where We Go Next
Linear arrangements are not the only way objects can be ordered. If objects are arranged around a circle, rotations can represent the same relative arrangement and ordinary factorial counting overcounts the result.
The next lesson, Circular Permutations, develops counting methods for arrangements around circles and other rotational settings.