How many permutations of N integers with K pairs of numbers that can't be adjacent?

Question

This is a computer science problem, I have a difficulty with the math part.

There are $n$ integers $\{1, 2,\dots, n\}$ and $K$ pairs of numbers $(a, b)$; $a \ne b$; $a, b \le n$. No pairs are identical. I have to find the number of permutations of all $b$ integers, where no $b$ from any pair is next to its $a$.

Example: $n=5,k=2$, and the pairs are $\{2,3\}$ and $\{1,4\}$. Then the permutation $4\;1\;3\;5\;2$ is okay, but the permutation $3\;1\;4\;2\;5$ is not.

The answer for the problem is 78 in this case (counted via a brute force computer program, checking every possibility).

If $k = 1$, the problem would be simple, as the answer is $n! - (n-1)!$. Here however, there are permutations containing more than one pair. Any help appreciated.

Edit: $n <= 1000000$, $k <= 100000$.

Answer 1

Since i have reputation under 50 I'm not allowed to post a comment, but I have to ask you some restrictions for N and K, since it is a algorithmic problem. If K is small, say under 20, you can use the principle of inclusion and exclusion, trying to find the number of permutations where at least one pair restriction is violated. Secondly, if K is not small, but a number x can be in at most one pair (i.e. cannot have (1,2) (1,3) ) you can also use pinex. Please answer this question for further help. Thanks!

P.S. The result depends on the elements of the pairs not only on the number of pairs. For example, if n=4 and the pairs are (1,2) and (2,3) the answer is 4. On the other hand if n=4 and the pairs are (1,2) and (3,4) the answer is 16. In conclusion, a formula dependent only on k does not exist. In other words, if there had been a formula the problem would have have depended only on n and k, and it is not.

Answer 2

I have found something more, If $k=2$, then It will be $n!-2(n-1)\times (n-2)!+(n-1)(n-3)(n-4)!$ The method I have applied is 1) Let every elements permute. Count all possibilities. 2) Just taking the first pair fix in the permutation & let others permute. Count all possibilities. 3) Do the same with the second pair. Count all possibilities. 4) Take both pair fixed & other permute. Count all possibilities.

Now the combination is 1)-2)-3)+4).

Similarly all possibilities for $k=3,4,..$ can be calculated.