8
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please explain the main contents of the link and give the formula here. Link only answers are discouraged because they become useless if the link dies. $\endgroup$ – Joonas Ilmavirta Dec 10 '14 at 11:24
  • $\begingroup$ Any proof for that formula: $a(n)=2\sum_{k=0}^{[n/2]}\binom{n-1}{k}\left(\binom{n-1}{k} \binom{2n+1-2k}{n+1} + \binom{n-1}{k+1}\binom{2n-2k}{n+1}\right)$? $\endgroup$ – user1537366 Dec 10 '14 at 11:26
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Exactly, I was just going to post my answer, which is slightly simpler because of symmetry, but these methods do not give a easy solution for the general case that is in the question linked. Also, you might want to change the function names to capital letters! $\endgroup$ – user1537366 Dec 10 '14 at 10:08
0
$\begingroup$

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.

$\endgroup$

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.