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


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
Adding the spaces [here denoted by an underscore]:

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

  • $\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

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


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 = \sum\limits_{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)\sum\limits_{\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,b\quad \Rightarrow \;\quad N_{\,w1} = 1!\left( \matrix{ 2 \cr 2 \cr} \right) = 1 \cr & a,a,b,c,d,e,f\quad \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


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}) = \sum\limits_{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) = 0\quad \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]\sum\limits_{\left\{ \begin{subarray}{l} 1 \leqslant \,k \ne \,j\, \leqslant \,n \\ \mathbf{0}\, \leqslant \,\mathbf{s}\, \leqslant \,\mathbf{r}\, \\ 0 < \,\sum\limits_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) = \sum\limits_{\left\{ \begin{subarray}{l} 1 \leqslant \,k \ne \,j\, \leqslant \,n \\ \mathbf{0} \leqslant \,\mathbf{s}\, \leqslant \,\mathbf{r} \\ 0 < \sum\limits_l {s_{\,l} } = 1\, < \,R \end{subarray} \right.} {N_{\,0} (\mathbf{r} - \mathbf{s},a,k)N_{\,0} (\mathbf{s},j,b)} = \hfill \\ = \sum\limits_{\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 \\ = \sum\limits_{\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 \\ = \sum\limits_{\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 \\ = \sum\limits_{1 \leqslant \,k \ne \,b\, \leqslant \,n} {N_{\,0} (\mathbf{r} - \mathbf{u}(b),a,k)} = \hfill \\ = \sum\limits_{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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.