I am looking for a closed expression for calculating the number of combinations of $n = n_1 + n_2 + n_3$ objects arranged in an ordered list, where there are $n_1$ $a$, $n_2$ $b$ and $n_3$ $c$, under the constraint that $a$ may not appear adjacent to $a$, $b$ not adjacent to $b$, and $c$ not adjacent to $c$.

If $n_1 = n_2 = n_3$, the following is an upper bound on the number of combinations:

$3$ ways of picking the first, and $2$ ways of picking all subsequent objects gives

$$3 \cdot 2^{n-1}$$

A solution only exists if $n_1$ is not greater than $1+n_2+n_3$ and similarly for $n_2$ and $n_3$

Thanks to @Byron Schmuland for pointing me to a general answer; the integral that needs to be evaluated looks a bit daunting.

Now I need a solution to the integral for three items like the one listed on page 9 of the paper cited in the answer for two items.

  • $\begingroup$ Jair Taylor's answer here math.stackexchange.com/questions/129451/… gives the solution, not only for three, but also four, five, etc. $\endgroup$ – user940 Feb 18 '13 at 19:01
  • $\begingroup$ Some MathJax tips for future reference: n_1 gives you index 1 on n; and \cdot is the multiplication dot. Putting an equation between double dollar signs centers it. $\endgroup$ – gnometorule Feb 18 '13 at 19:02
  • $\begingroup$ Thanks for the link Byron Schmuland. My reading of that question is that it is for the case $n1=n2=n3$ only, which is useful as a tighter upper bound. I have a situation where the $n$'s are rarely equal. Thanks gnometorule $\endgroup$ – Derek Jones Feb 18 '13 at 19:11
  • 1
    $\begingroup$ No, Taylor's solution does not assume $n_1=n_2=n_3$ and gives an explicit formula. $\endgroup$ – user940 Feb 18 '13 at 19:15
  • $\begingroup$ The parameter to Taylor's equation is $k$, there is no $k_1$, $k_2$ and $k_3$ to support different numbers of each item. $\endgroup$ – Derek Jones Feb 18 '13 at 19:20

In addition to the formula linked above there is a nice generating function. The number of solutions with $i$ $a$'s, $j$ $b$'s and $k$ $c$'s is the coefficient of $a^ib^jc^k$ in $$\frac{1}{1 - \frac{a}{1+a} - \frac{b}{1+b} - \frac{c}{1+c}}.$$ This is a consequence of the beautiful "Carlitz-Scoville-Vaughan" theorem; see this MathOverflow question for an explanation.

  • $\begingroup$ Yes! Exactly what I was after. Thanks for this @Jair Taylor $\endgroup$ – Derek Jones Feb 19 '13 at 14:51

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.