# Compute the Fibonomial Coefficient

## 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) \times f(2) \times ... \times f(n-1) \times f(n)$$

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

\begin{align}a(n, 0) & = 1 \\ a(n, k) & = \frac {g(n)} {g(n-k) \times g(k)} \\ & = \frac {f(n) \times f(n-1) \times ... \times f(n-k+1)} {f(1) \times f(2) \times ... \times f(k)} \end{align}

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

## 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. 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. Aug 6 '16 at 6:14

# 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. 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. Aug 5 '16 at 23:00
• Oh, that is actually not disallowed, thanks=) Aug 5 '16 at 23:00
• You can presumably divide twice to avoid parens.
– xnor
Aug 5 '16 at 23:01
• Now that we have this, the next thing could be the fibonomial transform ;-) 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 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


# 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: 304260 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}


# 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


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


# Mathematica, 30 bytes

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


# Jelly, 10 bytes

;ạ/RÆḞP€÷/


Try it online!

## How it works

;ạ/RÆḞP€÷/ - Main link. Takes [n, r] on the left
ạ/        - Calculate |n-r|
;          - Yield [n, r, |n-r|]
R       - Convert each to a range
ÆḞ     - For each integer i, yield the i'th Fibonacci number
P€   - Get the product of each array, yielding [g(n), g(r), g(n-r)]
÷/ - Yield g(n) ÷ g(r) ÷ g(n-r) = g(n) ÷ (g(r) × g(n-r))