9

Problema

Dado um valor n, imagine uma paisagem de montanha inscrita em uma referência (0, 0) a (2n, 0). Não deve haver espaços em branco entre as encostas e a montanha não deve descer abaixo do eixo x. O problema a ser resolvido é: dado n (que define o tamanho da paisagem) e o número k de picos (k sempre menor ou igual a n), quantas combinações de montanhas são possíveis com k picos?

Entrada

n quem representa a largura da paisagem ek qual é o número de picos.

Resultado

Apenas o número de combinações possíveis.

Exemplo

Dado n = 3 e k = 2, a resposta são 3 combinações.

Apenas para dar um exemplo visual, eles são os seguintes:

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

são as 3 combinações possíveis usando 6 posições (3 * 2) e 2 picos.

Editar: - mais exemplos -

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

Condição vencedora

Aplicam-se as regras de código-golfe padrão . O menor envio em bytes vence.

code-golf combinatorics recursion combinaçõesD
fonte

4

É o mesmo que, "encontre o número de expressões de npares de parênteses correspondentes que contêm exatamente kinstâncias de ()"?

xnor

4

https://oeis.org/A001263 ?

Xnor

@ xnor sim, é.

Jonathan Allan

4

Convém atualizar o desafio com um título mais explícito, como Compute Narayana Numbers .

Arnauld

Você pode confirmar se uma entrada com kzero deve ou não ser manipulada? Em caso afirmativo, uma entrada nigual a zero (com ktambém zero por definição) deve ser manipulada?

Jonathan Allan

7

Python, 40 bytes

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

Experimente online!

Usa a recorrência $a_{n,1} = 1$ , $a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}$ .

Anders Kaseorg
fonte

6

Geléia , 7 bytes

cⱮṫ-P÷⁸

Experimente online!

Recebe entrada como nentão k. Usa a fórmula

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

que eu encontrei na 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 linha funciona por si só.

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

Recebe entrada como kentão n.

7 bytes

cⱮ×ƝṪ÷⁸

Obrigado a Jonathan Allan por este.

dylnan
fonte

Espere ... cauda é definida automaticamente como 2 números? (Não sei Jelly em tudo, só uma pergunta boba)

Quintec

@Quintec Existem duas funções de cauda. Um ( Ṫ) que apenas pega o último elemento de um único argumento e o que eu usei ( ṫ) que usa dois argumentos. O primeiro argumento é uma lista e o segundo é um número (no meu caso, -1representado por um -no código), que informa quantos elementos salvar. Tendo -1dar dois elementos era o modo para definir golfiestṫ

dylnan

Peguei, obrigado! Eu vejo como geléia foi construído para o golfe ... hehe

Quintec

11

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

Jonathan Allan

4

JavaScript (ES6), 33 30 bytes

Guardado 3 bytes graças a @Shaggy

Toma entrada como (n)(k).

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

Experimente online!

Implementa a definição recursiva usada 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

Experimente online!

Computa:

{uma}_{n, k} = \frac{1 1}{k} (\binom{n - 1 1}{k - 1 1}) (\binom{n}{k - 1 1}) = \frac{1 1}{n} (\binom{n}{k}) (\binom{n}{k - 1 1}) = \frac{1 1}{n} {(\binom{n}{k})}^{2} \times \frac{k}{n - k + 1 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 (primeira fórmula).

Arnauld
fonte

-3 bytes com currying.

Shaggy

@ Shay Doh ... Obrigado. A revisão 7 finalmente parece que a revisão 1 deveria ter. : p

Arnauld 30/09

3

Wolfram Language (Mathematica) , 27 bytes

Três versões, todas do mesmo comprimento:

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

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

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

Experimente online! (Apenas a primeira versão, mas você pode copiar e colar para experimentar as outras.)

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

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

Misha Lavrov
fonte

2

J , 17 11 bytes

]%~!*<:@[!]

Experimente online!

Toma ncomo argumento certo, kcomo o esquerdo. Usa a mesma fórmula que a resposta Jelly de dylnan e a solução APL da Quintec.

Explicação:

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

Galen Ivanov
fonte

2

APL (Dyalog), 19 18 16 12 bytes

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

Obrigado a Galen Ivanov por -4 bytes

Usa a identidade na sequência OEIS. Pega k à esquerda en à direita.

TIO

Quintec
fonte

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

Galen Ivanov

@GalenIvanov Obrigado, meu APL tácito é extremamente fraco

Quintec

Meu APL como não é bom, eu só teve a oportunidade de experimentá-lo, depois de minha solução J :)

Galen Ivanov

1

Ruby , 50 bytes

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

Experimente online!

GB
fonte

1

Lisp comum , 76 bytes

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

Experimente online!

JRowan
fonte

Você pode salvar 2 bytes removendo os espaços após \ e depois de x

Galen Ivanov

11

Acabei de atualizar graças

JRowan

Sugerir em (*(1- x)x)vez de(* x(1- x))

ceilingcat 18/10/19

1

Perl 6 , 33 bytes

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

Experimente online!

Usa a fórmula

{uma}_{n, k} = (\binom{n - 1 1}{k - 1 1}) \times \frac{1 1}{k} (\binom{n}{k - 1 1}) = \prod_{Eu = 1 1}^{k - 1 1} (\frac{n - k}{Eu} + 1 1) \times \prod_{Eu = 2}^{k} (\frac{n - k}{Eu} + 1 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)$

Explicação

{[*]                            }  # 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.

Versão alternativa, 39 bytes

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

Experimente online!

Usa a fórmula da resposta de Arnauld:

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

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

Nwellnhof
fonte

0

Geléia , 8 bytes

,’$c’}P:

Um link diádico aceitando nà esquerda e kà direita que gera a contagem.

Experimente online!

Jonathan Allan
fonte

0

Stax , 9 bytes

ÇäO╪∙╜5‼O

Execute e depure

Estou usando a fórmula de dylnan em stax.

Descompactado, desmontado e comentado, o programa tem esta aparência.

        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

Execute este

recursivo
fonte

0

APL (NARS), 17 caracteres, 34 bytes

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

teste:

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

RosLuP
fonte

Diferentes combinações possíveis

Respostas:

Python, 40 bytes

Geléia , 7 bytes

JavaScript (ES6), 33 30 bytes

JavaScript (ES7), 59 58 49 45 bytes

Wolfram Language (Mathematica) , 27 bytes

J , 17 11 bytes

Explicação:

APL (Dyalog), 19 18 16 12 bytes

Ruby , 50 bytes

Lisp comum , 76 bytes

Perl 6 , 33 bytes

Explicação

Versão alternativa, 39 bytes

Geléia , 8 bytes

Stax , 9 bytes

APL (NARS), 17 caracteres, 34 bytes