6
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joffan Jun 16 '16 at 20:41
  • $\begingroup$ 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. $\endgroup$ – rp.beltran Jun 16 '16 at 20:43
  • $\begingroup$ Thanks for the link though, and I think you may be right that my logic there is a bit off, I'm not sure. $\endgroup$ – rp.beltran Jun 16 '16 at 20:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Jal Jun 16 '16 at 20:51
  • 1
    $\begingroup$ 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$. $\endgroup$ – JMoravitz Jun 16 '16 at 21:37
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is brilliant. I have been thinking about this problem for a while now, and clearly the wrong way. Thanks. $\endgroup$ – rp.beltran Jun 16 '16 at 21:32
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think it's fair to say "a better explanation than joriki's answer" :-) $\endgroup$ – joriki Jun 16 '16 at 21:23
  • 1
    $\begingroup$ This helped me understand it a lot. Thank you. I would like to have accepted both versions, this was very well explained. $\endgroup$ – rp.beltran Jun 16 '16 at 21:32

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.