Objetivo

Te dan un entero n( n > 1). Debe salida cuántas permutaciones de los enteros 1a nhay que comienzan en 1, al final n, y no tienen dos números enteros consecutivos que se diferencian por 1.

Alternativamente, si toma el gráfico completo K_ny elimina los bordes del camino 1-2-3-...-n, debe contar los caminos hamiltonianos desde 1hasta nen el gráfico restante.

Los ejemplos se usarán f(n)para una función que incorpore ny genere el número de permutaciones válidas, pero su envío puede ser una función o un programa.

Ejemplos

Para n = 6, una posible solución es1-3-5-2-4-6

Sin embargo, 1-3-5-2-6-4no es una solución válida ya que no termina con 6.

De hecho, para n = 6, solo hay 2 soluciones ( 1-4-2-5-3-6es la otra).

Por lo tanto f(6) = 2.

Porque n = 4las únicas permutaciones que comienzan 1y terminan en 4son 1-2-3-4y 1-3-2-4. En ambos, el 2es adyacente al 3, dando enteros consecutivos que difieren en 1. Por lo tanto f(4) = 0.

Casos de prueba

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

Criterio ganador

Este es el código de golf, gana la respuesta más corta.

MATL , 16 bytes

qtq:Y@0&Yc!d|qAs

Pruébalo en línea!

Para entradas que exceden 12se queda sin memoria.

Explicación

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

Mathematica, 58 bytes, tiempo polinomial ( n )

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

Cómo funciona

En lugar de iterar sobre permutaciones con fuerza bruta, usamos el principio de inclusión-exclusión para contarlas combinatoriamente.

Sea S el conjunto de todas las permutaciones de [1,…, n] con σ ₁ = 1, σ _n = n , y sea S _i el conjunto de permutaciones σ ∈ S tal que | σ _i - σ _{i + 1} | = 1. Entonces el conteo que estamos buscando es

| S | - | S ₁ ∪ ⋯ ∪ S _{n - 1} | = ∑ _{2 ≤ k ≤ n + 1; 1 ≤ i 2 <⋯ < i k - 1 < n} (−1) ^{k - 2} | S _{i 2} ∩ ⋯ ∩ S _{i k - 1} |.

Ahora, | S _{i 2} ∩ ⋯ ∩ S _{i k - 1} | solo depende de k y del número j de corridas de índices consecutivos en [ i ₁ , i ₂ , ..., i _{k - 1} , i _k ] donde por conveniencia arreglamos i ₁ = 0 e i _k = n . Específicamente,

| S _{i 2} ∩ ⋯ ∩ S _{i k - 1} | = 2 ^{j - 2} ( n - k ) !, para 2 ≤ j ≤ k ≤ n ,
| S _{i 2} ∩ ⋯ ∩ S _{i k - 1} | = 1, para j = 1, k = n + 1.

El número de tales conjuntos de índices [ i ₁ , i ₂ , ..., i _{k - 1} , i _k ] con j carreras es

( _{k - 1} C _{j - 1} ) ( _{n - k} C _{j - 2} ), para 2 ≤ j ≤ k ≤ n ,
1, para j = 1, k = n + 1.

El resultado es entonces

(−1) ^{n - 1} + ∑ _{2 ≤ k ≤ n} ∑ _{2 ≤ j ≤ k} (−1) ^{k - 2} ( _{k - 1} C _{j - 1} ) ( _{n - k} C _{j - 2} ) 2 ^{j - 2} ( n - k )!

La suma interior sobre j puede ser escrito utilizando el hipergeométrica ₂ F ₁ función :

(−1) ^{n - 1} + ∑ _{2 ≤ k ≤ n} (−1) ^k ( k - 1) ₂ F ₁ (2 - k , k - n ; 2; 2) ( n - k )!

a lo que aplicamos una transformación de Pfaff que nos permite eliminar los poderes de −1 usando un valor absoluto:

(−1) ^{n - 1} + ∑ _{2 ≤ k ≤ n} (−1) ⁿ ( k - 1) ₂ F ₁ ( k , k - n ; 2; 2) ( n - k )!
= | −1 + ∑ _{1 ≤ k ≤ n} ( k - 1) ₂ F ₁ ( k , k - n ; 2; 2) ( n - k )! |.

