Calcule el coeficiente fibonomial

11

Antecedentes

La secuencia de Fibonacci se define como

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

El fibonorial, similar al factorial, es el producto de los primeros n números de Fibonacci.

g(n) = f(1) * f(2) * ... * f(n-1) * f(n)

El coeficiente fibonomial, similar al coeficiente binomial se define como

a(n, 0) = 1
a(n, k) = g(n) / ( g(n-k) * g(k) )
        = f(n) * f(n-1) * ... * f(n-k+1) / ( f(1) * f(2) * ... * f(k) )

Tarea

Su objetivo es crear una función o un programa para calcular el coeficiente de Fibonomial dado dos números enteros no negativos n y k con kn .

Casos de prueba

a(0, 0) = 1
a(1, 1) = 1
a(2, 0) = 1
a(3, 2) = 2
a(8, 3) = 1092
a(11, 5) = 1514513
a(22, 7) = 7158243695757340957617
a(25, 3) = 49845401197200
a(50, 2) = 97905340104793732225
a(100, 1) = 354224848179261915075

Reglas

  • Este es el por lo que gana el código más corto.
  • Las construcciones están permitidas.

Relacionado

millas
fuente
Si es necesario, aquí hay una página web que enumera los primeros 1335valores en la secuencia del Coeficiente Fibonomial.
R. Kap
¿El a(50, 2)caso de prueba falta un guión 9?
Joe
@SirBidenXVII Oh sí, tienes razón, me perdí un dígito.
millas

Respuestas:

1

Jalea , 16 bytes

0+⁸С1ḊP
;_/Ç€:/

Pruébalo en línea!

Créditos a Dennis por el enlace auxiliar de Fibonacci-orial.

;_/Ç€:/     Main chain,  argument: [n,r]
 _/         Find n-r
;           Attach it to original: [n,r,n-r]
   ǀ       Apply helper link to each element, yielding [g(n),g(r),g(n-r)]
     :/     Reduce by integer division, yielding g(n)//g(r)//g(n-r)

0+⁸С1ḊP    Helper link, argument: n
0+⁸С1ḊP    Somehow return the n-th Fibonacci-orial.
Monja permeable
fuente
4

Haskell, 46 bytes

l=0:scanl(+)1l;a%0=1;a%b=(a-1)%(b-1)*l!!a/l!!b

Salidas flotantes. Genera la lista infinita de Fibonacci. Luego, realiza la reclusión binomial, multiplicando y dividiendo por elementos de la lista de Fibonacci.

xnor
fuente
4

Python 67 bytes

f=lambda n,a=1,b=1:n<1or a*f(n-1,b,a+b)
lambda n,k:f(n)/f(k)/f(n-k)

Llamar usando a(n,k). Utiliza la respuesta fibonorial de @Dennis (¿está permitido?) Y una implementación directa de la pregunta de lo contrario.

Theo
fuente
Todo el contenido del usuario está licenciado bajo CC-BY-SA, por lo que siempre que proporcione la atribución, puede reutilizar el código de otras respuestas. Puedes acortar tu segunda lambda a lambda n,k:f(n)/f(k)/f(n-k); nombrarlo no es obligatorio.
Dennis
3

Haskell, 77 57 55 52 50 bytes

La primera línea proviene originalmente de la función de Fibonacci o el desafío de secuencia y fue escrita por @Anon.

La segunda línea fue agregada en el desafío de Fibonacci-orial por @ChristianSievers.

Ahora agregué la tercera línea. ¿Hasta dónde llegarán esos desafíos? =)

f=1:scanl(+)1f
g=(scanl(*)1f!!)
n#k=g n/g(n-k)/g k

Gracias por 5 bytes @xnor!

falla
fuente
¿Se puede hacer en /lugar de div?
xnor
Hm sí, pero eso terminaría en números de coma flotante.
flawr
Oh, eso en realidad no está prohibido, gracias =)
error
Presumiblemente puede dividir dos veces para evitar a los padres.
xnor
1
Ahora que tenemos esto, lo siguiente podría ser la transformación fibonomial ;-)
Christian Sievers
3

C, 206 bytes:

#include <inttypes.h>
uint64_t F(x){return x<1 ? 0:x==1 ? 1:F(x-1)+F(x-2);}uint64_t G(H,B){uint64_t P=1;for(B=3;B<=H;B++)P*=F(B);return P;}main(U,Y){scanf("%d %d",&U,&Y);printf("%llu\n",G(U)/(G(U-Y)*G(Y)));}

