Contexte

La séquence de Fibonacci est définie comme

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

Le Fibonorial, similaire au factoriel, est le produit des n premiers nombres de Fibonacci.

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

Le coefficient fibonomial, similaire au coefficient binomial, est défini comme

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

Tâche

Votre objectif est de créer une fonction ou un programme pour calculer le coefficient de Fibonomial étant donné deux entiers non négatifs n et k avec k ≤ n .

Cas de test

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

Règles

• C'est le code-golf donc le code le plus court l'emporte.
• Les Builtins sont autorisés.

en relation

• A000045 - Défi - Séquence de Fibonacci
• A003266 - Défi - Fibonorial
• A010048 - Coefficient fibonomial

Gelée , 16 octets

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

Essayez-le en ligne!

Remerciements à Dennis pour le lien d'assistance Fibonacci-oral.

;_/Ç€:/     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.

Haskell, 46 octets

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

Les sorties flottent. Génère la liste infinie de Fibonacci. Ensuite, la récusion binomiale se multiplie et se divise par les éléments de la liste de Fibonacci.

Python 67 octets

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)

Appelez en utilisant a(n,k). Utilise la réponse fibonoriale @Dennis (est-ce autorisé?), Et une implémentation simple de la question sinon.

Haskell, 77 57 55 52 50 octets

La première ligne provient à l'origine de la fonction ou du défi de séquence de Fibonacci et a été écrite par @Anon.

La deuxième ligne a été ajoutée dans le défi Fibonacci- oral par @ChristianSievers.

Maintenant, j'ai ajouté la troisième ligne. Jusqu'où iront ces défis? =)

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

Merci pour 5 octets @xnor!

C, 206 octets:

#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)));}

Lors de l'exécution, demande en entrée 2 entiers séparés par des espaces. Le #includepréprocesseur est requis , car sans lui, ce uint_64n'est pas un type valide, et la seule autre façon de faire fonctionner cela pour des sorties assez importantes est d'utiliser des unsigned long longtypes de retour pour les fonctions F(Fibonacci) et G(Fibonorial), ce qui est beaucoup plus long que juste y compris <inttypes.h>et en utilisant 3 uint64_tdéclarations de type. Cependant, même avec cela, il cesse de fonctionner correctement aux valeurs d'entrée 14 1(confirmées en utilisant ceci , qui répertorie les premières 1325valeurs de la séquence de coefficient fibibien), probablement parce que la représentation Fibonacci et / ou Fibnorial des nombres 15et au-dessus déborde le 64 bits type entier utilisé.

C It Online! (Ideone)

Cheddar , 75 64 octets

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

Usage

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

MATL , 25 23 octets

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

Essayez-le en ligne!

Explication

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

R, 120 octets

Un peu plus de golf est probablement possible, donc les commentaires sont bien sûr les bienvenus!
J'ai utilisé ma réponse à la question orale de Fibonacci au début du code:

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

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

Java: 304 260 257

J'ai économisé quelques octets en compactant un peu la fonction de mémorisation et en la supprimant f(n)entièrement, en la remplaçant par un accès direct au tableau.

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]);}

Malheureusement, BigIntegerest nécessaire en raison de débordements et j'ai dû ajouter la mémorisation. Même sur une génération 6 i7, cela prenait beaucoup trop de temps pour fonctionner avec de grandes entrées.

Non golfé, avec passe-partout classet maincode:

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
}

Sortie du programme:

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

JavaScript (ES6), 70 octets

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)

Appelez en utilisant c(n)(k), assez simple.

Rubis, 72 octets

Un merci spécial à @ st0le pour le code de génération Fibonacci vraiment court .

->n,k{f=[a=b=1,1]+(1..n).map{b=a+a=b}
r=->i{f[i,k].inject:*}
k>0?r[n-k]/r[0]:1}

dc, 67 octets

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

L'entrée est considérée comme des constantes décimales délimitées par des espaces sur une seule ligne.

Cela utilise ma réponse à la /Fibon(acci-)?orial/question, qui multiplie tous les numéros de la pile à la dernière étape, ce qui nécessite que les autres numéros soient stockés ailleurs pendant que les autres Fibonorials sont calculés.

?       # 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

Julia, 53 octets

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

Crédits à @Lynn pour sa réponse Fibonorial .

Axiome 108 octets

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

un test

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

Type: Tuple Fraction Integer

Mathematica, 30 octets

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