Permute "aaaaabbbbbccccc" so that no two identical letters are adjacent

Question

This is a follow up question to Application of PIE. How many strings with the letters "aaaaabbbbbccccc" are there so that no two identical letters are adjacent?

Answer 1

My initial thoughts:

There are $15!$ permutations when we consider all letters to be distinct (for starters!), say $a_1,\ldots a_5$, and similarly for $b$'s and $c$'s. The conditions to avoid are $A(i,j)$, $B(i,j)$, $C(i,j)$ (where $i < j$), where e.g. $A(i,j)$ means all permutations where $a_i$ and $a_j$ are adjacent etc. So we need to count all permutations that avoid all the conditions (classical inclusion-exclusion), and then divide the result by $5! 5! 5!$, because in the final result we cannot actually distinguish the $a$'s, $b$'c and $c$'s.

How to count $A(i,j)$: we merge $a_i$ and $a_j$ to one symbol $a(i,j)$ and so we are left with $14!$ symbols, that we permute. In the final result, we can expand $a(i,j)$ back to either $a_i a_j$ or $a_j a_i$ and get two permutations that obey the condition. So we have $2!14!$ many permutations in $A(i,j)$ for every $i < j$. And we have ${5 \choose 2}$ such conditions. The same holds for all $B(i,j)$ and $C(i,j)$ as well.

So we have $15! - 3\cdot {5 \choose 2} 2! 14!$ as the first approximation.

Of course we double-count here: conditions $A(i,j)$ and $A(l,k)$ can both occur at the same time. There is a difference here when $(i,j)$ and $(l,k)$ overlap or not. In the latter case we have $2!2!13!$ many different permutations (two new symbols, both of which can be expanded in two ways), in the former $3! 12!$ ways (one new symbol for 3 different $a_i a_j a_k$, expanded $3!$ ways. Of the former type are ${5 \choose 2}{3 \choose 2}$ pairs, and the latter ${5 \choose 3}$ many.

ALso, conditions $A(i,j)$, $B(i,j)$ can occur at the same time. (and similarly $A$ and $C$ and $B$ and $C$ conditions). Collect of all these together as well, and add to the previous.

And so on. This might be too complicated, but it's the first thing I came up with.

Answer 2

There is a three-dimensional recurrence for this: let $f(x,y,z)$ be the number of combinations of $x$ a's, $y$ b's and $z$ c's so that no two identical letters are adjacent and the first letter is an "a".

$$f(1,0,0)=1$$ $$f(x,y,z)=f(y,z,x-1)+f(z,x-1,y)\quad\text{if }x>0\text{ and }0\text{ otherwise.}$$

So a simple JavaScript code to compute this is:

function f(x,y,z)
{
    var mem=[];
    function f2(bag)
    {
        if( bag in mem ) return mem[bag];
        if( bag.toString()=="1,0,0" ) return 1;
        if( bag[0]>0 ) return mem[bag]=f2([bag[1],bag[2],bag[0]-1])+f2([bag[2],bag[0]-1,bag[1]]);
        else return 0;
    }
    return f2([x,y,z])+f2([y,z,x])+f2([z,x,y]);
}
var ans=f(5,5,5);
alert(ans); // which gives 7188 but I'm not sure if that's correct.

Answer 3

I made an Algorithm and found the same answer as user1537366, then I search for a general formula, and Here it is

Answer 4

Best approach I think just use recursion, and a few appropriate functions:

$f(5,5,5) = a(4,5,5) + b(5,4,5) + c(5,5,4)$

$a(a,b,c) = b(a,b-1,c) + c(a,b,c-1)$ etc..

$a(-1,b,c) = 0$ etc.

Where $f(a,b,c)$ is the total number of sequences with $a$ a's etc.

$a(a,b,c)$ is the number of sequences where the last letter is 'a', and we can still use $a$ a's, $b$ b's etc.

Other option would be to use inclusion/exclusion, but that would have some very difficult functions for the duplicates.

Answer 5

According to Sequences with Adjacent Elements Unequal, the number of sequences of a's, b's and c's comprising $n$ of each letter such that no two identical letters are adjacent is: $$3\left(\sum_{v=0}^{\lfloor(s-1)/2\rfloor}{s-1\choose 2v}{2v\choose v}{s+v-1\choose v+1}2^{s-1-2v}+\sum_{v=0}^{\lfloor s/2\rfloor}{s\choose 2v}{2v\choose v}{s+v-1\choose v}2^{s-2v}\right)$$

The crucial trick was to note that the blocks of b's and c's between consecutive a's are alternating.