3
$\begingroup$

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.

$\endgroup$
9
  • $\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
    Commented Feb 18, 2013 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
    Commented Feb 18, 2013 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
    Commented Feb 18, 2013 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
    Commented Feb 18, 2013 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
    Commented Feb 18, 2013 at 19:20

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .