9

Problema

Dado un valor n, imagine un paisaje de montaña inscrito en una referencia (0, 0) a (2n, 0). No debe haber espacios blancos entre las pendientes y tampoco la montaña debe descender por debajo del eje x. El problema a resolver es: dado n (que define el tamaño del paisaje) y el número k de picos (k siempre menor o igual que n), ¿cuántas combinaciones de montañas son posibles con k picos?

Entrada

n quién representa el ancho del paisaje yk cuál es el número de picos.

Salida

Solo la cantidad de combinaciones posibles.

Ejemplo

Dado n = 3 yk = 2, la respuesta es 3 combinaciones.

Solo para dar un ejemplo visual, son los siguientes:

   /\     /\      /\/\
/\/  \   /  \/\  /    \

son las 3 combinaciones posibles usando 6 (3 * 2) posiciones y 2 picos.

Editar: - más ejemplos -

n  k  result
2  1  1
4  1  1
4  3  6
5  2  10

Condición ganadora

Aplican reglas estándar de código de golf . La presentación más corta en bytes gana.

code-golf combinatorics recursion combinacionesD
fuente

44

¿Es esto lo mismo que "encontrar el número de expresiones de npares de paréntesis coincidentes que contienen kinstancias exactas de ()"?

xnor

44

https://oeis.org/A001263 ?

xnor

@xnor sí lo es.

Jonathan Allan

44

Es posible que desee actualizar el desafío con un título más explícito como Compute Narayana Numbers .

Arnauld

¿Podría confirmar si se kdebe manejar una entrada con cero? Si es así, ¿se debe manejar una entrada con nigual a cero (con ktambién cero por definición)?

Jonathan Allan

7

Python, 40 bytes

f=lambda n,k:k<2or~-n*n*f(n-1,k-1)/~-k/k

Pruébalo en línea!

Utiliza la recurrencia $a_{n,1} = 1$ , $a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}$ .

Anders Kaseorg
fuente

6

Jalea , 7 bytes

cⱮṫ-P÷⁸

Pruébalo en línea!

Toma entrada como nentonces k. Usa la fórmula

$N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}$

que encontré en Wikipedia .

cⱮṫ-P÷⁸
c        Binomial coefficient of n and...
 Ɱ       each of 1..k
  ṫ-     Keep the last two. ṫ is tail, - is -1.
    P    Product of the two numbers.
     ÷   Divide by
      ⁸  n.

7 bytes

Cada línea funciona por sí sola.

,’$c@P÷
c@€ṫ-P÷

Toma entrada como kentonces n.

7 bytes

cⱮ×ƝṪ÷⁸

Gracias a Jonathan Allan por este.

dylnan
fuente

Espera ... ¿la cola se define automáticamente como 2 números? (No conozco a Jelly en absoluto, solo una pregunta tonta)

Quintec

@Quintec Hay dos funciones de cola. Uno ( Ṫ) que solo toma el último elemento de un argumento único y el que usé ( ṫ) que toma dos argumentos. El primer argumento es una lista y el segundo es un número (en mi caso -1representado por un -en el código) que le indica cuántos elementos guardar. Tener -1dar dos elementos era la forma golfiest para definirṫ

dylnan

Gotcha, gracias! Veo cómo se construyó la gelatina para el golf ... jeje

Quintec

1

Otra variante para 7 f (n, k):cⱮ×ƝṪ÷⁸

Jonathan Allan

4

JavaScript (ES6), 33 30 bytes

Guardado 3 bytes gracias a @Shaggy

Toma entrada como (n)(k).

n=>g=k=>--k?n*--n/-~k/k*g(k):1

Pruébalo en línea!

Implementa la definición recursiva utilizada por Anders Kaseorg .

JavaScript (ES7), 59 58 49 45 bytes

Toma entrada como (n)(k).

n=>k=>k/n/(n-k+1)*(g=_=>k?n--/k--*g():1)()**2

Pruébalo en línea!

Calcula:

a_{n, k} = \frac{1}{k} (\binom{n - 1}{k - 1}) (\binom{n}{k - 1}) = \frac{1}{n} (\binom{n}{k}) (\binom{n}{k - 1}) = \frac{1}{n} {(\binom{n}{k})}^{2} \times \frac{k}{n - k + 1}

$a_{n,k}=\frac{1}{k}\binom{n-1}{k-1}\binom{n}{k-1}=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}=\frac{1}{n}\binom{n}{k}^2\times\frac{k}{n-k+1}$

Derivado de A001263 (primera fórmula).

Arnauld
fuente

-3 bytes con curry.

Shaggy

@Shaggy Doh ... Gracias. La revisión n. ° 7 finalmente parece ser la revisión n. ° 1. : p

Arnauld

3

Wolfram Language (Mathematica) , 27 bytes

Tres versiones, todas de la misma longitud:

(b=Binomial)@##b[#,#2-1]/#&

Binomial@##^2#2/(#-#2+1)/#&

