OK, let’s see. I hope you’re ready to follow this…
I’m also assuming that you don’t want 20,1
Define properties E[sub]i[/sub] where E[sub]i[/sub] is true if i(i + 1)occurs in the new
permutation. Since we have a circular arrangement, E[sub]n[/sub] is the property that n1 occurs. The first step is to compute E[sub]i[/sub]. Now a permutation with property E[sub]i[/sub] can be thought of as a permutation of
1; 2; : : : ;(i(i + 1)); : : : ; n,
where we treat (i(i + 1)) as a single item. That is, we permute n - 1 objects in a circle. There are (n - 2)! ways of doing this.
Now consider E[sub]i[/sub] AND E[sub]j[/sub]. There are two cases depending on whether i + 1=j or i +1 < j. In the first case j = i +1, we are permuting the following objects:
1; 2; : : : ;(i(i +1)(i +2)); : : :; n
i(i +1)(i +2)is a single item. There are n - 2 objects, so the number of ways of doing this in a circle is (n - 3)!
In the second case j >i+1 we are permuting the objects:
1; 2; : : : ;(i(i +1)); : : :;(j(j + 1)); : : : ; n,
where i(i +1)and j(j +1) are single objects. But there are still n - 2 objects in total and hence (n - 3)! permutations.
In the general case where we consider k properties, no matter how the properties are ordered and what size “meta-objects” are created by combining integers, the total number of objects is reduced by the number of properties, which is k. So there will still be (n - k - 1)! permutations around a circle.
In this case, we are interested in the number of situations in which none of the E[sub]i[/sub]’s occur.
(n - 1)! - SUM[sub]k=2[/sub][sup]k = n-1[/sup]([sup]n[/sup]C[sub]k[/sub](n - k)!)
= (n - 1)! - SUM[sub]k=2[/sub][sup]k = n-1[/sup](n!/(k!(n - k)!)(n - k)!)
= (n - 1)! - SUM[sub]k=2[/sub][sup]k = n-1/sup
I’m sure that there is a simple way of evaluating this sum, but I’ve devoted enough time to it for now unfortunately. I’m gonna get in trouble unless I submit this now and get on with it.
So I did it on Excel instead (how inelegant!)
So for now, your answer is:
20! - “the sum from k = 2 to 19 of” (20! / k!)
which is negative. So I screwed up. Bollocks.
::scrutinizes sea of italics and superscripts::
Arse if I can see where the error is.
I’ll try later if noone has finished it off.