Tras la ejecución, solicita 2 enteros separados por espacios como entrada. Se requiere el#include preprocesador , ya que sin él, no es un tipo válido, y la única otra forma de hacer que esto funcione para salidas bastante grandes es usar tipos de retorno para las funciones (Fibonacci) y (Fibonorial), que es mucho más que simplemente incluyendo y utilizando 3 declaraciones de tipo. Sin embargo, incluso con eso, deja de funcionar correctamente en los valores de entrada (confirmado al usar esto , que enumera los primeros valores en la secuencia del coeficiente fibonomial), muy probablemente porque la representación de los números de Fibonacci y / o fibnorial desborda los 64 bits tipo entero usado.uint_64unsigned long longFG<inttypes.h>uint64_t14 1132515

¡C en línea! (Ideona)

R. Kap
fuente
Probablemente sea desde el desbordamiento de 15 desbordamientos fibonorialesuint_64
millas del
3

Cheddar , 75 64 bytes

a->b->(g->g((a-b+1)|>a)/g(1|>b))(n->n.map(Math.fib).reduce((*)))

Uso

cheddar> var f = a->b->(g->g((a-b+1)|>a)/g(1|>b))(n->n.map(Math.fib).reduce((*)))
cheddar> f(11)(5)
1514513
Monja permeable
fuente
2

MATL , 25 23 bytes

1ti2-:"yy+]vtPi:)w5M)/p

Pruébalo en línea!

Explicación

1t      % Push 1 twice
i2-:    % Take input n. Generate vector [1 2 ... n-2]
"       % Repeat n-2 times
  yy    %   Push the top two elements again
  +     %   Add them
]       % End
v       % Concatenate into column vector of first n Fibonacci numbers
tP      % Duplicate and reverse
i:      % Take input k. Generate vector [1 2 ... k]
)       % Apply index to get last k Fibonacci numbers
w       % Swap to move vector of first n Fibonacci numbers to top
5M      % Push [1 2 ... k] again
)       % Apply index to get first k Fibonacci numbers
/       % Divide element-wise
p       % Product of vector. Implicitly display
Luis Mendo
fuente
2

R, 120 bytes

Probablemente sea posible jugar un poco más al golf, por lo que los comentarios son bienvenidos.
Utilicé mi respuesta a la pregunta de Fibonacci-orial al comienzo del código:

A=function(n,k){p=(1+sqrt(5))/2;f=function(N){x=1;for(n in 1:N){x=prod(x,(p^n-(-1/p)^n)/sqrt(5))};x};f(n)/(f(k)*f(n-k))}

Sin golf:

A=function(n,k){
p=(1+sqrt(5))/2
    f=function(N){
        x=1
        for(n in 1:N){
           x=prod(x,(p^n-(-1/p)^n)/sqrt(5))
                     }
        x
        }

f(n)/(f(k)*f(n-k))
}
Frédéric
fuente
2

Java: 304 260 257

Ahorré algunos bytes al compactar un poco la función de memorización y eliminarla por f(n)completo, reemplazándola con acceso directo a la matriz.

BigInteger[]c;BigInteger a(int n,int k){m(n);return g(n).divide(g(n-k)).divide(g(k));}BigInteger g(int n){return n<3?BigInteger.ONE:g(n-1).multiply(c[n-1]);}void m(int n){c=new BigInteger[n];for(int i=0;i<n;++i)c[i]=(i<2)?BigInteger.ONE:c[i-2].add(c[i-1]);}

Lamentablemente, BigIntegeres necesario debido a desbordamientos y tuve que agregar una memoria. Incluso en un i7 generación 6, que estaba tomando forma demasiado tiempo en caso de grandes entradas.

Sin golf, con repetitivo classy maincódigo:

import java.math.BigInteger;

public class ComputeTheFibonomialCoefficient {

  public static void main(final String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "0", "0", "1" },
      { "1", "1", "1" },
      { "2", "0", "1" },
      { "3", "2", "2" },
      { "8", "3", "1092" },
      { "11", "5", "1514513" },
      { "22", "7", "7158243695757340957617" },
      { "25", "3", "49845401197200" },
      { "50", "2", "97905340104793732225" },
      { "100", "1", "354224848179261915075" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("a(" + data[0] + ", " + data[1] + ")");
      System.out.println("  Expected -> " + data[2]);
      System.out.print("    Actual -> ");
      System.out.println(new ComputeTheFibonomialCoefficient().a(
          Integer.parseInt(data[0]), Integer.parseInt(data[1])));
      System.out.println();
    }
  }

  // Begin golf

  BigInteger[] c;

  BigInteger a(int n, int k) {
    m(n);
    return g(n).divide(g(n - k)).divide(g(k));
  }

  BigInteger g(int n) {
    return n < 3 ? BigInteger.ONE : g(n - 1).multiply(c[n - 1]);
  }

  void m(int n) {
    c = new BigInteger[n];
    for (int i = 0; i < n; ++i)
      c[i] = (i < 2) ? BigInteger.ONE : c[i - 2].add(c[i - 1]);
  }
  // End golf
}

