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 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 < ⋯ < ik − 1 < 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]&[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}
7You see, kids, you can't just check how many permutations of
[2..n-1]
contain no deltas of1
or-1
, you have to also check that none of them start with2
or end withn-1
... – ETHproductions – 2017-07-05T12:23:27.1131Does the list have to start with 1 and end with the number? – Okx – 2017-07-05T12:24:09.373
To fix ETH's comment, what you should be checking (to work for 1) is check the amount of permutations that 1. Start with 1, 2. End with n, 3. Do not contain consecutive numbers. – Okx – 2017-07-05T12:46:28.517
@Okx Then brute-force solutions would either be a few bytes longer to handle the special case of 1, or even slower than they are already... :P – ETHproductions – 2017-07-05T12:52:09.810
I understand your point, thought I'd rather not add any rule that will eliminate existing answers. Plus I think the 1 rule is arbitrary and has no meaning in the problem. – Philippe – 2017-07-05T12:52:53.890
It seems there is no entry for this sequence in OEIS. Perhaps it deserves to be, what do you think? – Luis Mendo – 2017-07-05T14:04:26.917
Haha yeah I looked for it. I don't know, I'm curious to see if it has other applications. I might turn that problem to a fastest-code later ahah! – Philippe – 2017-07-05T14:05:55.250
I presume that "without any consecutive numbers" means "without any two-element sublists in which the second is one greater than the first" (because any list of two or more elements which only contains integers must contain consecutive elements which are numbers, so although that's the simpler interpretation in general the context rules it out). However,
– Peter Taylor – 2017-07-05T16:24:44.020[0 2 1 3]
would therefore be a valid permutation, which conflicts with the test cases. Cf A000757.3Maybe the OP means "adjacent" not "consecutive"? – Stilez – 2017-07-05T18:18:32.130
6
Bizarly the sequence is here: http://algo.inria.fr/libraries/autocomb/graphs99.ps where on page 6 is written
– Christiaan Westerbeek – 2017-07-05T20:51:47.647Q_ser:=z + 2 z^6 + 10 z^7 + 68 z^8 + 500 z^9 + 4174 z^10 + 38774 z^11 + 397584z^12 + 4462848 z^13 + 54455754 z^14
I spend some time now trying to use the formulas, but I can't compose one that generates the sequence. Amazing to see the the exponent of z is the input of the formula and the outcome is the multiplication factor. The one how can deduce the formula from there may be one with the shortest answer in bytes@ChristiaanWesterbeek Amazing find! I could use a result from page 7, but I'm far from beating the size of the golfing language solutions. – Christian Sievers – 2017-07-05T23:41:30.817
1
@ChristiaanWesterbeek that's called the generating function for the sequence. There exist many sequences with a generating function that has a nicer closed form than the sequence itself, it's cool stuff!
– Carmeister – 2017-07-06T06:45:42.007I know generating function as I did some advanced maths, but never got to that level. It's a real blast ahah! – Philippe – 2017-07-06T06:48:03.963