beads in a string with restrictions

Question

Using the principle of inclusion and exclusion; let $p,q\in \mathbb{N}$, being $p$ odd, there are $pq$ beads of $q$ different colors, with $p$ beads in each color. If the beads of the same colour are identical, in how many ways can this beads be put in a string in such a way that beads of the same colour must be in two separate blocks?

the answer is $${1\over 2}\left[ {p\over 2}\right]^q\left(\sum_{i=0}^q(-1)^i{q\choose i}2^i(2q-i)!\right)$$ but I don't know why

Answer 1

First we need to answer an auxiliary question, which is: given $i$ items with $i+1$ gaps surrounding them/between them, where each gap consists of a sequence of cells, what is the number of ways to distribute $m$ cells in total into these gaps? This is seen to have generating function $$ f(z) = \frac{1}{(1-z)^{i+1}}$$ and hence the count is given by $$[z^m] \frac{1}{(1-z)^{i+1}} = {m+i\choose m} = {m+i\choose i}.$$ (A similar calculation is at this MSE link.)

Second, solve the problem of having two items of each of $q$ colors and count all sequences where two items of the same color may not be adjacent. Here the base sets $A_j$ for inclusion-exclusion count the number of sequences where color $j$ is adjacent. This gives for the intersection terms $$|A_r\cap A_s\cap\cdots|$$ of $i$ colors the cardinality $${q\choose i} \times i! \times {2q-2i+i\choose i} \times {2q-2i\choose 2,2,\ldots, 2}$$ because we must choose the $i$ adjacent colors from the $q$ colors total, consider all their permutations, distribute the $2q-2i$ remaining items into $i+1$ spaces and fill these with the $2q-2i$ items. (This will count the sequences where at least the $i$ chosen colors are adjacent.)

Simplifying we get $${q\choose i} \times i! \times \frac{(2q-i)!}{(2q-2i)!\times i!} \times \frac{(2q-2i)!}{2^{q-i}} = {q\choose i} \frac{(2q-i)!}{2^{q-i}}.$$ Substituting this into the inclusion-exclusion formula yields $$\sum_{i=0}^q {q\choose i} (-1)^i \frac{(2q-i)!}{2^{q-i}} = \frac{1}{2^q} \sum_{i=0}^q {q\choose i} \times(-1)^i\times 2^i\times (2q-i)!$$

This sequence starts out like this: $$0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120, 851371260364800,\ldots$$ and we find that we have A114938 from the OEIS.

Third, to conclude, note when there are $p$ instances of each color the two blocks may have the dimensions $(1,p-1),(2,p-2),(3,p-3),\cdots,(p-2,2),(p-1,1),$so there are $p-1$ pairs, giving the formula $$\frac{(p-1)^q}{2^q} \sum_{i=0}^q {q\choose i} \times(-1)^i\times 2^i\times (2q-i)!$$ But since $p$ is odd we have $$\Big\lfloor\frac{p-1}{2}\Big\rfloor = \Big\lfloor\frac{p}{2}\Big\rfloor$$ giving $$\Big\lfloor\frac{p}{2}\Big\rfloor^q \sum_{i=0}^q {q\choose i} \times(-1)^i\times 2^i\times (2q-i)!,$$ which may be prepended with a multiplier of $1/2$ if reflective symmetry of the string is considered (with $p$ being odd two blocks of the same color cannot be mapped onto each other by a reflection).

The following Maple program may be used to verify the solution to part two for values up to $q=5.$

with(combinat,permute);

w :=
proc(n)
    local p, obj, r, adm, pos;
    option remember;

    r := 0;

    obj :=[seq(k,k=1..n),seq(k,k=1..n)];

    for p in permute(obj) do
        adm := true;

        for pos from 1 to 2*n-1 do
            if p[pos] = p[pos+1] then
                adm := false;
                break;
            fi;
        od;

        if adm then r := r+1 fi;
    od;

    r;
end;

w2 := q -> 1/2^q*sum(binomial(q,i)*(-1)^i*2^i*(2*q-i)!,i=0..q);