Counting from 1 to n without any consecutive numbers Goal

You are given an integer n (n &gt; 1). You must output how many permutations of the integers 1 to n there are which start at 1, end at n, and don't have two consecutive integers which differ by 1.

Alternatively, if you take the complete graph K_n and remove the edges of the path 1-2-3-...-n you must count the Hamiltonian paths from 1 to n in the remaining graph.

The examples will use f(n) for a function that takes in n and outputs the number of valid permutations, but your submission can be a function or a program.



Examples

For n = 6, a possible solution is 1-3-5-2-4-6

However, 1-3-5-2-6-4 is not a valid solution since it does not end with 6.

In fact, for n = 6, there are only 2 solutions (1-4-2-5-3-6 is the other one).

Hence f(6) = 2.



For n = 4 the only permutations which start in 1 and end in 4 are 1-2-3-4 and 1-3-2-4. In both of them the 2 is adjacent to the 3, giving consecutive integers which differ by 1. Therefore f(4) = 0.



Test cases

f(6) = 2
f(4) = 0
f(8) = 68
f(13) = 4462848




Winning criterion

This is code-golf, the shortest answer wins.
Mathematica, 58 bytes, polynomial(n) time

Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&amp;


How it works

Rather than iterating over permutations with brute force, we use the inclusion–exclusion principle to count them combinatorially.

Let S be the set of all permutations of [1, …, n] with σ1 = 1, σn = n, and let Si be the set of permutations σ ∈ S such that |σi − σi + 1| = 1.  Then the count we are looking for is

|S| − |S1 ∪ ⋯ ∪ Sn − 1| = ∑2 ≤ k ≤ n + 1; 1 ≤ i2 &lt; ⋯ &lt; ik − 1 &lt; n (−1)k − 2|Si2 ∩ ⋯ ∩ Sik − 1|.

Now, |Si2 ∩ ⋯ ∩ Sik − 1| only depends on k and on the number j of runs of consecutive indices in [i1, i2, …, ik − 1, ik] where for convenience we fix i1 = 0 and ik = n. Specifically,

|Si2 ∩ ⋯ ∩ Sik − 1| = 2j − 2(n − k)!, for 2 ≤ j ≤ k ≤ n,
|Si2 ∩ ⋯ ∩ Sik − 1| = 1, for j = 1, k = n + 1.

The number of such index sets [i1, i2, …, ik − 1, ik] with j runs is

(k − 1Cj − 1)(n − kCj − 2), for 2 ≤ j ≤ k ≤ n,
1, for j = 1, k = n + 1.

The result is then

(−1)n − 1 + ∑2 ≤ k ≤ n ∑2 ≤ j ≤ k  (−1)k − 2(k − 1Cj − 1)(n − kCj − 2)2j − 2(n − k)!

The inner sum over j can be written using the hypergeometric 2F1 function:

(−1)n − 1 + ∑2 ≤ k ≤ n (−1)k(k − 1)2F1(2 − k, k − n; 2; 2)(n − k)!

to which we apply a Pfaff transformation that lets us golf away the powers of −1 using an absolute value:

(−1)n − 1 + ∑2 ≤ k ≤ n (−1)n(k − 1)2F1(k, k − n; 2; 2)(n − k)!
= |−1 + ∑1 ≤ k ≤ n (k − 1)2F1(k, k − n; 2; 2)(n − k)!|.

Demo

In[1]:= Table[Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&amp;[n],{n,50}]

Out[1]= {1, 0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584, 4462848, 

&gt;    54455754, 717909202, 10171232060, 154142811052, 2488421201446, 

&gt;    42636471916622, 772807552752712, 14774586965277816, 297138592463202402, 

&gt;    6271277634164008170, 138596853553771517492, 3200958202120445923684, 

&gt;    77114612783976599209598, 1934583996316791634828454, 

&gt;    50460687385591722097602304, 1366482059862153751146376304, 

&gt;    38366771565392871446940748410, 1115482364570332601576605376898, 

&gt;    33544252621178275692411892779180, 1042188051349139920383738392594332, 

&gt;    33419576037745472521641814354312790, 

&gt;    1105004411146009553865786545464526206, 

&gt;    37639281863619947475378460886135133496, 

&gt;    1319658179153254337635342434408766065896, 

&gt;    47585390139805782930448514259179162696722, 

&gt;    1763380871412273296449902785237054760438426, 

&gt;    67106516021125545469475040472412706780911268, 

&gt;    2620784212531087457316728120883870079549134420, 

&gt;    104969402113244439880057492782663678669089779118, 

&gt;    4309132147486627708154774750891684285077633835734, 

&gt;    181199144276064794296827392186304334716629346180848, 

&gt;    7800407552443042507640613928796820288452902805286368, 

&gt;    343589595090843265591418718266306051705639884996218154, 

&gt;    15477521503994968035062094274002250590013877419466108978, 

&gt;    712669883315580566495978374316773450341097231239406211100, 

&gt;    33527174671849317156037438120623503416356879769273672584588, 

&gt;    1610762789255012501855846297689494046193178343355755998487686}