Permutation of n objects with restriction of adjacent pairs

Given $n$ objects with values $\{x_1,x_2,x_3,\dots,x_n\},$ and $m$ pairs $a_k = \{x_i,x_j\}$. Let $\{p_1,p_2,p_3,\dots,p_n\}$ be a permutation of objects. The question is to find number of permutations of objects such that none of the pairs $\{p_i,p_{i+1}\} \in a_k\ \forall i \in (1,n-1)$.

I tried to use inclusion-exclusion principle, first I took all the objects without any constraint. Then I picked number a pair $a_k$ and removed it from the total answer using inclusion-exclusion. But I was not able to solve it.

I don't assume the solution has a compact form, so I expect a procedure rather than an answer.

Solution 1:

This is essentially a computer program disguised as mathematics.

Let $X = \left\{x_1,x_2,\cdots,x_n\right\}$.

Define $N_{x_i} = X \setminus \displaystyle{\bigcup_{x_i \not \in a_j}} a_j$, the set of allowable neighbours of $x_i$ (note $x_i \not \in N_{x_i}$).

Define $F(A, S) = \left\{\begin{array}{ll}1&\text{if $S = \varnothing$}\\{\displaystyle\sum_{e\in A \cap S}}F(N_e,S\setminus\left\{e\right\})&\text{if $S \ne \varnothing$}\end{array}\right.$.

$F(A,S)$ counts the number of admissible permutations of $S$ that begin with an element in $A$. The number you want in your question is $F(X,X)$.

(Edit: Added following explanation, changed notation from $N_i$ to $N_{x_i}$)

$F$ counts the permutations the same way as you'd count them systematically by hand using $n$ friends to help. Seat your friends at desks $1,\cdots,n$ (you sit at desk $0$) and give them the following instructions:

1. You all have a bunch of lists $N_{x_i}$ that tell you what elements are OK to put next to $x_i$.

2. If you're sitting at desk $d$, wait for the person at desk $d-1$ to hand you two lists, $A$ and $S$.

3. Your job is to count the number of allowable permutations of $S$ that start with one of the elements from $A$.

4. Set your total to $0$.

5. For each $x_i \in S$, check whether $x_i \in A$. If $x_i \in A$ then make up two lists: $A' = N_{x_i}$ and $S' = S \setminus \left\{x_i\right\}$. Hand $A'$ and $S'$ to desk $d+1$. Wait for desk $d+1$ to hand you back a number. Add this to your total.

6. Hand your total back to the person at desk $d-1$.

7. Go to step 2.

Friend at desk $n$: "Wait, I don't have anyone to pass my lists on to!!"

You: "That's OK - whenever you try to pass on a list $S'$, it will be $\varnothing$. Just pretend the guy at desk $n+1$ hands you back a $1$ each time."

Then you hand your friend at desk $1$ the lists $A=X, S=X$. He eventually hands you back the number of allowable permutations. At this point you should tell everyone to stop, otherwise they'll be stuck waiting for more input.