3
$\begingroup$

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$.

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Rather than frame your post as a comment (request for clarification) posing as an Answer, I suggest you rework this as a real Answer, stating any assumptions required (and explaining in detail what inclusion/exclusion or pinex can be used to find the solution). $\endgroup$
    – hardmath
    Commented Oct 11, 2014 at 17:20
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ No because at first you have to fix $1$ pair then you can vary the 2nd pair in $(n-3)$ positions then you vary the first pair in $(n-1)$ positions in each of it $(n-3)$ positions of 2nd pair will be there. Now you see that all combinations of two fix pairs are complete so you don't have to take $2!$ there. $\endgroup$
    – Ri-Li
    Commented Oct 11, 2014 at 20:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .