current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 6 down vote favorite

The Problem:

So I was thinking up some simple combinatorics problems, and this one stumped me.

Let N be the set of numbers $\{1 .. n\}$, or any set of cardinality $n$

Let K be the set of numbers $\{1 .. k\}$ where $k < n$, or any subset of N of cardinality $k$

How many permutations of N exist such that no two members of set k are adjacent?

Here was my basic approach:

Solutions = Permutations of N - Permutations of N that contain a pair in K

Permutations of N = nPn = n!

Every item in K will occur in each permutation of N so we loop through: 

 You place down one item of K
 Possibilities where the next is in K = K - 1
 You place down an item of K 
 possibilities where next is in k = k-2
 ...
 You place the last item in K

The total permutations with a pair would therefore be:

$ (k-1) + (k-2) + ... + 0 $

However, many of those entries are duplicates, so we have to rule out instances where two of those pairs occurred in one set, and then again rule out instances that occurred three times, up pairs occurred k times

I think the amount with two pairs would best be found by getting the amount with one pair minus the amount with no more.

To do this I would loop as:

You place two items in K
There are k-2 chances the next item is in k
You place an item in K
There are k-3 chances the next item is in k
...
You place your last item in K

Total permutations with two pairs $= (k - 2) + (k - 3) + ... + 0$

Total permutations with three pairs $= (k - 3) + (k - 4) + ... + 0$

And so on..

And at this point I know I am incorrect, because I would get a total of:

$( (k-1) + (k-2) + ... + 0 ) - ( (k-2) + (k-3) + ... + 0 ) - ( (k-3) + (k-4) + ... + 0 ) + ... + 0$ permutations that contain pairs.

This number is waaay negative...

As I pointed out at the end of that, my solution finds a negative amount of permutations that have pairs in them, and so it is clearly wrong. If someone could explain my error, or else show a better way to approach the problem, I would greatly appreciate it.

Things that I think could be causing my answer to be wrong:

  • I'm not sure if my generalization for removing the permutations with multiple pairs from the total amount of possible pairs works correctly if the pair does not occur as the first appearance of a member of set K
share|cite|improve this question
    
Have you considered that the instances with three pairs, for example, have already been removed (three times) as part of removing the instances with two pairs? See inclusion-exclusion for more discussion. – Joffan 9 hours ago
    
They have been removed three times when I remove all pairs, so I try to add them back, once by adding back all the pairs that occur twice, and then by adding back all the pairs that occur three times. – rp.beltran 9 hours ago
    
Thanks for the link though, and I think you may be right that my logic there is a bit off, I'm not sure. – rp.beltran 8 hours ago
1  
What you are doing to do might be a bit hard to keep track of, I think there is a simpler way to approach this question. – Sina 8 hours ago
1  
As an aside, I'm unsure how you were attempting to do your calculations... It appears that you are using a summorial (i.e. triangle number $1+2+3+\dots+k-1$) as opposed to factorials $1\times 2\times 3\times \cdots \times (k-1)$ in some of your calculations. Approaching via inclusion-exclusion on the events that element $i$ is adjacent to some other element in $K$ appears very frustrating to do. Even being more specific, defining events $A_{i,j}$ where element $i$ is adjacent to element $j$ will be cumbersome as you can have impossibilities like $1$ being next to $2$, nxt to $3$, nxt to $1$. – JMoravitz 8 hours ago
up vote 9 down vote accepted

Let's call the elements up to $k$ white and the others black, and consider elements of the same colour to be indistinguishable for now. For arrangements beginning with a white element, glue a black element to the left of all other white elements and choose $k-1$ slots among the resulting $n-k$ objects (excluding the initial white element) for the glued pairs. For arrangements beginning with a black element, glue a black element to the left of all white elements and choose $k$ slots among the resulting $n-k$ objects for the glued pairs. In total, that makes $\binom{n-k}{k-1}+\binom{n-k}k=\binom{n-k+1}k$ arrangements. Each corresponds to $k!$ permutations of the white elements and $(n-k)!$ permutations of the black elements, so the total number of permutations is

$$ \binom{n-k+1}kk!(n-k)!=\frac{(n-k+1)!k!(n-k)!}{(n-2k+1)!k!}=\frac{(n-k+1)!(n-k)!}{(n-2k+1)!}\;. $$

If $n-2k+1\lt0$, i.e. $k\gt\frac{n+1}2$, the binomial coefficient is zero and there are no such permutations.

share|cite|improve this answer
1  
This is brilliant. I have been thinking about this problem for a while now, and clearly the wrong way. Thanks. – rp.beltran 8 hours ago
up vote 6 down vote

An alternate explanation to @joriki's answer.

Let the $k$ elements $\{1,2,3,\dots,k\}$ be called "white" and the remaining $n-k$ elements be called "black."

First arrange the $n-k$ black elements in a row, leaving a bit of extra space to either side including to the left of the leftmost and to the right of the rightmost black element.

In these $n-k+1$ available spaces, choose $k$ of them to be occupied by white elements.

Arrange the white elements in a row and place them in the chosen locations.

There are then $\binom{n-k+1}{k}(n-k)!k!$ arrangements.

Note that when $k>n-k+1$, i.e. $k>\frac{n+1}{2}$ you will be forced to have two white elements adjacent and will have zero possible arrangments.

share|cite|improve this answer
    
I think it's fair to say "a better explanation than joriki's answer" :-) – joriki 8 hours ago
1  
This helped me understand it a lot. Thank you. I would like to have accepted both versions, this was very well explained. – rp.beltran 8 hours ago

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.