Manifestación

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}

Jalea , 17 16 bytes

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

Un enlace monádico.

Pruébalo en línea!

¿Cómo?

ṖḊŒ!ð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)

Japt , 19 18 bytes

o2 á è_pU äÉ m²e>1

¡Pruébelo en línea! No recomendaría probar en nada más grande que 10.

Explicación

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

05AB1E , 17 bytes

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

Pruébalo en línea!

Haskell, 76 65 bytes

Guardado 11 bytes gracias a @xnor.

Usando el resultado de la Q_recpágina 7 del hallazgo de @ ChristiaanWesterbeek, obtenemos

f 1=1
f n|n<6=0
f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2]

No entiendo cómo se relaciona su próximo resultado hacon esto, pero después de acelerar (primero por memorización, ver versiones anteriores, luego como a continuación) obtengo sus números.

Si bien lo anterior está bien n=20, es esencialmente un ejemplo de cómo no hacer recursión. Aquí hay una versión más rápida (solo para n>=6) que también necesitaría memoria constante, si solo los números no siguieran aumentando ...

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]]

Eso da

Prelude> f 50
1610762789255012501855846297689494046193178343355755998487686
Prelude> f 500
659178618863924802757920269977240274180092211041657762693634630044383805576666007245903670780603497370173231423527767109899936008034229541700392144282505597945561328426013937966521561345817045884498867592832897938083071843810602104434376305964577943025310184523643816782047883794585616331928324460394146825636085453532404319881264974005968087265587062691285454120911586459406436421191277596121471930913837355151842093002557978076653884610826296845041929616496533544124347765641367732716560025553179112645454078955409181466212732427071306363820080109636358537270466838558068527692374178581063316309789026101221004745226182671038004326069705775312654329754698423385241664984156235692539255677944294995403233446243315371404887473868003155621849544566385172835597260848972758443874423271017007843907015007416644383573987606586308556317833384896267539628278571497402655322562624217658332870157802254043614726316296058329670971054977099155788604175817828380564156329839201579006169173002756295957371639199917376529472990059986681882194726437566769717959443857298155265292535858523609764515938314672724480762724541633037484152303637096

No hay problema para obtener también, f 5000pero no quiero pegar el resultado ...

Por cierto, es posible no usar matemática elegante y aún no usar la fuerza (ultra) bruta. Primero, en lugar de mirar todas las permutaciones, mire las permutaciones parciales y solo extiéndalas cuando aún no sean inválidas. No sirve de nada mirar todas las permutaciones que comienzan con 1 6 5. En segundo lugar, algunas permutaciones parciales les gustan 1 3 5 7y 1 5 3 7tienen exactamente las mismas continuaciones válidas, por lo que deben manejarse juntas. Usando estas ideas, podría calcular los valores hasta n=16 en 0.3s.

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

Mathematica, 66 bytes

Count[Permutations@Range@#,x:{1,__,#}/;FreeQ[Differences@x,1|-1]]&

Explicación

Functioncon el primer argumento #.

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

A continuación se muestra la versión antes del dominio del golf de @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)

Gracias a la respuesta de @ChristianSievers que logró redactar una solución de Haskell a partir de un documento que encontré después de buscar en Google '0, 2, 10, 68, 500, 4174, 38774, 397584', aquí hay una versión de Javascript que tampoco se permuta.

Uso

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

Brachylog , 26 bytes

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

Pruébalo en línea!

Explicación

{                    }ᶜ       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 , 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)

Pruébalo en línea!

Se eliminaron cuatro bytes al no intentar una línea de la función (como lo sugiere @shooqie) y otro byte al reemplazar abscon un cuadrado. (Requiere Python 3.5+)

Python 2 , 136 bytes

-10 bytes gracias a @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*

Pruébalo en línea!

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

casos de prueba n: 2 a 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]

Pruébalo en línea!

Esto se basa en el artículo de Philippe Flajolet descubierto por @Christiaan Westerbeek ; es mucho más rápido y dos bytes más corto que mi solución Python 3 que enumera las posibles permutaciones. (En Python 3, reducese ha movido molestamente a functools).

Hay una versión mucho más corta que usa el producto de punto de numpy, pero se desborda rápidamente y requiere que se haya importado numpy. Pero por lo que vale:

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]