title: Permutations excluding repeated characters
body: <p>I'm working on a Free Code Camp problem - <a href="http://www.freecodecamp.com/challenges/bonfire-no-repeats-please" rel="nofollow noreferrer">http://www.freecodecamp.com/challenges/bonfire-no-repeats-please</a></p>
  
  <p>The problem description is as follows -</p>
  
  <blockquote>
    <p>Return the number of total permutations of the provided string that
    don't have repeated consecutive letters. For example, 'aab' should
    return 2 because it has 6 total permutations, but only 2 of them don't
    have the same letter (in this case 'a') repeating.</p>
  </blockquote>
  
  <p>I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.</p>
  
  <p>But I have this gnawing feeling that I can solve this mathematically.</p>
  
  <p>First question then - Can I?</p>
  
  <p>Second question - If yes, what formula could I use?</p>
  
  <p>To elaborate further -</p>
  
  <p>The example given in the problem is "aab" which the site says has six possible permutations, with only two meeting the non-repeated character criteria:</p>
  
  <p>aab aba baa aab aba baa</p>
  
  <p>The problem sees each character as unique so maybe "aab" could better be described as "a1a2b"</p>
  
  <p>The tests for this problem are as follows (returning the number of permutations that meet the criteria)-</p>
  
  <pre><code>"aab" should return 2
  "aaa" should return 0
  "abcdefa" should return 3600
  "abfdefa" should return 2640
  "zzzzzzzz" should return 0
  </code></pre>
  
  <p>I have read through a lot of post about Combinatorics and Permutations and just seem to be digging a deeper hole for myself. But I really want to try to resolve this problem efficiently rather than brute force through an array of all possible permutations.</p>
  
  <p>I posted this question on math.stackexchange - <a href="https://math.stackexchange.com/q/1410184/264492">https://math.stackexchange.com/q/1410184/264492</a></p>
  
  <p>The maths to resolve the case where only one character is repeated is pretty trivial - Factorial of total number of characters minus number of spaces available multiplied by repeated characters.</p>
  
  <ul>
  <li>"aab" = 3! - 2! * 2! = 2 </li>
  <li>"abcdefa" = 7! - 6! * 2! = 3600</li>
  </ul>
  
  <p>But trying to figure out the formula for the instances where more than one character is repeated has eluded me. e.g. "abfdefa"</p>