How many strings of letters, where all of $a,b,c$'s don't create a continuous block.

Question

I need to find out, how many string made out of $\alpha$ $a$'s, $\beta$ $b$'s and $\gamma$ $c$'s where all of $a,b$ or $c$'s are not packed together, meaning that for $2$ $a$'s and $3$ $b$'s and $2$ $c$'s $aabcbcb$ is not allowed, because all of $a$'s are next to each other, same with $aabbbcc$ or $ccbabab$ but $abcabcb$ is allowed.

So I tried to solve it using inclusion exclusion principle, and this is what I've come up with: $|A|$- number of all strings $=\dfrac{(\alpha+\beta+\gamma)!}{\alpha!\beta!\gamma!}$

$|A_w|$- number of wrong strings$=|A_a|+|A_b|+|A_c|-|A_{bc}|-|A_{ac}|-|A_{ab}|+|A_{abc}|$

What I'm looking for $|A|-|A_w|$

Where $A_{xyz}$ is number of combinations, where all of $x$ and $z$ and $y$ are next to each other.

For example $A_{bc}=(\alpha+1)(\alpha+2)$, because first we put all the $b$ somewhere between $\alpha$ $a$'s and we can do it $(\alpha+1)$ ways and then we put all of the $c$'s somewhere between all of the $a$'s and the block of $b$'s but not inside the block of $b$'s, so there are $(\alpha+2)$ ways to do that.

Would this solution be correct?

Answer 1

The solution looks good. Actually doing the counting/enumeration I get $$|A_a| = (\beta+\gamma+1) {\beta+\gamma \choose \beta}$$ and $$|A_b| = (\alpha+\gamma+1) {\alpha+\gamma \choose \gamma}$$ and $$|A_c| = (\alpha+\beta+1) {\alpha+\beta \choose \alpha}$$ because we must choose a position for the packed together block and then distribute the leftover elements into the remaining slots.

For the two-element combinations we get that $$|A_{ab}| = 2 \times \sum_{a+b+c=\gamma} 1 = 2\times [z^\gamma] \frac{1}{(1-z)^3} = 2\times {\gamma+2\choose \gamma}.$$ By symmetry, $$|A_{ac}| = 2\times {\beta+2\choose \beta}$$ and $$|A_{bc}| = 2\times {\alpha+2\choose \alpha}.$$ This is because there are now two ways to order the packed together blocks and the leftover elements must be distributed into the spaces between the two blocks. (Three spaces, $a+b+c=\gamma$ distributions.)

Finally, $$|A_{abc}| = 6,$$ for obvious reasons.

Therefore we have that the end result for the number of wrong strings is $$(\beta+\gamma+1) {\beta+\gamma \choose \beta} +(\alpha+\gamma+1) {\alpha+\gamma \choose \gamma} +(\alpha+\beta+1) {\alpha+\beta \choose \alpha}\\ -2\times {\gamma+2\choose \gamma} -2\times {\beta+2\choose \beta} -2\times {\alpha+2\choose \alpha} +6.$$ This formula holds for $\alpha,\beta,\gamma>0.$

Here is a Maple program that can help verify the above formula.

with(combinat,permute);

cnt :=
proc(av,bv,cv)
    option remember;
    local str, sq, w, aw, bw, cw, strx;

    w := 0;

    sq := [seq(a,k=1..av),seq(b,k=1..bv),seq(c,k=1..cv)];

    aw := cat(seq('a', k=1..av));
    bw := cat(seq('b', k=1..bv));
    cw := cat(seq('c', k=1..cv));

    for str in permute(sq, av+bv+cv) do
        strx := cat(seq(str[k], k=1..nops(str)));

        if searchtext(aw,strx)>0 or
        searchtext(bw,strx)>0 or
        searchtext(cw,strx)>0 then
            w := w+1;
        fi;
    od;

    w;
end;

v :=
proc(av,bv,cv)
    (bv+cv+1)*binomial(bv+cv,bv)+
    (av+cv+1)*binomial(av+cv,cv)+
    (av+bv+1)*binomial(av+bv,av)
    -2*binomial(cv+2,cv)
    -2*binomial(bv+2,bv)
    -2*binomial(av+2,av)
    +6;
end;