Background

The Fibonacci sequence is defined as

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

The Fibonorial, similar to the factorial, is the product of the first n Fibonacci numbers.

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

The Fibonomial coefficient, similar to the binomial coefficient is defined as

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

Task

Your goal is to create a function or program to compute the Fibonomial coefficient given two non-negative integers n and k with kn.

Test Cases

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

Rules

  • This is so the shortest code wins.
  • Builtins are allowed.

Related

  • If needed, here is a webpage that lists the first 1335 values in the Fibonomial Coefficient sequence. – R. Kap Aug 6 '16 at 3:57
  • Is the a(50, 2) test case missing a leading 9? – Joe Aug 6 '16 at 6:09
  • @SirBidenXVII Oh yes, you're right I missed a digit. – miles Aug 6 '16 at 6:14

15 Answers 15

up vote 1 down vote accepted

Jelly, 16 bytes

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

Try it online!

Credits to Dennis for the Fibonacci-orial helper link.

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

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

Outputs floats. Generates the infinite Fibonacci list. Then, does the binomial recusion, multiplying and dividing by elements from the Fibonacci list.

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)

Call using a(n,k). Uses @Dennis fibonorial answer (is that allowed?), and a straightforward implementation of the question otherwise.

  • All user content is licensed under CC-BY-SA, so as long as you provide attribution, you can reuse code from other answers. You can shorten your second lambda to lambda n,k:f(n)/f(k)/f(n-k); naming it is not required. – Dennis Aug 6 '16 at 4:10

Haskell, 77 57 55 52 50 bytes

The first line is originally coming from the Fibonacci function or sequence challenge and was written by @Anon.

The second line was added in the Fibonacci-orial challenge by @ChristianSievers.

Now I added the third line. How much further will those challenges go?=)

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

Thanks for 5 bytes @xnor!

  • Can you do / rather than div? – xnor Aug 5 '16 at 22:52
  • Hm yes, but that would end up in floating point numbers. – flawr Aug 5 '16 at 23:00
  • Oh, that is actually not disallowed, thanks=) – flawr Aug 5 '16 at 23:00
  • You can presumably divide twice to avoid parens. – xnor Aug 5 '16 at 23:01
  • 1
    Now that we have this, the next thing could be the fibonomial transform ;-) – Christian Sievers Aug 5 '16 at 23:55

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

Upon execution, asks for 2 space separated integers as input. The #include preprocessor is required, as without it, uint_64 is not a valid type, and the only other way to make this work for fairly big outputs is using unsigned long long return types for both the F (Fibonacci) and G (Fibonorial) functions, which is much longer than just including the <inttypes.h> and using 3 uint64_t type declarations. However, even with that, it stops working correctly at input values 14 1 (confirmed by using this, which lists the first 1325 values in the Fibonomial Coefficient sequence), most likely because the Fibonacci and/or Fibnorial representation of numbers 15 and above overflow the 64-bit integer type used.

C It Online! (Ideone)

  • It's probably since the Fibonorial of 15 overflows uint_64 – miles Aug 6 '16 at 2:53

Cheddar, 75 64 bytes

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 bytes

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

Try it online!

Explanation

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

dc, 67 bytes

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

Input is taken as space-delimited decimal constants on a single line.

This uses my answer to the /Fibon(acci-)?orial/ question, which multiplies all numbers on the stack in the last step, requiring the other numbers to be stored elsewhere while the other Fibonorials are calculated.

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

R, 120 bytes

Some more golfing is probably be possible, so comments are of course welcomed !
I used my answer of the Fibonacci-orial question in the begining of the 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))}

Ungolfed :

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

I saved some bytes by compacting the memoization function a bit and removing f(n) entirely, replacing it with direct array access.

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

Unfortunately, BigInteger is required due to overflows and I had to add memoization. Even on a generation 6 i7, it was taking way too long to run with large inputs.

Ungolfed, with boilerplate class and main code:

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
}

Program output:

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

Call using c(n)(k), pretty straightforward.

Ruby, 72 bytes

Special thanks to @st0le for the really short Fibonacci generation code.

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

Julia, 53 bytes

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

Credits to @Lynn for his Fibonorial answer.

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

some 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 bytes

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.