1/(Beta[#2,d=#-#2+1]^2d##)&

Pruébalo en línea! (Solo la primera versión, pero puede copiar y pegar para probar las otras).

\frac{n! (n - 1)!}{k! (k - 1)! (n - k)! (n - k - 1)!}

$\frac{n!(n-1)!}{k!(k-1)!(n-k)!(n-k-1)!}$

Misha Lavrov
fuente

2

J , 17 11 bytes

]%~!*<:@[!]

Pruébalo en línea!

Toma ncomo argumento correcto, kcomo el izquierdo. Utiliza la misma fórmula que la respuesta Jelly de dylnan y la solución APL de Quintec.

Explicación:

            ] - n  
           !  - choose
       <:@[   - k-1
      *       - multiplied by
     !        - n choose k
   %~         - divided by
  ]           - n

Galen Ivanov
fuente

2

APL (Dyalog), 19 18 16 12 bytes

⊢÷⍨!×⊢!⍨¯1+⊣

Gracias a @Galen Ivanov por -4 bytes

Utiliza la identidad en la secuencia OEIS. Toma k a la izquierda yn a la derecha.

TIO

Quintec
fuente

⊢÷⍨!×⊢!⍨¯1+⊣para 12 bytes , argumento invertido

Galen Ivanov

@GalenIvanov Gracias, mi APL tácito es extremadamente débil

Quintec

Mi APL no es buena, simplemente aproveché la oportunidad para intentarlo, después de mi solución J :)

Galen Ivanov

1

Ruby , 50 bytes.

->l,n{eval [[*n..l]*2*?*,l,n,[*1..l-=n]*2,l+1]*?/}

Pruébalo en línea!

GB
fuente

1

Lisp común , 76 bytes

(defun x(n k)(cond((= k 1)1)(t(*(/(* n(1- n))(* k(1- k)))(x(1- n)(1- k))))))

Pruébalo en línea!

JRowan
fuente

Puede guardar 2 bytes eliminando los espacios después de \ y después de x

Galen Ivanov

1

Recién actualizado gracias

JRowan

Sugerir en (*(1- x)x)lugar de(* x(1- x))

ceilingcat

1

Perl 6 , 33 bytes

{[*] ($^n-$^k X/(2..$k X-^2))X+1}

Pruébalo en línea!

Usa la fórmula

a_{n, k} = (\binom{n - 1}{k - 1}) \times \frac{1}{k} (\binom{n}{k - 1}) = \prod_{i = 1}^{k - 1} (\frac{n - k}{i} + 1) \times \prod_{i = 2}^{k} (\frac{n - k}{i} + 1)

$a_{n,k}=\binom{n-1}{k-1}\times\frac{1}{k}\binom{n}{k-1}=\prod_{i=1}^{k-1}(\frac{n-k}{i}+1)\times\prod_{i=2}^{k}(\frac{n-k}{i}+1)$

Explicación

{[*]                            }  # Product of
     ($^n-$^k X/                   # n-k divided by
                (2..$k X-^2))      # numbers in ranges [1,k-1], [2,k]
                             X+1   # plus one.

Versión alternativa, 39 bytes.

{combinations(|@_)²/(1+[-] @_)/[/] @_}

Pruébalo en línea!

Utiliza la fórmula de la respuesta de Arnauld:

a_{n, k} = \frac{1}{n} {(\binom{n}{k})}^{2} \times \frac{k}{n - k + 1}

$a_{n,k}=\frac{1}{n}\binom{n}{k}^2\times\frac{k}{n-k+1}$

nwellnhof
fuente

0

Jalea , 8 bytes

,’$c’}P:

Un enlace diádico que acepta na la izquierda y ka la derecha que produce el recuento.

Pruébalo en línea!

Jonathan Allan
fuente

0

Stax , 9 bytes

ÇäO╪∙╜5‼O

Ejecutar y depurarlo

Estoy usando la fórmula de dylnan en stax.

Desempaquetado, sin golf y comentado, el programa se ve así.

        program begins with `n` and `k` on input stack
{       begin block for mapping
  [     duplicate 2nd element from top of stack (duplicates n)
  |C    combinatorial choose operation
m       map block over array, input k is implicitly converted to [1..k]
O       push integer one *underneath* mapped array
E       explode array onto stack
*       multiply top two elements - if array had only element, then the pushed one is used
,/      pop `n` from input stack and divide

Ejecute este

recursivo
fuente

0

APL (NARS), 17 caracteres, 34 bytes

{⍺÷⍨(⍵!⍺)×⍺!⍨⍵-1}

prueba:

  f←{⍺÷⍨(⍵!⍺)×⍺!⍨⍵-1}
  (2 f 1)(4 f 1)(4 f 3)(5 f 2)    
1 1 6 10

RosLuP
fuente

Diferentes combinaciones posibles

Respuestas:

Python, 40 bytes

Jalea , 7 bytes

JavaScript (ES6), 33 30 bytes

JavaScript (ES7), 59 58 49 45 bytes

Wolfram Language (Mathematica) , 27 bytes

J , 17 11 bytes

Explicación:

APL (Dyalog), 19 18 16 12 bytes

Ruby , 50 bytes.

Lisp común , 76 bytes

Perl 6 , 33 bytes

Explicación

Versión alternativa, 39 bytes.

Jalea , 8 bytes

Stax , 9 bytes

APL (NARS), 17 caracteres, 34 bytes