# Counting from 1 to n without any consecutive numbers

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

• You see, kids, you can't just check how many permutations of [2..n-1] contain no deltas of 1 or -1, you have to also check that none of them start with 2 or end with n-1... Jul 5, 2017 at 12:23
• Does the list have to start with 1 and end with the number?
– Okx
Jul 5, 2017 at 12:24
• Maybe the OP means "adjacent" not "consecutive"? Jul 5, 2017 at 18:18
• Bizarly the sequence is here: algo.inria.fr/libraries/autocomb/graphs99.ps where on page 6 is written Q_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 Jul 5, 2017 at 20:51
• @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! Jul 6, 2017 at 6:45

# 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 ≤ kn + 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(nk)!, for 2 ≤ jkn,
|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)(nkCj − 2), for 2 ≤ jkn,
1, for j = 1, k = n + 1.

The result is then

(−1)n − 1 + ∑2 ≤ kn2 ≤ jk (−1)k − 2(k − 1Cj − 1)(nkCj − 2)2j − 2(nk)!

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

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

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

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

### 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}

• My mind is blown, good job Jul 6, 2017 at 6:42

# MATL, 16 bytes

qtq:Y@0&Yc!d|qAs


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

• Working fine, well done :) Jul 5, 2017 at 14:10
• Although there were some really nice advancement into this problem, your solution is still the shortest. It is also faster than the Jelly one. Congratz! Jul 6, 2017 at 9:11

# Jelly, 17 16 bytes

ṖḊŒ!ð1;;⁹IỊṀðÐḟL


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)

• Sorry but it does not meet the test cases Jul 5, 2017 at 12:53
• Yeah, you made the same mistake Okx and I made at first. You have to account for the fact that the second number cannot be 2 and the second-to-last number cannot be n-1 Jul 5, 2017 at 12:56
• @Philippe fixed it up. Jul 5, 2017 at 13:49
• I don't think using IỊṀ is valid. Specifically, what if -2 is one of the deltas in there for example? You can fix with IAỊṀ for +1. Jul 5, 2017 at 14:13
• @JonathanAllan Ooh I thought it returned x <= 1. Jul 5, 2017 at 14:33

# Japt, 19 18 bytes

o2 á è_pU äÉ m²e>1


Test it online! 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

• Good job! Funny how my brute-force code can't get over n = 13 neither ahah Jul 5, 2017 at 12:26
• @Philippe I wouldn't recommend accepting so fast, I'm sure this will be shorter in 05AB1E or Jelly ;-) Jul 5, 2017 at 12:27
• Fails on testcase 1.
– Okx
Jul 5, 2017 at 12:31
• @Okx OP has specified that we can assume n > 1. Jul 5, 2017 at 12:35

# 05AB1E, 17 bytes

L¦¨œʒ¹1Š)˜¥Ä1å_}g


Try it online!

• It's not providing the right results, sorry Jul 5, 2017 at 12:12
• @Philippe On which testcase?
– Okx
Jul 5, 2017 at 12:13
• @Philippe Fixed.
– Okx
Jul 5, 2017 at 12:29
• ¹1Š)˜ saves a byte. Jul 5, 2017 at 23:01

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. • You can write the recursive expression shorter like a dot by extracting out the coefficients: f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2].
– xnor
Jul 6, 2017 at 1:59
• @xnor Right, thanks! Jul 6, 2017 at 2:53
• This is some good work, I'm astonished by the results this community came up with! Too bad it's a golf ^^ Jul 6, 2017 at 6:46

# 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)))

• Looks pretty fast, good job! Jul 5, 2017 at 14:09
• 117 bytes
– ovs
Jul 5, 2017 at 16:32

# 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 *)
]]&


# Javascript (ES6), 1007472 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 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

• The task description only asks for f(n) when n>1, so it doesn't matter what you return for n=1. Also I think f(1)=1 is correct. Jul 6, 2017 at 8:06
• You can combine the special cases as n<6?n==1|0: for a further two-char saving. Jul 6, 2017 at 8:09
• Great. I adjusted for those 2 comments. Jul 6, 2017 at 8:12
• And by reordering terms and relying on order of evaluation it's possible to get down to 60: f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n) Jul 6, 2017 at 8:27

# Brachylog, 26 bytes

{⟦₁pLh1&~tLs₂ᶠ{-ȧ>1}ᵐ}ᶜ|∧0


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


# Python 3, 109107 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!

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+)

• 103 bytes Jul 6, 2017 at 10:04

# Python 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!

• 136 bytes
– ovs
Jul 5, 2017 at 16:37

# 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}

# Python 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!

This is based on Philippe Flajolet's paper discovered by @Christiaan Westerbeek; it's much faster and two bytes shorter than my Python 3 solution 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]