6
$\begingroup$

We have $n$ types of objects, the number of objects of type $i$ being $a_i$, $1\leq i\leq n$.

What is the number of permutations of the $\sum_{i=1}^n a_i$ objects, if no two objects of the same type may be next to each other?

A simple example: If we have the objects $\{a,a,a,b,b,c,c\}$, then we allow $abcabac$ but not $aaabbcc$.

I have searched the web. The only results I found were about permutations of (pairwise) different objects avoiding certain patterns.

I put this question on math.stackexchange.com but haven't received an answer.

$\endgroup$
3
  • 1
    $\begingroup$ Not getting an answer on m.se is not sufficient reason for asking it here. Anyway, you should edit in a link to the m.se version. $\endgroup$ Mar 20, 2012 at 22:02
  • 3
    $\begingroup$ Actually, it doesn't seem trivial at all (except the $n=2$ case when the answer is $2$ if $a_1=a_2$, $1$ if $|a_1-a_2|=1$ and $0$ otherwise). When the question is well-posed, I vote to close without any comment if I know the answer and just find the question too trivial to waste my time on. However, here I have no idea whether there is a reasonably nice formula (to write a monstrous sum is never a problem), so if somebody could enlighten me before voting to close, I would appreciate it. $\endgroup$
    – fedja
    Mar 20, 2012 at 22:25
  • $\begingroup$ You might find oeis.org/A110706 worth a look. It gives an explicit formula for equal numbers of three objects. $\endgroup$ Mar 23, 2012 at 20:35

2 Answers 2

11
$\begingroup$

There's a nice result, I think due to Carlitz, Scoville, and Vaughan (I learned it as the "Carlitz-Scoville-Vaughan theorem", but I'm not sure how common that is) that the o.g.f. for words in which no pair of consecutive letters is among a restricted set is the multiplicative inverse of the o.g.f. for words in which every pair of consecutive letters is in that restricted set, evaluated at $(-a,-b,-c,\dots)$.

So for your problem, the o.g.f. for words in $a,b,c$ where all adjacent letters are the same is $$g(a,b,c) = 1 + a + b + c + a^2 + b^2 + c^2 + \cdots = 1 + \frac{a}{1-a}+\frac{b}{1-b}+\frac{c}{1-c},$$ which means the generating function for words in $a,b,c$ where no adjacent letters are the same is $$f(a,b,c) = \frac{1}{g(-a,-b,-c)} = \frac{1}{1-\frac{a}{1+a}-\frac{b}{1+b}-\frac{c}{1+c}}.$$

$\endgroup$
3
  • $\begingroup$ That's cool! (And easier to work with than my o.g.f) $\endgroup$ Mar 21, 2012 at 1:39
  • 5
    $\begingroup$ Another way of writing this generating function (in any number of variables) is $$ \frac{\sum_{i≥0} e_i}{1−\sum_{i≥1}(i−1)e_i}, $$ where $e_i$ is the $i$th elementary symmetric function in the variables. See Exercise~7.47(k) of Enumerative Combinatorics, vol. 2. Some references are given in the solution to this exercise. $\endgroup$ Mar 22, 2012 at 1:18
  • $\begingroup$ I wonder if there is a generalization of this, if we are talking about necklaces, not words. $\endgroup$
    – ivan
    Nov 8, 2018 at 10:59
8
$\begingroup$

Here is a generating function for the problem. I will do the case where there are three types of object, but the pattern will be evident. The strategy is to represent the free associative algebra on the types of object modulo the relation that each generator squares to zero.

Define

$$x = \pmatrix{ 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 } $$

$$y = \pmatrix{ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 } $$

$$z = \pmatrix{ 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 } $$

Now we build the generating function: $$f_k(a,b,c) = \pmatrix{1/2 & 1/2 & 1/2} (ax + by + cz)^k \pmatrix{1 \\ 1 \\ 1}.$$

For example, $$f_4(a,b,c)=2a^2b^2 + 6a^2bc + 6ab^2c + 2a^2c^2 + 6abc^2 + 2b^2c^2.$$ These coefficients are the answers to the problem. For instance, the first term asserts that there are exactly two ways to use $a,a,b,b$ to form a string without adjacent $a$'s or $b$'s.

If you care to diagonalize the matrix in the middle, you can obtain a more explicit formula for $f$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.