Salida del programa:

a(0, 0)
  Expected -> 1
    Actual -> 1

a(1, 1)
  Expected -> 1
    Actual -> 1

a(2, 0)
  Expected -> 1
    Actual -> 1

a(3, 2)
  Expected -> 2
    Actual -> 2

a(8, 3)
  Expected -> 1092
    Actual -> 1092

a(11, 5)
  Expected -> 1514513
    Actual -> 1514513

a(22, 7)
  Expected -> 7158243695757340957617
    Actual -> 7158243695757340957617

a(25, 3)
  Expected -> 49845401197200
    Actual -> 49845401197200

a(50, 2)
  Expected -> 97905340104793732225
    Actual -> 97905340104793732225

a(100, 1)
  Expected -> 354224848179261915075
    Actual -> 354224848179261915075

fuente
1

JavaScript (ES6), 70 bytes

a=n=>n<2?1:a(--n)+a(--n);b=n=>n?a(--n)*b(n):1;c=n=>k=>b(n)/b(n-k)/b(k)

Llamar usando c(n)(k), bastante sencillo.

Solo ASCII
fuente
1

cc, 67 bytes

?skdsn[si1d[sadlarla+zli>b*]sbzli>b*]dsgxsplnlk-lgxsqlklgxlprlqr*/f

La entrada se toma como constantes decimales delimitadas por espacios en una sola línea.

Esto usa mi respuesta a la /Fibon(acci-)?orial/pregunta, que multiplica todos los números en la pila en el último paso, requiriendo que los otros números se almacenen en otro lugar mientras se calculan los otros Fibonoriales.

?       # Take input from stdin
skdsn   # Store second number in register `k'; store a copy of first number in register `n'
[si1d[sadlarla+zli>b*]sbzli>b*] # Compute Fibonorial of top-of-stack, multiplying
                                #   until stack depth is 1
dsgx    # Store a copy of this function as g and execute it: g(n)
sp      # Store g(n) in register `p'
lnlk-   # Compute n-k
lgx     # Compute g(n-k)
sq      # Store g(n-k) in register `q'
lk lgx  # Compute g(k)
        # Top ---Down--->
lp      #  g(n)    g(k)
r       #  g(k)    g(n)
lq      #  g(n-k)  g(k)    g(n)
r       #  g(k)    g(n-k)  g(n)
*       # (g(k)g(n-k))     g(n)
/       #  g(n)/(g(k)g(n-k))
f       # Dump stack to stdout
Joe
fuente
1

Julia, 53 bytes

!x=[([1 1;1 0]^n)[2]for n=1:x]|>prod;n\k=!n/!(n-k)/!k

Créditos a @Lynn por su respuesta fibonorial .

Mama Fun Roll
fuente
1

Axioma 108 bytes

b(n,k)==(n<=k or k<1=>1;reduce(*,[fibonacci(i) for i in (n-k+1)..n])/reduce(*,[fibonacci(i) for i in 1..k]))

alguna prueba

(34) -> b(0,0),b(1,1),b(2,0),b(3,2),b(8,3),b(11,5),b(22,7)
   Compiling function b with type (NonNegativeInteger,
      NonNegativeInteger) -> Fraction Integer
   Compiling function b with type (PositiveInteger,PositiveInteger) ->
      Fraction Integer
   Compiling function b with type (PositiveInteger,NonNegativeInteger)
       -> Fraction Integer

   (34)  [1,1,1,2,1092,1514513,7158243695757340957617]
                                                 Type: Tuple Fraction Integer
(35) -> b(25,3),b(50,2),b(100,1)

   (35)  [49845401197200,97905340104793732225,354224848179261915075]

Tipo: Tuple Fraction Integer

RosLuP
fuente
1

Mathematica, 30 bytes

(f=Fibonorial)@#/f[#-#2]/f@#2&
alephalpha
fuente