# Constrained Permutation Problem

This isn't homework -- just a problem I came up with to test my skills. I failed, for now.

A teacher must arrange $n$ students into a line, but $k$ pairs of the students cannot stand one another and will fight if they are placed next to each other. How many peaceful arrangements of the students are there?

If $k = 1$, we can characterize the admissible sequences as structures of the form

$$(C_1, \cdots, C_{i-1}, (C_i, (C_{i+1} \cdots C_{j-1}), C_j), \cdots C_n)$$

So that the triple in the sequence corresponds to the necessary arrangement where at least once child is between $C_i$ and $C_j$, the unruly students.

Given any such structure, there are $(2! * (n - 2)!)$ relabelings which preserve the invariant (since we only care that $C_i$ and $C_j$ are apart by some natural number of students)

Now I'm stuck counting the structures. It appears that it can be solved using an occupancy number model. There are $a$ students before the unruly triple, $(b+2)$ students in the triple, and $c$ students after the triple, so that $a + (b + 2) + c = n$, where $b \geq 1$.

Can anybody help finish the write up as presented? I didn't even get past the k=1 case. :(

Is there a slick argument I should learn? (I'm using these problems to come up with "short cut" flash cards to memorize)

-
Instead of trying to directly count the number of arrangements where students stand next to each other, consider counting the number of arrangements where they do stand next to each other and subtracting that from the total number of possible arrangements. – Joe Z. Feb 15 '13 at 21:43
If you're still stuck after Joe's complement hint, use the Principle of Inclusion and Exclusion. – Calvin Lin Feb 15 '13 at 23:09