Permutations excluding repeated characters

Question

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 "a₁a₂b"

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

Answer 1

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..

Answer 2

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 = \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

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}) = \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.