Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Gerry Myerson Mar 20 '12 at 22:02
3  
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. –  fedja Mar 20 '12 at 22:25
    
You might find oeis.org/A110706 worth a look. It gives an explicit formula for equal numbers of three objects. –  Barry Cipra Mar 23 '12 at 20:35
add comment

2 Answers

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}}.$$

share|improve this answer
    
That's cool! (And easier to work with than my o.g.f) –  John Wiltshire-Gordon Mar 21 '12 at 1:39
3  
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. –  Richard Stanley Mar 22 '12 at 1:18
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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