Permute "aaaaabbbbbccccc" so that no two identical letters are adjacent 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?
 A: 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.
A: 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.

A: I made an Algorithm and found the same answer as user1537366, then I search for a general formula, and Here it is
A: 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.
A: 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.
