1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting permutations of a string with repeating characters

  1. Mar 7, 2016 #1

    squelch

    User Avatar
    Gold Member

    The problem statement:

    How many five-letter strings of capital letters have a letter repeated twice in a row? For example, include ABCCA and AAABC and ABBCC but not ABCAD.

    The attempt at a solution:

    • First, lets break down how we would perform the selection of a string that meets the question's criteria.
      • We select the first letter. There are 26 choices. This selection also triggers selection of the second letter, for which there is only one choice.
      • We then decide where in the five-position string to place these letters. There are four possible positions.
      • We then select for the other three letters. There are 26 possibilities for each letter, but we should exclude repeats. So the number of permutations for 26 letters to appear in three positions is P(26,3)=##\frac{26!}{(26-3)!}##
    • Then we combine the choices using the Product Rule.
      • [choices for first letter] * [choices for second letter] * [choices for position of first and second letter] * [permutations for remaining letters]
      • ##26*1*4*\frac{26!}{(26-3)!}=1622400##
    • We can then conclude that there are 1 622 400 such choices.
    I have been having a bit of trouble with this topic, so I'm essentially looking for a sanity check on this solution. I get the sense that I may have missed some key point.
     
  2. jcsd
  3. Mar 7, 2016 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Not sure I follow you reasoning, especially the part about "We then select for the other three letters ..."

    Hint: compute the number of 5 letter words that don't meet the question's criteria, meaning that no two adjacent letters are the same.
     
    Last edited: Mar 7, 2016
  4. Mar 7, 2016 #3

    squelch

    User Avatar
    Gold Member

    Okay, so I know that the total number of strings is 265.

    I consider a string where I'm selecting each character in turn to try to decide how many choices I get at each stage. If I want to construct a string where no two adjacent characters are the same, it seems that I could construct it in this way:
    [ 26 choices for character 1] * [25 choices for character 2] * [25 choices for character 3] * [25 choices for character 4] * [25 choices for character 5]
    ... so 26*254 choices to exclude? That doesn't seem intuitive.

    ninja edited to correct a horrible error
     
  5. Mar 7, 2016 #4

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Do you really have 26 choices for character 3 (and character 5)?
     
  6. Mar 7, 2016 #5

    squelch

    User Avatar
    Gold Member

    That was an awful error of mine that I thought I had corrected via edit fast enough, but alas, I did not.

    Corrected:
    [ 26 choices for character 1] * [25 choices for character 2] * [25 choices for character 3] * [25 choices for character 4] * [25 choices for character 5]
    ... so 26*25^4 choices to exclude?
     
  7. Mar 7, 2016 #6

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that is the result I also have : 265-26*254.
     
  8. Mar 7, 2016 #7

    squelch

    User Avatar
    Gold Member

    That was exceedingly helpful, thank you.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Counting permutations of a string with repeating characters
  1. Repeating sequence (Replies: 1)

  2. Repeated Eigenvalues (Replies: 1)

  3. Permutations ? (Replies: 3)

Loading...