Permutations excluding repeated characters












1












$begingroup$


I'm working on a Free Code Camp problem - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please



The problem description is as follows -




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.




I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.



But I have this gnawing feeling that I can solve this mathematically.



First question then - Can I?



Second question - If yes, what formula can I use?



To elaborate further -



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:



aab aba baa aab aba baa



The problem sees each character as unique so maybe "aab" could better be described as "a1a2b"



The tests for this problem are as follows (returning the number of permutations that meet the criteria)-




  • "aab" should return 2

  • "aaa" should return 0

  • "abcdefa" should return 3600

  • "abfdefa" should return 2640

  • "zzzzzzzz" should return 0


I have read through the following posts that have been really helpful in that they have convinced me I should be able to do this mathematically but I'm still in the dark as to how to apply their ideas to my particular problem. - Number of permutations in a word ignoring the consecutive repeated characters and https://answers.yahoo.com/question/index?qid=20110916091008AACH7vf










share|cite|improve this question











$endgroup$

















    1












    $begingroup$


    I'm working on a Free Code Camp problem - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please



    The problem description is as follows -




    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.




    I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.



    But I have this gnawing feeling that I can solve this mathematically.



    First question then - Can I?



    Second question - If yes, what formula can I use?



    To elaborate further -



    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:



    aab aba baa aab aba baa



    The problem sees each character as unique so maybe "aab" could better be described as "a1a2b"



    The tests for this problem are as follows (returning the number of permutations that meet the criteria)-




    • "aab" should return 2

    • "aaa" should return 0

    • "abcdefa" should return 3600

    • "abfdefa" should return 2640

    • "zzzzzzzz" should return 0


    I have read through the following posts that have been really helpful in that they have convinced me I should be able to do this mathematically but I'm still in the dark as to how to apply their ideas to my particular problem. - Number of permutations in a word ignoring the consecutive repeated characters and https://answers.yahoo.com/question/index?qid=20110916091008AACH7vf










    share|cite|improve this question











    $endgroup$















      1












      1








      1


      1



      $begingroup$


      I'm working on a Free Code Camp problem - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please



      The problem description is as follows -




      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.




      I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.



      But I have this gnawing feeling that I can solve this mathematically.



      First question then - Can I?



      Second question - If yes, what formula can I use?



      To elaborate further -



      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:



      aab aba baa aab aba baa



      The problem sees each character as unique so maybe "aab" could better be described as "a1a2b"



      The tests for this problem are as follows (returning the number of permutations that meet the criteria)-




      • "aab" should return 2

      • "aaa" should return 0

      • "abcdefa" should return 3600

      • "abfdefa" should return 2640

      • "zzzzzzzz" should return 0


      I have read through the following posts that have been really helpful in that they have convinced me I should be able to do this mathematically but I'm still in the dark as to how to apply their ideas to my particular problem. - Number of permutations in a word ignoring the consecutive repeated characters and https://answers.yahoo.com/question/index?qid=20110916091008AACH7vf










      share|cite|improve this question











      $endgroup$




      I'm working on a Free Code Camp problem - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please



      The problem description is as follows -




      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.




      I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.



      But I have this gnawing feeling that I can solve this mathematically.



      First question then - Can I?



      Second question - If yes, what formula can I use?



      To elaborate further -



      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:



      aab aba baa aab aba baa



      The problem sees each character as unique so maybe "aab" could better be described as "a1a2b"



      The tests for this problem are as follows (returning the number of permutations that meet the criteria)-




      • "aab" should return 2

      • "aaa" should return 0

      • "abcdefa" should return 3600

      • "abfdefa" should return 2640

      • "zzzzzzzz" should return 0


      I have read through the following posts that have been really helpful in that they have convinced me I should be able to do this mathematically but I'm still in the dark as to how to apply their ideas to my particular problem. - Number of permutations in a word ignoring the consecutive repeated characters and https://answers.yahoo.com/question/index?qid=20110916091008AACH7vf







      permutations factorial






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Apr 13 '17 at 12:19









      Community

      1




      1










      asked Aug 26 '15 at 11:17









      John BehanJohn Behan

      1063




      1063






















          2 Answers
          2






          active

          oldest

          votes


















          0












          $begingroup$

          Hint: Let's assume you have 15 positions and you need to distribute the letter a $5$ times. Then you can achieve this in the following way: Distribute the letter "a" 5 times on 11 positions. Now set an empty space between every pair of consecutive letters.



          A specific example: The first distribution might yield

          -a-aaa--a--

          Adding the spaces [here denoted by an underscore]:

          -a_-a_a_a_--a--



          In the next step you can distribute the next letter on the remaining 10 positions etc..






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            OK, I'll ponder this one and get back tomorrow :) Thanks
            $endgroup$
            – John Behan
            Aug 26 '15 at 15:30










          • $begingroup$
            I figure you're pushing me towards considering the blank spaces between the letters.
            $endgroup$
            – John Behan
            Aug 27 '15 at 0:57










          • $begingroup$
            I figure you're pushing me towards considering the blank spaces between the letters. However I can't see a way to use this in a formula for counting the permutations without consecutive letters. When I try to think of how to count these using anything but the most trivial example ("aab") I can't see a pattern.
            $endgroup$
            – John Behan
            Aug 27 '15 at 1:14










          • $begingroup$
            Have you already understood how this construction yields all arrangements? Counting them is simple combinatorics.
            $endgroup$
            – Dominik
            Aug 27 '15 at 3:03










          • $begingroup$
            I've come up with this solution for the problem "abcdefa" In total there are 7! possible permutations = 5040 But, with the two 'a' characters beside each other, there are 6! possible permututions = 720 As both 'a' characters are seen as unique, I then double this result, which gives me 1440 5040 - 1440 gives a result of 3600 I've started working on the other problems 'aab' and 'abfdefa' to see if I can find a pattern. Am I on the right track?
            $endgroup$
            – John Behan
            Aug 27 '15 at 7:09



















          0












          $begingroup$

          Interesting problem indeed: I am keen to try and see what is possible to fix down.



          Premise



          So we are considering the words, formed from the alphabet
          $$
          alpha = left{ {1,2,, cdots ,,n} right}
          $$
          with total number of repetitions of each character strictly correspondending to the vector
          $$
          {bf r} = left( {r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} } right)
          $$
          and thus having length equal to
          $$
          R = sumlimits_{1 le ,k, le ,n} {r_{,k} }
          $$



          With $r_k=0$ we will indicate that there is no occurence of the character $k$, which is a case
          useful to consider in the following.
          Of course, there is no loss of generality in permuting the vector $bf r$, so that we may assume that its
          components are arranged ,e.g., as non-increasing; then $a$ and $b$ shall also be permuted accordingly.



          So
          $$
          {bf r}_{,{bf n}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} ,0,, cdots ,0} right)quad Rightarrow quad {bf r}_{,{bf m}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} } right)
          $$



          The total number of words that can be formed from a given $bf r$ (the alphabet is implicit in its dimension), by definition of Multinomial is:
          $$
          N_w ({bf r}) = left( matrix{
          R cr
          r_{,1} ,r_{,2} ,, cdots ,,r_{,n} cr} right) = {{R!} over {r_{,1} !r_{,2} !, cdots ,r_{,n} !}}
          $$



          Our focus is on the words that do not have equal contiguous characters.



          The Multinomial approach



          Consider the words in which one specific character (wlog, the first) does not appear contiguously,
          i.e. in runs of not more than $1$ in length, while the others can be placed in whatever way.

          Then, as explained in this post, their number will be:
          $$ bbox[lightyellow] {
          eqalign{
          & N_{,w1} (r_{,1} ,R) = left( matrix{ R - r_{,1} cr
          r_{,2} ,, cdots ,,r_{,n} cr} right)N_b (r_{,1} ,1,R - r_{,1} + 1) = left( matrix{
          R - r_{,1} cr
          r_{,2} ,, cdots ,,r_{,n} cr} right)sumlimits_{left( {0, le } right),,j,,left( { le ,r_{,1} ,/2} right)} {left( { - 1} right)^j left( matrix{
          R - r_{,1} + 1 cr j cr} right)left( matrix{ R - 2j cr r_{,1} - 2,j cr} right)} = cr
          & = left( matrix{ R - r_{,1} cr r_{,2} ,, cdots ,,r_{,n} cr} right)left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right)
          = left( matrix{ R cr r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} cr} right)
          left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right);mathop /limits_{} ;
          left( matrix{ R cr r_{,1} cr} right) cr}
          tag{1} }$$



          If the other characters have repetition $1$, then clearly that is the number of words with no equal contiguous character.
          In this case $R=n+r_{1}-1$
          $$ bbox[lightyellow] {
          eqalign{
          & N_{,w1} left( {r_{,1} ,,1,, cdots ,1} right) = left( matrix{
          R cr
          r_{,1} ,1,, cdots ,,1 cr} right)left( matrix{
          R - r_{,1} + 1 cr
          r_{,1} cr} right);mathop /limits_{} ;left( matrix{
          R cr
          r_{,1} cr} right) = cr
          & = left( {R - r_{,1} } right)!left( matrix{
          R - r_{,1} + 1 cr
          r_{,1} cr} right) = left( {n - 1} right)!left( matrix{
          n cr
          r_{,1} cr} right) cr}
          tag{2} }$$



          For the examples you give
          $$
          eqalign{
          & a,a,bquad Rightarrow ;quad N_{,w1} = 1!left( matrix{
          2 cr
          2 cr} right) = 1 cr
          & a,a,b,c,d,e,fquad Rightarrow ;quad N_{,w1} = 5!left( matrix{
          6 cr
          2 cr} right) = 1800 cr}
          $$
          so, with your method of counting, you just have to multiply by $r_{1}!$.



          For the case of a general $bf {r}$, we could develop forward identity (1) and proceed by inclusion-exclusion, but looks cumbersome.

          Let's try instead to find an adequate recurrence.



          The recursive approach



          Definitions



          Let's call
          $$
          N_{,0} ({bf r},a,b)
          $$
          the N. of words with no equal contiguous character, with repetition vector $bf r$ (the alphabet is implicit in it)
          and with starting character $a$ and ending character $b$.



          We consider empty, and thus their number null, the words for which:

          - the starting and ending character do not pertain to the alphabet : $a notin alpha ,; vee ;b notin alpha $

          - any component of the repetition vector is negative : $exists k:r_{,k} < 0$

          - the start or the end character have null repetition : $r_{,a} = 0,; vee ;r_{,b} = 0$

          - the dimension of $bf r$, i.e. of the alphabet, is null : $n<1$



          In this way, it is clear that the words with a given starting and ending character constitute a partition
          of the set of the considered words.



          Let's then indicate
          $$
          N_{,0} ({bf r}) = sumlimits_{1 le ,k,,j, le ,n} {N_{,0} ({bf r},k,j)}
          $$
          and put by definition that the number of empty words is 1
          $$
          N_{,0} ({bf 0}) = 1
          $$



          Also, we define the following vectors
          $$
          eqalign{
          & {bf u}_{,n} (a) = left( {delta _{,k,,a} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right];;left| {,1 le k le n} right.} right) cr
          & {bf u}_{,n} (a,b) = left( {delta _{,k,,a} + delta _{,k,,b} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right] + left[ {b = k} right];;left| {,1 le k le n} right.} right) cr
          & {bf u}_{,n} = left( {1;;left| {,1 le k le n} right.} right) cr}
          $$
          where $delta _{,k,,a} $ denotes the Kronecker delta and
          $[P]$ denotes the Iverson bracket.



          The starting cases



          Then, considering the simplest case of $R=1$, we have
          $$
          N_{,0} ({bf u}_{,n} (c),a,b) = left[ {a = b = c} right] = left[ {a = c} right]left[ {b = c} right]
          $$
          while for $R=2$
          $$
          N_{,0} ({bf u}_{,n} (c,d),a,b) = left[ {c ne d} right]left( {left[ {a = c} right]left[ {b = d} right] + left[ {a = d} right]left[ {b = c} right]} right)
          $$
          and for $R=3$
          $$
          N_{,0} ({bf u}_{,n} (c,d,e),a,b) = left[ {a ne b} right]left[ {left( {a,b} right) in 2{rm - permutation},{rm from},(c,d,e)} right]
          $$
          and finally for ${bf u}_{,n} $ ($R=n$)
          $$
          N_{,0} ({bf u}_{,n} ,a,b) = left[ {1 = n} right]left[ {a = b} right] + left[ {2 le n} right]left[ {a ne b} right]left( {n - 2} right)!
          $$



          The recursion



          Take a word (with no equal contiguous character) of length $2 le R$.

          We can divide it into two subwords of fixed length $R-S$ and $1 le S < R$.

          The end character of the first shall be different from the starting character of the second.

          Then we can part the repetition vector between them in all the ways, such that
          the sum of the components of the first is $R-S$ and that of the second is $S$.
          That means that $bf{r}$ is reparted into $bf{r-s}$ and $bf{s}$.
          Both vectors shall have at least one positive component. However, with the conditions
          established above $N_{,0} (mathbf{0},a,b) = 0quad left| {;1 leqslant n} right.$



          We can therefore write $N_{,0} (mathbf{r},a,b)$ as the following sum in $j,k,bf{s}$
          $$ bbox[lightyellow] {
          begin{gathered}
          N_{,0} (mathbf{r},a,b) = left[ {1 = R} right]left[ {a = b = k:r_{,k} ne 0} right] + hfill \
          + left[ {2 leqslant R} right]sumlimits_{left{ begin{subarray}{l}
          1 leqslant ,k ne ,j, leqslant ,n \
          mathbf{0}, leqslant ,mathbf{s}, leqslant ,mathbf{r}, \
          0 < ,sumlimits_l {s_{,l} } = S, < ,R
          end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k);N_{,0} (mathbf{s},j,b)} hfill \
          end{gathered}
          tag{3} }$$



          Then, for $S=1$ , (and $2 le R$), in particular, we have
          $$ bbox[lightyellow] {
          begin{gathered}
          N_{,0} (mathbf{r},a,b) = sumlimits_{left{ begin{subarray}{l}
          1 leqslant ,k ne ,j, leqslant ,n \
          mathbf{0} leqslant ,mathbf{s}, leqslant ,mathbf{r} \
          0 < sumlimits_l {s_{,l} } = 1, < ,R
          end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k)N_{,0} (mathbf{s},j,b)} = hfill \
          = sumlimits_{left{ begin{subarray}{l}
          1 leqslant ,k ne ,j, leqslant ,n \
          1 leqslant ,l, leqslant ,n \
          1 < ,R
          end{subarray} right.} {N_{,0} left( {left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k} right);N_{,0} left( {left( {0,, cdots ,1_{,left( l right)} ,, cdots ,,0} right),j,b} right)} = hfill \
          = sumlimits_{left{ begin{subarray}{l}
          1 leqslant ,k ne ,j, leqslant ,n \
          1 leqslant ,l, leqslant ,n \
          1 < ,R
          end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k);left[ {l = j = b} right]} = hfill \
          = sumlimits_{left{ begin{subarray}{l}
          1 leqslant ,k ne ,b, leqslant ,n \
          1 < ,R
          end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,b} - 1,, cdots ,,r_{,n} } right),a,k)} = hfill \
          = sumlimits_{1 leqslant ,k ne ,b, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} = hfill \
          = sumlimits_{1 leqslant ,k, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} - N_{,0} (mathbf{r} - mathbf{u}(b),a,b) hfill \
          end{gathered}
          tag{4} }$$



          which I checked to be correct against a dozen of cases.






          share|cite|improve this answer









          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1410184%2fpermutations-excluding-repeated-characters%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            0












            $begingroup$

            Hint: Let's assume you have 15 positions and you need to distribute the letter a $5$ times. Then you can achieve this in the following way: Distribute the letter "a" 5 times on 11 positions. Now set an empty space between every pair of consecutive letters.



            A specific example: The first distribution might yield

            -a-aaa--a--

            Adding the spaces [here denoted by an underscore]:

            -a_-a_a_a_--a--



            In the next step you can distribute the next letter on the remaining 10 positions etc..






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              OK, I'll ponder this one and get back tomorrow :) Thanks
              $endgroup$
              – John Behan
              Aug 26 '15 at 15:30










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters.
              $endgroup$
              – John Behan
              Aug 27 '15 at 0:57










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters. However I can't see a way to use this in a formula for counting the permutations without consecutive letters. When I try to think of how to count these using anything but the most trivial example ("aab") I can't see a pattern.
              $endgroup$
              – John Behan
              Aug 27 '15 at 1:14










            • $begingroup$
              Have you already understood how this construction yields all arrangements? Counting them is simple combinatorics.
              $endgroup$
              – Dominik
              Aug 27 '15 at 3:03










            • $begingroup$
              I've come up with this solution for the problem "abcdefa" In total there are 7! possible permutations = 5040 But, with the two 'a' characters beside each other, there are 6! possible permututions = 720 As both 'a' characters are seen as unique, I then double this result, which gives me 1440 5040 - 1440 gives a result of 3600 I've started working on the other problems 'aab' and 'abfdefa' to see if I can find a pattern. Am I on the right track?
              $endgroup$
              – John Behan
              Aug 27 '15 at 7:09
















            0












            $begingroup$

            Hint: Let's assume you have 15 positions and you need to distribute the letter a $5$ times. Then you can achieve this in the following way: Distribute the letter "a" 5 times on 11 positions. Now set an empty space between every pair of consecutive letters.



            A specific example: The first distribution might yield

            -a-aaa--a--

            Adding the spaces [here denoted by an underscore]:

            -a_-a_a_a_--a--



            In the next step you can distribute the next letter on the remaining 10 positions etc..






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              OK, I'll ponder this one and get back tomorrow :) Thanks
              $endgroup$
              – John Behan
              Aug 26 '15 at 15:30










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters.
              $endgroup$
              – John Behan
              Aug 27 '15 at 0:57










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters. However I can't see a way to use this in a formula for counting the permutations without consecutive letters. When I try to think of how to count these using anything but the most trivial example ("aab") I can't see a pattern.
              $endgroup$
              – John Behan
              Aug 27 '15 at 1:14










            • $begingroup$
              Have you already understood how this construction yields all arrangements? Counting them is simple combinatorics.
              $endgroup$
              – Dominik
              Aug 27 '15 at 3:03










            • $begingroup$
              I've come up with this solution for the problem "abcdefa" In total there are 7! possible permutations = 5040 But, with the two 'a' characters beside each other, there are 6! possible permututions = 720 As both 'a' characters are seen as unique, I then double this result, which gives me 1440 5040 - 1440 gives a result of 3600 I've started working on the other problems 'aab' and 'abfdefa' to see if I can find a pattern. Am I on the right track?
              $endgroup$
              – John Behan
              Aug 27 '15 at 7:09














            0












            0








            0





            $begingroup$

            Hint: Let's assume you have 15 positions and you need to distribute the letter a $5$ times. Then you can achieve this in the following way: Distribute the letter "a" 5 times on 11 positions. Now set an empty space between every pair of consecutive letters.



            A specific example: The first distribution might yield

            -a-aaa--a--

            Adding the spaces [here denoted by an underscore]:

            -a_-a_a_a_--a--



            In the next step you can distribute the next letter on the remaining 10 positions etc..






            share|cite|improve this answer









            $endgroup$



            Hint: Let's assume you have 15 positions and you need to distribute the letter a $5$ times. Then you can achieve this in the following way: Distribute the letter "a" 5 times on 11 positions. Now set an empty space between every pair of consecutive letters.



            A specific example: The first distribution might yield

            -a-aaa--a--

            Adding the spaces [here denoted by an underscore]:

            -a_-a_a_a_--a--



            In the next step you can distribute the next letter on the remaining 10 positions etc..







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Aug 26 '15 at 11:34









            DominikDominik

            17.6k11945




            17.6k11945












            • $begingroup$
              OK, I'll ponder this one and get back tomorrow :) Thanks
              $endgroup$
              – John Behan
              Aug 26 '15 at 15:30










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters.
              $endgroup$
              – John Behan
              Aug 27 '15 at 0:57










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters. However I can't see a way to use this in a formula for counting the permutations without consecutive letters. When I try to think of how to count these using anything but the most trivial example ("aab") I can't see a pattern.
              $endgroup$
              – John Behan
              Aug 27 '15 at 1:14










            • $begingroup$
              Have you already understood how this construction yields all arrangements? Counting them is simple combinatorics.
              $endgroup$
              – Dominik
              Aug 27 '15 at 3:03










            • $begingroup$
              I've come up with this solution for the problem "abcdefa" In total there are 7! possible permutations = 5040 But, with the two 'a' characters beside each other, there are 6! possible permututions = 720 As both 'a' characters are seen as unique, I then double this result, which gives me 1440 5040 - 1440 gives a result of 3600 I've started working on the other problems 'aab' and 'abfdefa' to see if I can find a pattern. Am I on the right track?
              $endgroup$
              – John Behan
              Aug 27 '15 at 7:09


















            • $begingroup$
              OK, I'll ponder this one and get back tomorrow :) Thanks
              $endgroup$
              – John Behan
              Aug 26 '15 at 15:30










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters.
              $endgroup$
              – John Behan
              Aug 27 '15 at 0:57










            • $begingroup$
              I figure you're pushing me towards considering the blank spaces between the letters. However I can't see a way to use this in a formula for counting the permutations without consecutive letters. When I try to think of how to count these using anything but the most trivial example ("aab") I can't see a pattern.
              $endgroup$
              – John Behan
              Aug 27 '15 at 1:14










            • $begingroup$
              Have you already understood how this construction yields all arrangements? Counting them is simple combinatorics.
              $endgroup$
              – Dominik
              Aug 27 '15 at 3:03










            • $begingroup$
              I've come up with this solution for the problem "abcdefa" In total there are 7! possible permutations = 5040 But, with the two 'a' characters beside each other, there are 6! possible permututions = 720 As both 'a' characters are seen as unique, I then double this result, which gives me 1440 5040 - 1440 gives a result of 3600 I've started working on the other problems 'aab' and 'abfdefa' to see if I can find a pattern. Am I on the right track?
              $endgroup$
              – John Behan
              Aug 27 '15 at 7:09
















            $begingroup$
            OK, I'll ponder this one and get back tomorrow :) Thanks
            $endgroup$
            – John Behan
            Aug 26 '15 at 15:30




            $begingroup$
            OK, I'll ponder this one and get back tomorrow :) Thanks
            $endgroup$
            – John Behan
            Aug 26 '15 at 15:30












            $begingroup$
            I figure you're pushing me towards considering the blank spaces between the letters.
            $endgroup$
            – John Behan
            Aug 27 '15 at 0:57




            $begingroup$
            I figure you're pushing me towards considering the blank spaces between the letters.
            $endgroup$
            – John Behan
            Aug 27 '15 at 0:57












            $begingroup$
            I figure you're pushing me towards considering the blank spaces between the letters. However I can't see a way to use this in a formula for counting the permutations without consecutive letters. When I try to think of how to count these using anything but the most trivial example ("aab") I can't see a pattern.
            $endgroup$
            – John Behan
            Aug 27 '15 at 1:14




            $begingroup$
            I figure you're pushing me towards considering the blank spaces between the letters. However I can't see a way to use this in a formula for counting the permutations without consecutive letters. When I try to think of how to count these using anything but the most trivial example ("aab") I can't see a pattern.
            $endgroup$
            – John Behan
            Aug 27 '15 at 1:14












            $begingroup$
            Have you already understood how this construction yields all arrangements? Counting them is simple combinatorics.
            $endgroup$
            – Dominik
            Aug 27 '15 at 3:03




            $begingroup$
            Have you already understood how this construction yields all arrangements? Counting them is simple combinatorics.
            $endgroup$
            – Dominik
            Aug 27 '15 at 3:03












            $begingroup$
            I've come up with this solution for the problem "abcdefa" In total there are 7! possible permutations = 5040 But, with the two 'a' characters beside each other, there are 6! possible permututions = 720 As both 'a' characters are seen as unique, I then double this result, which gives me 1440 5040 - 1440 gives a result of 3600 I've started working on the other problems 'aab' and 'abfdefa' to see if I can find a pattern. Am I on the right track?
            $endgroup$
            – John Behan
            Aug 27 '15 at 7:09




            $begingroup$
            I've come up with this solution for the problem "abcdefa" In total there are 7! possible permutations = 5040 But, with the two 'a' characters beside each other, there are 6! possible permututions = 720 As both 'a' characters are seen as unique, I then double this result, which gives me 1440 5040 - 1440 gives a result of 3600 I've started working on the other problems 'aab' and 'abfdefa' to see if I can find a pattern. Am I on the right track?
            $endgroup$
            – John Behan
            Aug 27 '15 at 7:09











            0












            $begingroup$

            Interesting problem indeed: I am keen to try and see what is possible to fix down.



            Premise



            So we are considering the words, formed from the alphabet
            $$
            alpha = left{ {1,2,, cdots ,,n} right}
            $$
            with total number of repetitions of each character strictly correspondending to the vector
            $$
            {bf r} = left( {r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} } right)
            $$
            and thus having length equal to
            $$
            R = sumlimits_{1 le ,k, le ,n} {r_{,k} }
            $$



            With $r_k=0$ we will indicate that there is no occurence of the character $k$, which is a case
            useful to consider in the following.
            Of course, there is no loss of generality in permuting the vector $bf r$, so that we may assume that its
            components are arranged ,e.g., as non-increasing; then $a$ and $b$ shall also be permuted accordingly.



            So
            $$
            {bf r}_{,{bf n}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} ,0,, cdots ,0} right)quad Rightarrow quad {bf r}_{,{bf m}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} } right)
            $$



            The total number of words that can be formed from a given $bf r$ (the alphabet is implicit in its dimension), by definition of Multinomial is:
            $$
            N_w ({bf r}) = left( matrix{
            R cr
            r_{,1} ,r_{,2} ,, cdots ,,r_{,n} cr} right) = {{R!} over {r_{,1} !r_{,2} !, cdots ,r_{,n} !}}
            $$



            Our focus is on the words that do not have equal contiguous characters.



            The Multinomial approach



            Consider the words in which one specific character (wlog, the first) does not appear contiguously,
            i.e. in runs of not more than $1$ in length, while the others can be placed in whatever way.

            Then, as explained in this post, their number will be:
            $$ bbox[lightyellow] {
            eqalign{
            & N_{,w1} (r_{,1} ,R) = left( matrix{ R - r_{,1} cr
            r_{,2} ,, cdots ,,r_{,n} cr} right)N_b (r_{,1} ,1,R - r_{,1} + 1) = left( matrix{
            R - r_{,1} cr
            r_{,2} ,, cdots ,,r_{,n} cr} right)sumlimits_{left( {0, le } right),,j,,left( { le ,r_{,1} ,/2} right)} {left( { - 1} right)^j left( matrix{
            R - r_{,1} + 1 cr j cr} right)left( matrix{ R - 2j cr r_{,1} - 2,j cr} right)} = cr
            & = left( matrix{ R - r_{,1} cr r_{,2} ,, cdots ,,r_{,n} cr} right)left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right)
            = left( matrix{ R cr r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} cr} right)
            left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right);mathop /limits_{} ;
            left( matrix{ R cr r_{,1} cr} right) cr}
            tag{1} }$$



            If the other characters have repetition $1$, then clearly that is the number of words with no equal contiguous character.
            In this case $R=n+r_{1}-1$
            $$ bbox[lightyellow] {
            eqalign{
            & N_{,w1} left( {r_{,1} ,,1,, cdots ,1} right) = left( matrix{
            R cr
            r_{,1} ,1,, cdots ,,1 cr} right)left( matrix{
            R - r_{,1} + 1 cr
            r_{,1} cr} right);mathop /limits_{} ;left( matrix{
            R cr
            r_{,1} cr} right) = cr
            & = left( {R - r_{,1} } right)!left( matrix{
            R - r_{,1} + 1 cr
            r_{,1} cr} right) = left( {n - 1} right)!left( matrix{
            n cr
            r_{,1} cr} right) cr}
            tag{2} }$$



            For the examples you give
            $$
            eqalign{
            & a,a,bquad Rightarrow ;quad N_{,w1} = 1!left( matrix{
            2 cr
            2 cr} right) = 1 cr
            & a,a,b,c,d,e,fquad Rightarrow ;quad N_{,w1} = 5!left( matrix{
            6 cr
            2 cr} right) = 1800 cr}
            $$
            so, with your method of counting, you just have to multiply by $r_{1}!$.



            For the case of a general $bf {r}$, we could develop forward identity (1) and proceed by inclusion-exclusion, but looks cumbersome.

            Let's try instead to find an adequate recurrence.



            The recursive approach



            Definitions



            Let's call
            $$
            N_{,0} ({bf r},a,b)
            $$
            the N. of words with no equal contiguous character, with repetition vector $bf r$ (the alphabet is implicit in it)
            and with starting character $a$ and ending character $b$.



            We consider empty, and thus their number null, the words for which:

            - the starting and ending character do not pertain to the alphabet : $a notin alpha ,; vee ;b notin alpha $

            - any component of the repetition vector is negative : $exists k:r_{,k} < 0$

            - the start or the end character have null repetition : $r_{,a} = 0,; vee ;r_{,b} = 0$

            - the dimension of $bf r$, i.e. of the alphabet, is null : $n<1$



            In this way, it is clear that the words with a given starting and ending character constitute a partition
            of the set of the considered words.



            Let's then indicate
            $$
            N_{,0} ({bf r}) = sumlimits_{1 le ,k,,j, le ,n} {N_{,0} ({bf r},k,j)}
            $$
            and put by definition that the number of empty words is 1
            $$
            N_{,0} ({bf 0}) = 1
            $$



            Also, we define the following vectors
            $$
            eqalign{
            & {bf u}_{,n} (a) = left( {delta _{,k,,a} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right];;left| {,1 le k le n} right.} right) cr
            & {bf u}_{,n} (a,b) = left( {delta _{,k,,a} + delta _{,k,,b} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right] + left[ {b = k} right];;left| {,1 le k le n} right.} right) cr
            & {bf u}_{,n} = left( {1;;left| {,1 le k le n} right.} right) cr}
            $$
            where $delta _{,k,,a} $ denotes the Kronecker delta and
            $[P]$ denotes the Iverson bracket.



            The starting cases



            Then, considering the simplest case of $R=1$, we have
            $$
            N_{,0} ({bf u}_{,n} (c),a,b) = left[ {a = b = c} right] = left[ {a = c} right]left[ {b = c} right]
            $$
            while for $R=2$
            $$
            N_{,0} ({bf u}_{,n} (c,d),a,b) = left[ {c ne d} right]left( {left[ {a = c} right]left[ {b = d} right] + left[ {a = d} right]left[ {b = c} right]} right)
            $$
            and for $R=3$
            $$
            N_{,0} ({bf u}_{,n} (c,d,e),a,b) = left[ {a ne b} right]left[ {left( {a,b} right) in 2{rm - permutation},{rm from},(c,d,e)} right]
            $$
            and finally for ${bf u}_{,n} $ ($R=n$)
            $$
            N_{,0} ({bf u}_{,n} ,a,b) = left[ {1 = n} right]left[ {a = b} right] + left[ {2 le n} right]left[ {a ne b} right]left( {n - 2} right)!
            $$



            The recursion



            Take a word (with no equal contiguous character) of length $2 le R$.

            We can divide it into two subwords of fixed length $R-S$ and $1 le S < R$.

            The end character of the first shall be different from the starting character of the second.

            Then we can part the repetition vector between them in all the ways, such that
            the sum of the components of the first is $R-S$ and that of the second is $S$.
            That means that $bf{r}$ is reparted into $bf{r-s}$ and $bf{s}$.
            Both vectors shall have at least one positive component. However, with the conditions
            established above $N_{,0} (mathbf{0},a,b) = 0quad left| {;1 leqslant n} right.$



            We can therefore write $N_{,0} (mathbf{r},a,b)$ as the following sum in $j,k,bf{s}$
            $$ bbox[lightyellow] {
            begin{gathered}
            N_{,0} (mathbf{r},a,b) = left[ {1 = R} right]left[ {a = b = k:r_{,k} ne 0} right] + hfill \
            + left[ {2 leqslant R} right]sumlimits_{left{ begin{subarray}{l}
            1 leqslant ,k ne ,j, leqslant ,n \
            mathbf{0}, leqslant ,mathbf{s}, leqslant ,mathbf{r}, \
            0 < ,sumlimits_l {s_{,l} } = S, < ,R
            end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k);N_{,0} (mathbf{s},j,b)} hfill \
            end{gathered}
            tag{3} }$$



            Then, for $S=1$ , (and $2 le R$), in particular, we have
            $$ bbox[lightyellow] {
            begin{gathered}
            N_{,0} (mathbf{r},a,b) = sumlimits_{left{ begin{subarray}{l}
            1 leqslant ,k ne ,j, leqslant ,n \
            mathbf{0} leqslant ,mathbf{s}, leqslant ,mathbf{r} \
            0 < sumlimits_l {s_{,l} } = 1, < ,R
            end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k)N_{,0} (mathbf{s},j,b)} = hfill \
            = sumlimits_{left{ begin{subarray}{l}
            1 leqslant ,k ne ,j, leqslant ,n \
            1 leqslant ,l, leqslant ,n \
            1 < ,R
            end{subarray} right.} {N_{,0} left( {left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k} right);N_{,0} left( {left( {0,, cdots ,1_{,left( l right)} ,, cdots ,,0} right),j,b} right)} = hfill \
            = sumlimits_{left{ begin{subarray}{l}
            1 leqslant ,k ne ,j, leqslant ,n \
            1 leqslant ,l, leqslant ,n \
            1 < ,R
            end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k);left[ {l = j = b} right]} = hfill \
            = sumlimits_{left{ begin{subarray}{l}
            1 leqslant ,k ne ,b, leqslant ,n \
            1 < ,R
            end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,b} - 1,, cdots ,,r_{,n} } right),a,k)} = hfill \
            = sumlimits_{1 leqslant ,k ne ,b, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} = hfill \
            = sumlimits_{1 leqslant ,k, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} - N_{,0} (mathbf{r} - mathbf{u}(b),a,b) hfill \
            end{gathered}
            tag{4} }$$



            which I checked to be correct against a dozen of cases.






            share|cite|improve this answer









            $endgroup$


















              0












              $begingroup$

              Interesting problem indeed: I am keen to try and see what is possible to fix down.



              Premise



              So we are considering the words, formed from the alphabet
              $$
              alpha = left{ {1,2,, cdots ,,n} right}
              $$
              with total number of repetitions of each character strictly correspondending to the vector
              $$
              {bf r} = left( {r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} } right)
              $$
              and thus having length equal to
              $$
              R = sumlimits_{1 le ,k, le ,n} {r_{,k} }
              $$



              With $r_k=0$ we will indicate that there is no occurence of the character $k$, which is a case
              useful to consider in the following.
              Of course, there is no loss of generality in permuting the vector $bf r$, so that we may assume that its
              components are arranged ,e.g., as non-increasing; then $a$ and $b$ shall also be permuted accordingly.



              So
              $$
              {bf r}_{,{bf n}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} ,0,, cdots ,0} right)quad Rightarrow quad {bf r}_{,{bf m}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} } right)
              $$



              The total number of words that can be formed from a given $bf r$ (the alphabet is implicit in its dimension), by definition of Multinomial is:
              $$
              N_w ({bf r}) = left( matrix{
              R cr
              r_{,1} ,r_{,2} ,, cdots ,,r_{,n} cr} right) = {{R!} over {r_{,1} !r_{,2} !, cdots ,r_{,n} !}}
              $$



              Our focus is on the words that do not have equal contiguous characters.



              The Multinomial approach



              Consider the words in which one specific character (wlog, the first) does not appear contiguously,
              i.e. in runs of not more than $1$ in length, while the others can be placed in whatever way.

              Then, as explained in this post, their number will be:
              $$ bbox[lightyellow] {
              eqalign{
              & N_{,w1} (r_{,1} ,R) = left( matrix{ R - r_{,1} cr
              r_{,2} ,, cdots ,,r_{,n} cr} right)N_b (r_{,1} ,1,R - r_{,1} + 1) = left( matrix{
              R - r_{,1} cr
              r_{,2} ,, cdots ,,r_{,n} cr} right)sumlimits_{left( {0, le } right),,j,,left( { le ,r_{,1} ,/2} right)} {left( { - 1} right)^j left( matrix{
              R - r_{,1} + 1 cr j cr} right)left( matrix{ R - 2j cr r_{,1} - 2,j cr} right)} = cr
              & = left( matrix{ R - r_{,1} cr r_{,2} ,, cdots ,,r_{,n} cr} right)left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right)
              = left( matrix{ R cr r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} cr} right)
              left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right);mathop /limits_{} ;
              left( matrix{ R cr r_{,1} cr} right) cr}
              tag{1} }$$



              If the other characters have repetition $1$, then clearly that is the number of words with no equal contiguous character.
              In this case $R=n+r_{1}-1$
              $$ bbox[lightyellow] {
              eqalign{
              & N_{,w1} left( {r_{,1} ,,1,, cdots ,1} right) = left( matrix{
              R cr
              r_{,1} ,1,, cdots ,,1 cr} right)left( matrix{
              R - r_{,1} + 1 cr
              r_{,1} cr} right);mathop /limits_{} ;left( matrix{
              R cr
              r_{,1} cr} right) = cr
              & = left( {R - r_{,1} } right)!left( matrix{
              R - r_{,1} + 1 cr
              r_{,1} cr} right) = left( {n - 1} right)!left( matrix{
              n cr
              r_{,1} cr} right) cr}
              tag{2} }$$



              For the examples you give
              $$
              eqalign{
              & a,a,bquad Rightarrow ;quad N_{,w1} = 1!left( matrix{
              2 cr
              2 cr} right) = 1 cr
              & a,a,b,c,d,e,fquad Rightarrow ;quad N_{,w1} = 5!left( matrix{
              6 cr
              2 cr} right) = 1800 cr}
              $$
              so, with your method of counting, you just have to multiply by $r_{1}!$.



              For the case of a general $bf {r}$, we could develop forward identity (1) and proceed by inclusion-exclusion, but looks cumbersome.

              Let's try instead to find an adequate recurrence.



              The recursive approach



              Definitions



              Let's call
              $$
              N_{,0} ({bf r},a,b)
              $$
              the N. of words with no equal contiguous character, with repetition vector $bf r$ (the alphabet is implicit in it)
              and with starting character $a$ and ending character $b$.



              We consider empty, and thus their number null, the words for which:

              - the starting and ending character do not pertain to the alphabet : $a notin alpha ,; vee ;b notin alpha $

              - any component of the repetition vector is negative : $exists k:r_{,k} < 0$

              - the start or the end character have null repetition : $r_{,a} = 0,; vee ;r_{,b} = 0$

              - the dimension of $bf r$, i.e. of the alphabet, is null : $n<1$



              In this way, it is clear that the words with a given starting and ending character constitute a partition
              of the set of the considered words.



              Let's then indicate
              $$
              N_{,0} ({bf r}) = sumlimits_{1 le ,k,,j, le ,n} {N_{,0} ({bf r},k,j)}
              $$
              and put by definition that the number of empty words is 1
              $$
              N_{,0} ({bf 0}) = 1
              $$



              Also, we define the following vectors
              $$
              eqalign{
              & {bf u}_{,n} (a) = left( {delta _{,k,,a} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right];;left| {,1 le k le n} right.} right) cr
              & {bf u}_{,n} (a,b) = left( {delta _{,k,,a} + delta _{,k,,b} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right] + left[ {b = k} right];;left| {,1 le k le n} right.} right) cr
              & {bf u}_{,n} = left( {1;;left| {,1 le k le n} right.} right) cr}
              $$
              where $delta _{,k,,a} $ denotes the Kronecker delta and
              $[P]$ denotes the Iverson bracket.



              The starting cases



              Then, considering the simplest case of $R=1$, we have
              $$
              N_{,0} ({bf u}_{,n} (c),a,b) = left[ {a = b = c} right] = left[ {a = c} right]left[ {b = c} right]
              $$
              while for $R=2$
              $$
              N_{,0} ({bf u}_{,n} (c,d),a,b) = left[ {c ne d} right]left( {left[ {a = c} right]left[ {b = d} right] + left[ {a = d} right]left[ {b = c} right]} right)
              $$
              and for $R=3$
              $$
              N_{,0} ({bf u}_{,n} (c,d,e),a,b) = left[ {a ne b} right]left[ {left( {a,b} right) in 2{rm - permutation},{rm from},(c,d,e)} right]
              $$
              and finally for ${bf u}_{,n} $ ($R=n$)
              $$
              N_{,0} ({bf u}_{,n} ,a,b) = left[ {1 = n} right]left[ {a = b} right] + left[ {2 le n} right]left[ {a ne b} right]left( {n - 2} right)!
              $$



              The recursion



              Take a word (with no equal contiguous character) of length $2 le R$.

              We can divide it into two subwords of fixed length $R-S$ and $1 le S < R$.

              The end character of the first shall be different from the starting character of the second.

              Then we can part the repetition vector between them in all the ways, such that
              the sum of the components of the first is $R-S$ and that of the second is $S$.
              That means that $bf{r}$ is reparted into $bf{r-s}$ and $bf{s}$.
              Both vectors shall have at least one positive component. However, with the conditions
              established above $N_{,0} (mathbf{0},a,b) = 0quad left| {;1 leqslant n} right.$



              We can therefore write $N_{,0} (mathbf{r},a,b)$ as the following sum in $j,k,bf{s}$
              $$ bbox[lightyellow] {
              begin{gathered}
              N_{,0} (mathbf{r},a,b) = left[ {1 = R} right]left[ {a = b = k:r_{,k} ne 0} right] + hfill \
              + left[ {2 leqslant R} right]sumlimits_{left{ begin{subarray}{l}
              1 leqslant ,k ne ,j, leqslant ,n \
              mathbf{0}, leqslant ,mathbf{s}, leqslant ,mathbf{r}, \
              0 < ,sumlimits_l {s_{,l} } = S, < ,R
              end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k);N_{,0} (mathbf{s},j,b)} hfill \
              end{gathered}
              tag{3} }$$



              Then, for $S=1$ , (and $2 le R$), in particular, we have
              $$ bbox[lightyellow] {
              begin{gathered}
              N_{,0} (mathbf{r},a,b) = sumlimits_{left{ begin{subarray}{l}
              1 leqslant ,k ne ,j, leqslant ,n \
              mathbf{0} leqslant ,mathbf{s}, leqslant ,mathbf{r} \
              0 < sumlimits_l {s_{,l} } = 1, < ,R
              end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k)N_{,0} (mathbf{s},j,b)} = hfill \
              = sumlimits_{left{ begin{subarray}{l}
              1 leqslant ,k ne ,j, leqslant ,n \
              1 leqslant ,l, leqslant ,n \
              1 < ,R
              end{subarray} right.} {N_{,0} left( {left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k} right);N_{,0} left( {left( {0,, cdots ,1_{,left( l right)} ,, cdots ,,0} right),j,b} right)} = hfill \
              = sumlimits_{left{ begin{subarray}{l}
              1 leqslant ,k ne ,j, leqslant ,n \
              1 leqslant ,l, leqslant ,n \
              1 < ,R
              end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k);left[ {l = j = b} right]} = hfill \
              = sumlimits_{left{ begin{subarray}{l}
              1 leqslant ,k ne ,b, leqslant ,n \
              1 < ,R
              end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,b} - 1,, cdots ,,r_{,n} } right),a,k)} = hfill \
              = sumlimits_{1 leqslant ,k ne ,b, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} = hfill \
              = sumlimits_{1 leqslant ,k, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} - N_{,0} (mathbf{r} - mathbf{u}(b),a,b) hfill \
              end{gathered}
              tag{4} }$$



              which I checked to be correct against a dozen of cases.






              share|cite|improve this answer









              $endgroup$
















                0












                0








                0





                $begingroup$

                Interesting problem indeed: I am keen to try and see what is possible to fix down.



                Premise



                So we are considering the words, formed from the alphabet
                $$
                alpha = left{ {1,2,, cdots ,,n} right}
                $$
                with total number of repetitions of each character strictly correspondending to the vector
                $$
                {bf r} = left( {r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} } right)
                $$
                and thus having length equal to
                $$
                R = sumlimits_{1 le ,k, le ,n} {r_{,k} }
                $$



                With $r_k=0$ we will indicate that there is no occurence of the character $k$, which is a case
                useful to consider in the following.
                Of course, there is no loss of generality in permuting the vector $bf r$, so that we may assume that its
                components are arranged ,e.g., as non-increasing; then $a$ and $b$ shall also be permuted accordingly.



                So
                $$
                {bf r}_{,{bf n}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} ,0,, cdots ,0} right)quad Rightarrow quad {bf r}_{,{bf m}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} } right)
                $$



                The total number of words that can be formed from a given $bf r$ (the alphabet is implicit in its dimension), by definition of Multinomial is:
                $$
                N_w ({bf r}) = left( matrix{
                R cr
                r_{,1} ,r_{,2} ,, cdots ,,r_{,n} cr} right) = {{R!} over {r_{,1} !r_{,2} !, cdots ,r_{,n} !}}
                $$



                Our focus is on the words that do not have equal contiguous characters.



                The Multinomial approach



                Consider the words in which one specific character (wlog, the first) does not appear contiguously,
                i.e. in runs of not more than $1$ in length, while the others can be placed in whatever way.

                Then, as explained in this post, their number will be:
                $$ bbox[lightyellow] {
                eqalign{
                & N_{,w1} (r_{,1} ,R) = left( matrix{ R - r_{,1} cr
                r_{,2} ,, cdots ,,r_{,n} cr} right)N_b (r_{,1} ,1,R - r_{,1} + 1) = left( matrix{
                R - r_{,1} cr
                r_{,2} ,, cdots ,,r_{,n} cr} right)sumlimits_{left( {0, le } right),,j,,left( { le ,r_{,1} ,/2} right)} {left( { - 1} right)^j left( matrix{
                R - r_{,1} + 1 cr j cr} right)left( matrix{ R - 2j cr r_{,1} - 2,j cr} right)} = cr
                & = left( matrix{ R - r_{,1} cr r_{,2} ,, cdots ,,r_{,n} cr} right)left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right)
                = left( matrix{ R cr r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} cr} right)
                left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right);mathop /limits_{} ;
                left( matrix{ R cr r_{,1} cr} right) cr}
                tag{1} }$$



                If the other characters have repetition $1$, then clearly that is the number of words with no equal contiguous character.
                In this case $R=n+r_{1}-1$
                $$ bbox[lightyellow] {
                eqalign{
                & N_{,w1} left( {r_{,1} ,,1,, cdots ,1} right) = left( matrix{
                R cr
                r_{,1} ,1,, cdots ,,1 cr} right)left( matrix{
                R - r_{,1} + 1 cr
                r_{,1} cr} right);mathop /limits_{} ;left( matrix{
                R cr
                r_{,1} cr} right) = cr
                & = left( {R - r_{,1} } right)!left( matrix{
                R - r_{,1} + 1 cr
                r_{,1} cr} right) = left( {n - 1} right)!left( matrix{
                n cr
                r_{,1} cr} right) cr}
                tag{2} }$$



                For the examples you give
                $$
                eqalign{
                & a,a,bquad Rightarrow ;quad N_{,w1} = 1!left( matrix{
                2 cr
                2 cr} right) = 1 cr
                & a,a,b,c,d,e,fquad Rightarrow ;quad N_{,w1} = 5!left( matrix{
                6 cr
                2 cr} right) = 1800 cr}
                $$
                so, with your method of counting, you just have to multiply by $r_{1}!$.



                For the case of a general $bf {r}$, we could develop forward identity (1) and proceed by inclusion-exclusion, but looks cumbersome.

                Let's try instead to find an adequate recurrence.



                The recursive approach



                Definitions



                Let's call
                $$
                N_{,0} ({bf r},a,b)
                $$
                the N. of words with no equal contiguous character, with repetition vector $bf r$ (the alphabet is implicit in it)
                and with starting character $a$ and ending character $b$.



                We consider empty, and thus their number null, the words for which:

                - the starting and ending character do not pertain to the alphabet : $a notin alpha ,; vee ;b notin alpha $

                - any component of the repetition vector is negative : $exists k:r_{,k} < 0$

                - the start or the end character have null repetition : $r_{,a} = 0,; vee ;r_{,b} = 0$

                - the dimension of $bf r$, i.e. of the alphabet, is null : $n<1$



                In this way, it is clear that the words with a given starting and ending character constitute a partition
                of the set of the considered words.



                Let's then indicate
                $$
                N_{,0} ({bf r}) = sumlimits_{1 le ,k,,j, le ,n} {N_{,0} ({bf r},k,j)}
                $$
                and put by definition that the number of empty words is 1
                $$
                N_{,0} ({bf 0}) = 1
                $$



                Also, we define the following vectors
                $$
                eqalign{
                & {bf u}_{,n} (a) = left( {delta _{,k,,a} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right];;left| {,1 le k le n} right.} right) cr
                & {bf u}_{,n} (a,b) = left( {delta _{,k,,a} + delta _{,k,,b} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right] + left[ {b = k} right];;left| {,1 le k le n} right.} right) cr
                & {bf u}_{,n} = left( {1;;left| {,1 le k le n} right.} right) cr}
                $$
                where $delta _{,k,,a} $ denotes the Kronecker delta and
                $[P]$ denotes the Iverson bracket.



                The starting cases



                Then, considering the simplest case of $R=1$, we have
                $$
                N_{,0} ({bf u}_{,n} (c),a,b) = left[ {a = b = c} right] = left[ {a = c} right]left[ {b = c} right]
                $$
                while for $R=2$
                $$
                N_{,0} ({bf u}_{,n} (c,d),a,b) = left[ {c ne d} right]left( {left[ {a = c} right]left[ {b = d} right] + left[ {a = d} right]left[ {b = c} right]} right)
                $$
                and for $R=3$
                $$
                N_{,0} ({bf u}_{,n} (c,d,e),a,b) = left[ {a ne b} right]left[ {left( {a,b} right) in 2{rm - permutation},{rm from},(c,d,e)} right]
                $$
                and finally for ${bf u}_{,n} $ ($R=n$)
                $$
                N_{,0} ({bf u}_{,n} ,a,b) = left[ {1 = n} right]left[ {a = b} right] + left[ {2 le n} right]left[ {a ne b} right]left( {n - 2} right)!
                $$



                The recursion



                Take a word (with no equal contiguous character) of length $2 le R$.

                We can divide it into two subwords of fixed length $R-S$ and $1 le S < R$.

                The end character of the first shall be different from the starting character of the second.

                Then we can part the repetition vector between them in all the ways, such that
                the sum of the components of the first is $R-S$ and that of the second is $S$.
                That means that $bf{r}$ is reparted into $bf{r-s}$ and $bf{s}$.
                Both vectors shall have at least one positive component. However, with the conditions
                established above $N_{,0} (mathbf{0},a,b) = 0quad left| {;1 leqslant n} right.$



                We can therefore write $N_{,0} (mathbf{r},a,b)$ as the following sum in $j,k,bf{s}$
                $$ bbox[lightyellow] {
                begin{gathered}
                N_{,0} (mathbf{r},a,b) = left[ {1 = R} right]left[ {a = b = k:r_{,k} ne 0} right] + hfill \
                + left[ {2 leqslant R} right]sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                mathbf{0}, leqslant ,mathbf{s}, leqslant ,mathbf{r}, \
                0 < ,sumlimits_l {s_{,l} } = S, < ,R
                end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k);N_{,0} (mathbf{s},j,b)} hfill \
                end{gathered}
                tag{3} }$$



                Then, for $S=1$ , (and $2 le R$), in particular, we have
                $$ bbox[lightyellow] {
                begin{gathered}
                N_{,0} (mathbf{r},a,b) = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                mathbf{0} leqslant ,mathbf{s}, leqslant ,mathbf{r} \
                0 < sumlimits_l {s_{,l} } = 1, < ,R
                end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k)N_{,0} (mathbf{s},j,b)} = hfill \
                = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                1 leqslant ,l, leqslant ,n \
                1 < ,R
                end{subarray} right.} {N_{,0} left( {left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k} right);N_{,0} left( {left( {0,, cdots ,1_{,left( l right)} ,, cdots ,,0} right),j,b} right)} = hfill \
                = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                1 leqslant ,l, leqslant ,n \
                1 < ,R
                end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k);left[ {l = j = b} right]} = hfill \
                = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,b, leqslant ,n \
                1 < ,R
                end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,b} - 1,, cdots ,,r_{,n} } right),a,k)} = hfill \
                = sumlimits_{1 leqslant ,k ne ,b, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} = hfill \
                = sumlimits_{1 leqslant ,k, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} - N_{,0} (mathbf{r} - mathbf{u}(b),a,b) hfill \
                end{gathered}
                tag{4} }$$



                which I checked to be correct against a dozen of cases.






                share|cite|improve this answer









                $endgroup$



                Interesting problem indeed: I am keen to try and see what is possible to fix down.



                Premise



                So we are considering the words, formed from the alphabet
                $$
                alpha = left{ {1,2,, cdots ,,n} right}
                $$
                with total number of repetitions of each character strictly correspondending to the vector
                $$
                {bf r} = left( {r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} } right)
                $$
                and thus having length equal to
                $$
                R = sumlimits_{1 le ,k, le ,n} {r_{,k} }
                $$



                With $r_k=0$ we will indicate that there is no occurence of the character $k$, which is a case
                useful to consider in the following.
                Of course, there is no loss of generality in permuting the vector $bf r$, so that we may assume that its
                components are arranged ,e.g., as non-increasing; then $a$ and $b$ shall also be permuted accordingly.



                So
                $$
                {bf r}_{,{bf n}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} ,0,, cdots ,0} right)quad Rightarrow quad {bf r}_{,{bf m}} = left( {r_{,1} ,r_{,2} ,, cdots ,,r_{,m} } right)
                $$



                The total number of words that can be formed from a given $bf r$ (the alphabet is implicit in its dimension), by definition of Multinomial is:
                $$
                N_w ({bf r}) = left( matrix{
                R cr
                r_{,1} ,r_{,2} ,, cdots ,,r_{,n} cr} right) = {{R!} over {r_{,1} !r_{,2} !, cdots ,r_{,n} !}}
                $$



                Our focus is on the words that do not have equal contiguous characters.



                The Multinomial approach



                Consider the words in which one specific character (wlog, the first) does not appear contiguously,
                i.e. in runs of not more than $1$ in length, while the others can be placed in whatever way.

                Then, as explained in this post, their number will be:
                $$ bbox[lightyellow] {
                eqalign{
                & N_{,w1} (r_{,1} ,R) = left( matrix{ R - r_{,1} cr
                r_{,2} ,, cdots ,,r_{,n} cr} right)N_b (r_{,1} ,1,R - r_{,1} + 1) = left( matrix{
                R - r_{,1} cr
                r_{,2} ,, cdots ,,r_{,n} cr} right)sumlimits_{left( {0, le } right),,j,,left( { le ,r_{,1} ,/2} right)} {left( { - 1} right)^j left( matrix{
                R - r_{,1} + 1 cr j cr} right)left( matrix{ R - 2j cr r_{,1} - 2,j cr} right)} = cr
                & = left( matrix{ R - r_{,1} cr r_{,2} ,, cdots ,,r_{,n} cr} right)left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right)
                = left( matrix{ R cr r_{,1} ,,r_{,2} ,, cdots ,,r_{,n} cr} right)
                left( matrix{ R - r_{,1} + 1 cr r_{,1} cr} right);mathop /limits_{} ;
                left( matrix{ R cr r_{,1} cr} right) cr}
                tag{1} }$$



                If the other characters have repetition $1$, then clearly that is the number of words with no equal contiguous character.
                In this case $R=n+r_{1}-1$
                $$ bbox[lightyellow] {
                eqalign{
                & N_{,w1} left( {r_{,1} ,,1,, cdots ,1} right) = left( matrix{
                R cr
                r_{,1} ,1,, cdots ,,1 cr} right)left( matrix{
                R - r_{,1} + 1 cr
                r_{,1} cr} right);mathop /limits_{} ;left( matrix{
                R cr
                r_{,1} cr} right) = cr
                & = left( {R - r_{,1} } right)!left( matrix{
                R - r_{,1} + 1 cr
                r_{,1} cr} right) = left( {n - 1} right)!left( matrix{
                n cr
                r_{,1} cr} right) cr}
                tag{2} }$$



                For the examples you give
                $$
                eqalign{
                & a,a,bquad Rightarrow ;quad N_{,w1} = 1!left( matrix{
                2 cr
                2 cr} right) = 1 cr
                & a,a,b,c,d,e,fquad Rightarrow ;quad N_{,w1} = 5!left( matrix{
                6 cr
                2 cr} right) = 1800 cr}
                $$
                so, with your method of counting, you just have to multiply by $r_{1}!$.



                For the case of a general $bf {r}$, we could develop forward identity (1) and proceed by inclusion-exclusion, but looks cumbersome.

                Let's try instead to find an adequate recurrence.



                The recursive approach



                Definitions



                Let's call
                $$
                N_{,0} ({bf r},a,b)
                $$
                the N. of words with no equal contiguous character, with repetition vector $bf r$ (the alphabet is implicit in it)
                and with starting character $a$ and ending character $b$.



                We consider empty, and thus their number null, the words for which:

                - the starting and ending character do not pertain to the alphabet : $a notin alpha ,; vee ;b notin alpha $

                - any component of the repetition vector is negative : $exists k:r_{,k} < 0$

                - the start or the end character have null repetition : $r_{,a} = 0,; vee ;r_{,b} = 0$

                - the dimension of $bf r$, i.e. of the alphabet, is null : $n<1$



                In this way, it is clear that the words with a given starting and ending character constitute a partition
                of the set of the considered words.



                Let's then indicate
                $$
                N_{,0} ({bf r}) = sumlimits_{1 le ,k,,j, le ,n} {N_{,0} ({bf r},k,j)}
                $$
                and put by definition that the number of empty words is 1
                $$
                N_{,0} ({bf 0}) = 1
                $$



                Also, we define the following vectors
                $$
                eqalign{
                & {bf u}_{,n} (a) = left( {delta _{,k,,a} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right];;left| {,1 le k le n} right.} right) cr
                & {bf u}_{,n} (a,b) = left( {delta _{,k,,a} + delta _{,k,,b} ;left| {,1 le k le n} right.} right) = left( {left[ {a = k} right] + left[ {b = k} right];;left| {,1 le k le n} right.} right) cr
                & {bf u}_{,n} = left( {1;;left| {,1 le k le n} right.} right) cr}
                $$
                where $delta _{,k,,a} $ denotes the Kronecker delta and
                $[P]$ denotes the Iverson bracket.



                The starting cases



                Then, considering the simplest case of $R=1$, we have
                $$
                N_{,0} ({bf u}_{,n} (c),a,b) = left[ {a = b = c} right] = left[ {a = c} right]left[ {b = c} right]
                $$
                while for $R=2$
                $$
                N_{,0} ({bf u}_{,n} (c,d),a,b) = left[ {c ne d} right]left( {left[ {a = c} right]left[ {b = d} right] + left[ {a = d} right]left[ {b = c} right]} right)
                $$
                and for $R=3$
                $$
                N_{,0} ({bf u}_{,n} (c,d,e),a,b) = left[ {a ne b} right]left[ {left( {a,b} right) in 2{rm - permutation},{rm from},(c,d,e)} right]
                $$
                and finally for ${bf u}_{,n} $ ($R=n$)
                $$
                N_{,0} ({bf u}_{,n} ,a,b) = left[ {1 = n} right]left[ {a = b} right] + left[ {2 le n} right]left[ {a ne b} right]left( {n - 2} right)!
                $$



                The recursion



                Take a word (with no equal contiguous character) of length $2 le R$.

                We can divide it into two subwords of fixed length $R-S$ and $1 le S < R$.

                The end character of the first shall be different from the starting character of the second.

                Then we can part the repetition vector between them in all the ways, such that
                the sum of the components of the first is $R-S$ and that of the second is $S$.
                That means that $bf{r}$ is reparted into $bf{r-s}$ and $bf{s}$.
                Both vectors shall have at least one positive component. However, with the conditions
                established above $N_{,0} (mathbf{0},a,b) = 0quad left| {;1 leqslant n} right.$



                We can therefore write $N_{,0} (mathbf{r},a,b)$ as the following sum in $j,k,bf{s}$
                $$ bbox[lightyellow] {
                begin{gathered}
                N_{,0} (mathbf{r},a,b) = left[ {1 = R} right]left[ {a = b = k:r_{,k} ne 0} right] + hfill \
                + left[ {2 leqslant R} right]sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                mathbf{0}, leqslant ,mathbf{s}, leqslant ,mathbf{r}, \
                0 < ,sumlimits_l {s_{,l} } = S, < ,R
                end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k);N_{,0} (mathbf{s},j,b)} hfill \
                end{gathered}
                tag{3} }$$



                Then, for $S=1$ , (and $2 le R$), in particular, we have
                $$ bbox[lightyellow] {
                begin{gathered}
                N_{,0} (mathbf{r},a,b) = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                mathbf{0} leqslant ,mathbf{s}, leqslant ,mathbf{r} \
                0 < sumlimits_l {s_{,l} } = 1, < ,R
                end{subarray} right.} {N_{,0} (mathbf{r} - mathbf{s},a,k)N_{,0} (mathbf{s},j,b)} = hfill \
                = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                1 leqslant ,l, leqslant ,n \
                1 < ,R
                end{subarray} right.} {N_{,0} left( {left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k} right);N_{,0} left( {left( {0,, cdots ,1_{,left( l right)} ,, cdots ,,0} right),j,b} right)} = hfill \
                = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,j, leqslant ,n \
                1 leqslant ,l, leqslant ,n \
                1 < ,R
                end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,l} - 1,, cdots ,,r_{,n} } right),a,k);left[ {l = j = b} right]} = hfill \
                = sumlimits_{left{ begin{subarray}{l}
                1 leqslant ,k ne ,b, leqslant ,n \
                1 < ,R
                end{subarray} right.} {N_{,0} (left( {r_{,1} ,, cdots ,r_{,b} - 1,, cdots ,,r_{,n} } right),a,k)} = hfill \
                = sumlimits_{1 leqslant ,k ne ,b, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} = hfill \
                = sumlimits_{1 leqslant ,k, leqslant ,n} {N_{,0} (mathbf{r} - mathbf{u}(b),a,k)} - N_{,0} (mathbf{r} - mathbf{u}(b),a,b) hfill \
                end{gathered}
                tag{4} }$$



                which I checked to be correct against a dozen of cases.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Jul 23 '17 at 22:04









                G CabG Cab

                19.3k31238




                19.3k31238






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1410184%2fpermutations-excluding-repeated-characters%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Ellipse (mathématiques)

                    Quarter-circle Tiles

                    Mont Emei