[Question]
  [
## Goal
You are given an integer `n` (`n > 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.
  
[Answer]
# Mathematica, 58 bytes, polynomial(*n*) time
```
Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&
```
### How it works
Rather than iterating over permutations with brute force, we use the [inclusion–exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) to count them combinatorially.
Let S be the set of all permutations of [1, …, n] with σ1 = 1, σ*n* = *n*, and let S*i* be the set of permutations σ ∈ S such that |σ*i* − σ*i* + 1| = 1. Then the count we are looking for is
|S| − |S1 ∪ ⋯ ∪ S*n* − 1| = ∑2 ≤ *k* ≤ *n* + 1; 1 ≤ *i*2 < ⋯ < *i**k* − 1 < *n* (−1)k − 2|S*i*2 ∩ ⋯ ∩ S*i**k* − 1|.
Now, |S*i*2 ∩ ⋯ ∩ S*i**k* − 1| only depends on *k* and on the number *j* of runs of consecutive indices in [*i*1, *i*2, …, *i**k* − 1, *i**k*] where for convenience we fix *i*1 = 0 and *i**k* = *n*. Specifically,
|S*i*2 ∩ ⋯ ∩ S*i**k* − 1| = 2*j* − 2(*n* − *k*)!, for 2 ≤ *j* ≤ *k* ≤ *n*,  
|S*i*2 ∩ ⋯ ∩ S*i**k* − 1| = 1, for *j* = 1, *k* = *n* + 1.
The number of such index sets [*i*1, *i*2, …, *i**k* − 1, *i**k*] with *j* runs is
(*k* − 1C*j* − 1)(*n* − *k*C*j* − 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* − 1C*j* − 1)(*n* − *k*C*j* − 2)2*j* − 2(*n* − *k*)!
The inner sum over *j* can be written using the [hypergeometric 2F1 function](https://en.wikipedia.org/wiki/Hypergeometric_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]&[n],{n,50}]
Out[1]= {1, 0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584, 4462848, 
>    54455754, 717909202, 10171232060, 154142811052, 2488421201446, 
>    42636471916622, 772807552752712, 14774586965277816, 297138592463202402, 
>    6271277634164008170, 138596853553771517492, 3200958202120445923684, 
>    77114612783976599209598, 1934583996316791634828454, 
>    50460687385591722097602304, 1366482059862153751146376304, 
>    38366771565392871446940748410, 1115482364570332601576605376898, 
>    33544252621178275692411892779180, 1042188051349139920383738392594332, 
>    33419576037745472521641814354312790, 
>    1105004411146009553865786545464526206, 
>    37639281863619947475378460886135133496, 
>    1319658179153254337635342434408766065896, 
>    47585390139805782930448514259179162696722, 
>    1763380871412273296449902785237054760438426, 
>    67106516021125545469475040472412706780911268, 
>    2620784212531087457316728120883870079549134420, 
>    104969402113244439880057492782663678669089779118, 
>    4309132147486627708154774750891684285077633835734, 
>    181199144276064794296827392186304334716629346180848, 
>    7800407552443042507640613928796820288452902805286368, 
>    343589595090843265591418718266306051705639884996218154, 
>    15477521503994968035062094274002250590013877419466108978, 
>    712669883315580566495978374316773450341097231239406211100, 
>    33527174671849317156037438120623503416356879769273672584588, 
>    1610762789255012501855846297689494046193178343355755998487686}
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 16 bytes
```
qtq:Y@0&Yc!d|qAs
```
[Try it online!](https://tio.run/##y00syfn/v7Ck0CrSwUAtMlkxpabQsfj/fwsA "MATL – Try It Online")
For inputs exceeding `12` it runs out of memory.
### Explanation
```
q      % Implicitly input n. Push n-1
tq     % Duplicate and subtract 1: pushes n-2
:      % Range [1 2 ... n-2]
Y@     % Matrix with all permutations, each in a row
0      % Push 0
&Yc    % Append n-1 and predend 0 to each row
!      % Tranpose
d      % Consecutive differences along each column
|      % Absolute value
q      % Subtract 1
A      % All: true if all values in each column are non-zero
s      % Sum. Implicitly display
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~17~~ 16 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
ṖḊŒ!ð1;;⁹IỊṀðÐḟL
```
A monadic link.
**[Try it online!](https://tio.run/##ASsA1P9qZWxsef//4bmW4biKxZIhw7AxOzvigblJ4buK4bmAw7DDkOG4n0z///84 "Jelly – Try It Online")**
### How?
```
ṖḊŒ!ð1;;⁹IỊṀðÐḟL - Link: number n
Ṗ                - pop (implicit range build) -> [1,n-1]
 Ḋ               - dequeue -> [2,n-1]
  Œ!             - all permutations of [2,n-1]
    ð       ðÐḟ  - filter discard those entries for which this is truthy:
     1;          -   1 concatenated with the entry
       ;⁹        -   ...concatenated with right (n)
         I       -   incremental differences
          Ị      -   is insignificant (absolute value <=1)
           Ṁ     -   maximum
               L - length (the number of valid arrangements)
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~19~~ 18 bytes
```
o2 á è_pU äÉ m²e>1
```
[Test it online!](http://ethproductions.github.io/japt/?v=1.4.5&code=bzIg4SDoX3BVIOTJIG2yZT4x&input=OA==) I would not recommend testing on anything larger than `10`.
### Explanation
```
o2 á è_  pU äÉ  m²  e>1
o2 á èZ{ZpU ä-1 mp2 e>1}
                          : Implicit: U = input integer
o2                        : Create the range [2..U-1].
   á                      : Generate all permutations of this range.
     èZ{               }  : Check how many permutations Z return a truthy value:
        ZpU               :   Push U to the end of Z.
            ä-1           :   Push 1 to the beginning of Z, then take the difference
                          :   of each pair of items.
                m         :   Map each item X to
                 p2       :     X ** 2. This gives a number greater than 1 unless the
                          :     item is 1 or -1.
                    e>1   :   Return whether every item in this list is greater than 1.
                          :   This returns `true` iff the permutation contains no
                          :   consecutive pairs of numbers.
                          : Implicit: output result of last expression
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 17 bytes
```
L¦¨œʒ¹1Š)˜¥Ä1å_}g
```
[Try it online!](https://tio.run/##ASYA2f8wNWFiMWX//0zCpsKoxZPKksK5McWgKcucwqXDhDHDpV99Z///OA "05AB1E – Try It Online")
[Answer]
## Haskell, ~~76~~ 65 bytes
Saved 11 bytes thanks to @xnor.
Using the result for `Q_rec` on page 7 of @ChristiaanWesterbeek's find, we get
```
f 1=1
f n|n<6=0
f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2]
```
I don't understand how their next result `ha` relates to this, but after speeding up (first by memoization, see earlier versions, then as below) I get their numbers.
While the above is okay for `n=20`, it is essentialy an example how not to do recursion. Here is a faster version (only for `n>=6`) that also would only need constant memory - if only the numbers didn't keep increasing...
```
f n=last$foldl(#)[1,0,0,0,0][6..n]
l#n=tail l++[sum$zipWith(*)l[n-4,1,10-2*n,4,n-2]]
```
That gives
```
Prelude> f 50
1610762789255012501855846297689494046193178343355755998487686
Prelude> f 500
659178618863924802757920269977240274180092211041657762693634630044383805576666007245903670780603497370173231423527767109899936008034229541700392144282505597945561328426013937966521561345817045884498867592832897938083071843810602104434376305964577943025310184523643816782047883794585616331928324460394146825636085453532404319881264974005968087265587062691285454120911586459406436421191277596121471930913837355151842093002557978076653884610826296845041929616496533544124347765641367732716560025553179112645454078955409181466212732427071306363820080109636358537270466838558068527692374178581063316309789026101221004745226182671038004326069705775312654329754698423385241664984156235692539255677944294995403233446243315371404887473868003155621849544566385172835597260848972758443874423271017007843907015007416644383573987606586308556317833384896267539628278571497402655322562624217658332870157802254043614726316296058329670971054977099155788604175817828380564156329839201579006169173002756295957371639199917376529472990059986681882194726437566769717959443857298155265292535858523609764515938314672724480762724541633037484152303637096
```
It's no problem to also get `f 5000` but I don't want to paste the result...
---
BTW, it's possible to not use fancy math and still not use (ultra) brute force. First, instead of looking at all permutations, look at partial permutations and only extend them when they are not already invalid. It's no use to look at all permutations starting with `1 6 5`. Second, some partial permutations like `1 3 5 7` and `1 5 3 7` have exactly the same valid continuations, so handle them together. Using these ideas, I could compute the values up to `n=16` in 0.3s.
[Answer]
# Python, 125 bytes
```
from itertools import*
lambda n:sum(p[-1]-p[0]==n-1and all(~-abs(x-y)for x,y in zip(p,p[1:]))for p in permutations(range(n)))
```
[Answer]
# Mathematica, 66 bytes
```
Count[Permutations@Range@#,x:{1,__,#}/;FreeQ[Differences@x,1|-1]]&
```
## Explanation
`Function` with first argument `#`.
```
Count[                                                             (* Count the number of *)
      Permutations@                                                (* permutations of *)
                   Range@#,                                        (* the list {1, ..., #} *)
                           x:{1,__,#}                              (* of the form {1, __, #} *)
                                     /;                            (* such that *)
                                             Differences@x,        (* the list of differences of consecutive elements *)
                                       FreeQ[                      (* is free of elements of the form *)
                                                           1|-1    (* 1 or -1 *)
                                                               ]]&
```
[Answer]
# Javascript (ES6), ~~100~~ ~~74~~ ~~72~~ 60 bytes
```
f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)
```
Below is the version before the golf-mastery of @PeterTaylor
```
f=n=>n<6?n==1|0:(n-4)*f(n-5)+f(n-4)-2*(n-5)*f(n-3)+4*f(n-2)+(n-2)*f(n-1)
```
Thanks to the answer from @ChristianSievers that managed to draft a Haskell solution from a [paper](http://algo.inria.fr/libraries/autocomb/graphs99.ps) that I found after googling '0, 2, 10, 68, 500, 4174, 38774, 397584', here's a Javascript version that does not permutate too.
Usage
```
for (i=1; i<=20; i++) {
  console.log(i, f(i))
}
1 1 
2 0 
3 0 
4 0 
5 0 
6 2 
7 10 
8 68 
9 500 
10 4174 
11 38774 
12 397584 
13 4462848 
14 54455754 
15 717909202 
16 10171232060 
17 154142811052 
18 2488421201446 
19 42636471916622 
20 772807552752712
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 26 bytes
```
{⟦₁pLh1&~tLs₂ᶠ{-ȧ>1}ᵐ}ᶜ|∧0
```
[Try it online!](https://tio.run/##AToAxf9icmFjaHlsb2cy//974p@m4oKBcExoMSZ@dExz4oKC4bagey3Ipz4xfeG1kH3htpx84oinMP//OP9a "Brachylog – Try It Online")
### Explanation
```
{                    }ᶜ       Output = count the number of outputs of:
 ⟦₁pL                           L is a permutation of [1, …, Input]
    Lh1                         The head of L is 1
       &~tL                     The tail of L is the Input
          Ls₂ᶠ                  Find all sublists of length 2 of L
              {    }ᵐ           Map on each sublist:
               -ȧ>1               The elements are separated by strictly more than 1
                       |      Else (no outputs to the count)
                        ∧0    Output = 0
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~109~~ ~~107~~ 102 bytes
```
q=lambda s,x,n:sum(q(s-{v},v,n)for v in s if(v-x)**2>1)if s else x<n;f=lambda n:q({*range(2,n)},1,n-1)
```
[Try it online!](https://tio.run/##NcxLDoIwEAbgq8yOGTI1Fl2hcpcaqTaB4VFsME3PXiHG7f/4xs/yGuSU83TrTH9/GPC8stT@3eOEXsWQOLCQHWYI4AQ8OItBrVSWVaPJ2S1pO9/CepWL/SNSTxjL2cizxWq7J9YsSlPeHbc7v@7M@kj1ODtZsIgJVAMxFYdt1ZsFHYNFR0T5Cw "Python 3 – Try It Online")
Removed four bytes by not trying to one-line the function (as suggested by @shooqie) and another byte by replacing `abs` with a square.
(Requires Python 3.5+)
[Answer]
# [Python 2](https://docs.python.org/2/), 136 bytes
-10 bytes thanks to @ovs.
```
lambda n,r=range:sum(x[0]<1and~-n==x[-1]and 2+~any(abs(x[i]-x[i+1])<2for i in r(n-1))for x in permutations(r(n)))
from itertools import*
```
[Try it online!](https://tio.run/##PYxBCsIwEEX3PcXsmthGbBERabxIzSKlrQ6YSZmmUBG9ekw3bj48/uNNr/DwVMdR3@LTuq63QCVrtnQfLvPixNoeTFNZ6r@KtF5bVZkEUBdfSy9huzkZaFSaojKyqUfPgIAELEhVUm68bjwN7JZgA3qaRTqllNnI3gGGgYP3zxnQTZ7DLv4b7bE8lWdzyQAmRgqQvz@grvD@5PskORsEljAKlDL@AA "Python 2 – Try It Online")
[Answer]
# Mathematica, 134 bytes
```
(s=Permutations@Range[2,#-1];g=Table[Join[Prepend[s[[i]],1],{#}],{i,Length@s}];Length@Select[Union@*Abs@*Differences/@g,FreeQ[#,1]&])&
```
  
test cases n: 2 to 12
> 
> {0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584}
> 
> 
> 
[Answer]
# [Python 2](https://docs.python.org/2/), 105 bytes
```
lambda n:reduce(lambda a,i:a+[i*a[-5]+a[-4]+2*(1-i)*a[-3]+4*a[-2]+(i+2)*a[-1]],range(2,n),[0,1]+4*[0])[n]
```
[Try it online!](https://tio.run/##LYpBDoIwEEWvMmHV0sHQihsSvEidRRXQSWQgDS4M4ewV1M1/@S9ves@PUVzqm0t6huHaBpA6du3r1qn/D8h1MJ7z4IsTmW0rMi5XtmC9uyOZaqcjo9i4r7NEGIPcO@VQNPoS7V75krQXSv0YgYEFfo1FZ3UNU2SZIVtWaM6wrNlhy4YwK0boFWudPg "Python 2 – Try It Online")
This is based on [Philippe Flajolet's paper](http://algo.inria.fr/libraries/autocomb/graphs99.ps) discovered by [@Christiaan Westerbeek](https://codegolf.stackexchange.com/users/58434/christiaan-westerbeek); it's much faster and two bytes shorter than my [Python 3 solution](https://codegolf.stackexchange.com/a/130059/25319) which enumerates the possible permutations. (In Python 3, `reduce` has annoyingly been moved to `functools`.)
There is a much shorter version using numpy's dot product, but that overflows quite rapidly and requires numpy to have been imported. But for what it's worth:
```
lambda n:reduce(lambda a,i:a+[dot([i,1,2-2*i,4,i+2],a[-5:])],range(2,n),[0,1]+4*[0])[n]
```
]