Objetivo

El objetivo de este desafío es producir una función nque calcule el número de formas de dividir la n X 1cuadrícula en triángulos donde todos los vértices de los triángulos se encuentran en los puntos de la cuadrícula.

Ejemplo

Por ejemplo, hay 14 formas de particionar la cuadrícula de 2 x 1, por lo que a f(2) = 14través de las siguientes particiones, las particiones tienen 2, 2, 2, 2, 4 y 2 orientaciones distintas, respectivamente.

Puntuación

Este es el código de golf , por lo que gana el código más corto.

05AB1E , 13 bytes

·LÉœÙεÅγo;P}O

Puerto de la respuesta Jelly de @Bubbler .

Muy lento debido a las permutaciones incorporadas.

Pruébelo en línea o verifique las primeras cuatro entradas .

Explicación:

·                # Double the (implicit) input
 L               # Create a list in the range [1, doubled_input]
  É              # Check for each if they're odd (1 if truthy, 0 is falsey)
                 # We now have a list of n 0s and n 1s (n being the input)
   œ             # Get all permutations of that list
    Ù            # Only leave the unique permutations
     ε     }     # Map each permutation to:
      Åγ         #  Run-length encode the current value (short for `γ€g`)
        o        #  Take 2 to the power for each
         ;       #  Halve each
          P      #  Take the product of the mapped permutation
            O    # Sum all mapped values together (and output implicitly)

Haskell , 60 55 54 52 bytes

Después de dibujar y programar muchos ejemplos, se me ocurrió que esto es lo mismo que el problema de las torres:

En un tablero de ajedrez $(n+1) \times (n+1)$ , ¿cuántas maneras hay para que una torre pase de $(0,0)$ a $(n,n)$ simplemente moviéndose a la derecha $+(1,0)$ o arriba $+(0,1)$ ?

Básicamente tiene la línea superior e inferior de la cuadrícula $1 \times n$ . Ahora debe completar la línea no horizontal. Cada triángulo debe tener dos líneas no horizontales. Si uno de sus lados es parte de la línea superior o inferior corresponde a la dirección y la longitud que tomaría en el problema de las torres. Este es OEIS A051708 . Como ilustración de esta correspondencia, considere los siguientes ejemplos. Aquí la línea superior corresponde a los movimientos hacia arriba, mientras que la línea inferior corresponde a los movimientos hacia la derecha.

¡Gracias @PeterTaylor por -6 bytes y @PostLeftGarfHunter por -2 bytes!

b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n

Pruébalo en línea!

Haskell , 42 bytes

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

Pruébalo en línea!

Una implementación bastante directa que recurre a más de 2 variables.

Así es como podemos obtener esta solución. Comience con el código que implementa una fórmula recursiva directa:

54 bytes

0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n

Pruébalo en línea!

Usando la interpretación de movimiento de torre de flawr , a%bes el número de caminos que llevan la torre de (a,b)a (0,0), usando solo movimientos para disminuir una coordenada. El primer movimiento disminuye ao disminuye b, manteniendo el otro igual, de ahí la fórmula recursiva.

49 bytes

a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n

Pruébalo en línea!

Podemos evitar la repetición map(a%)[0..b-1]++map(b%)[0..a-1]al notar que las dos mitades son iguales ae bintercambiadas. La llamada auxiliar a?bcuenta las rutas donde disminuye el primer movimiento a, y así b?acuenta aquellas donde disminuye el primer movimiento b. En general, estos son diferentes, y se suman a a%b.

La suma en a?btambién se puede escribir como una lista de comprensión a?b=sum[a%i|i<-[0..b-1]].

42 bytes

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

Pruébalo en línea!

Finalmente, nos deshacemos %y simplemente escribimos la recursión en términos de ?reemplazando a%icon a?i+i?aen la llamada recursiva.

El nuevo caso base hace que esto ?dé el doble de salidas que ?en la versión de 49 bytes, ya que con 0?0=1, tendríamos 0%0=0?0+0?0=2. Esto permite definir f n=n?nsin la reducción a la mitad que otros necesitaríamos hacer.

CJam (24 bytes)

{2,*e!{e`0f=:(1b2\#}%1b}

Demostración en línea

Esto usa el enfoque de Bubbler de Bubbler de sumar sobre permutaciones de n0s y n1s.

Disección

{         e# Define a block
  2,*     e#   Given input n, create an array of n 0s and n 1s
  e!      e#   Generate all permutations of that array
  {       e#   Map:
    e`    e#     Run-length encode
    0f=:( e#     Extract just the lengths and decrement them
    1b    e#     Sum
    2\#   e#     Raise 2 to the power of that sum
  }%
  1b      e#  Sum the mapped values
}

Enfoque alternativo (28 bytes)

{_1aa{_2$,f{j}@@,f{j}+1b}2j}

Demostración en línea

Disección

Todos los triángulos tienen un borde horizontal y dos bordes que unen las líneas horizontales. Etiquete los bordes no horizontales con una tupla de sus dos coordenadas x y ordene lexicográficamente. Entonces, el primer borde es (0,0), el último es (n,n), y dos bordes consecutivos difieren exactamente en una de las dos posiciones. Esto lo convierte en una recursión simple, que he implementado utilizando el operador de recursión memorizado j:

{            e# Define a block
  _          e#   Duplicate the argument to get n n
  1aa        e#   Base case for recursion: 0 0 => 1
  {          e#   Recursive body taking args a b
    _2$,f{j} e#     Recurse on 0 b up to a-1 b
    @@,f{j}  e#     Recurse on a 0 up to a b-1
    +1b      e#     Combine and sum
  }2j        e#   Memoised recursion with 2 args
}

Nota

Esta no es la primera vez que quiero fjrecibir soporte en CJam. Aquí también reduciría la puntuación a 24 bytes. Quizás debería intentar escribir un parche ...

Jalea , ₁₅ 14 bytes

Ø.xŒ!QŒɠ€’§2*S

Pruébalo en línea!

-1 byte basado en el comentario de Peter Taylor.

Utiliza la ilustración de flawr directamente, en lugar de la fórmula resultante.

Cómo funciona

Ø.xŒ!QŒɠ€’§2*S    Main link (monad). Input: positive integer N.
Ø.x               Make an array containing N zeros and ones
   Œ!Q            All unique permutations
      Œɠ€         Run-length encode on each permutation
         ’§       Decrement and sum each
           2*S    Raise to power of 2 and sum

Tome todas las rutas posibles en una cuadrícula cuadrada. El número de formas de mover unidades L en una dirección como torre es 2**(L-1). Aplique esto a cada ruta y sume la cantidad de formas de atravesar cada ruta.

Carbón , 44 31 bytes

tachado 44 sigue siendo regular 44

Ｆ⊕θ«≔⟦⟧ηＦ⊕θ⊞ηΣ∨⁺ηＥυ§λκ¹⊞υη»Ｉ⊟⊟υ

Pruébalo en línea! Explicación: funciona calculando el número de formas de dividir un trapecio de longitudes de lados opuestos m,nen triángulos que se encuentran en desplazamientos enteros. Este es simplemente un caso general del rectángulo de tamaño nen la pregunta. El número de particiones se da de forma recursiva como las sumas de los números de particiones para todos los lados m,0..n-1y n,0..m-1. Esto es equivalente al problema generalizado de las torres, OEIS A035002 . El código simplemente calcula el número de particiones que funcionan desde 0,0hasta el n,nuso de los valores calculados previamente a medida que avanza.

Ｆ⊕θ«

Pase sobre las filas 0..n.

≔⟦⟧η

Comience con una fila vacía.

Ｆ⊕θ

Pase sobre las columnas de la fila 0..n.

⊞ηΣ∨⁺ηＥυ§λκ¹

Lleve la fila hasta el momento y los valores en las filas anteriores en la columna actual, y agregue la suma total a la fila actual. Sin embargo, si no hay ningún valor, sustitúyalo 1en lugar de la suma.

⊞υη»

Agregue la fila terminada a la lista de filas hasta ahora.

Ｉ⊟⊟υ

Salida del valor final calculado.

JavaScript (ES6),  45 44  42 bytes

Utiliza la fórmula recursiva encontrada por Peter Taylor y flawr .

f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n

Pruébalo en línea!

Pari / GP , 43 bytes

Según OEIS , la función generadora de esta secuencia es

n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2

Pruébalo en línea!

Python 3 , 51 bytes

lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)

Pruébalo en línea!

Respuesta del puerto de flawr