Compute the Fibonomial Coefficient

Question

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

Task

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 code-golf so the shortest code wins.
Builtins are allowed.

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.

answered Aug 5, 2016 at 22:59

xnor

150k26 gold badges290 silver badges678 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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)

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 5, 2016 at 22:35

Theo

5195 silver badges14 bronze badges

\$\begingroup\$ 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. \$\endgroup\$

Dennis
– Dennis

2016-08-06 04:10:31 +00:00
Commented Aug 6, 2016 at 4:10

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 5, 2016 at 22:32

flawr

44.1k7 gold badges109 silver badges253 bronze badges

\$\begingroup\$ Can you do / rather than div? \$\endgroup\$

xnor
– xnor

2016-08-05 22:52:12 +00:00
Commented Aug 5, 2016 at 22:52
\$\begingroup\$ Hm yes, but that would end up in floating point numbers. \$\endgroup\$

flawr
– flawr

2016-08-05 23:00:13 +00:00
Commented Aug 5, 2016 at 23:00
\$\begingroup\$ You can presumably divide twice to avoid parens. \$\endgroup\$

xnor
– xnor

2016-08-05 23:01:55 +00:00
Commented Aug 5, 2016 at 23:01
\$\begingroup\$ Yes floats are allowed and there is no time limit so the recursive Fibonacci definition you used earlier was also valid. \$\endgroup\$

miles
– miles

2016-08-05 23:07:04 +00:00
Commented Aug 5, 2016 at 23:07
1

\$\begingroup\$ Now that we have this, the next thing could be the fibonomial transform ;-) \$\endgroup\$

Christian Sievers
– Christian Sievers

2016-08-05 23:55:06 +00:00
Commented Aug 5, 2016 at 23:55

| Show 2 more comments

Community · Accepted Answer · 2020-06-17 09:04:33Z

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
– miles, Commented Aug 6, 2016 at 2:53

Leaky Nun · Accepted Answer · 2016-08-06 05:25:51Z

3

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

answered Aug 6, 2016 at 5:25

Leaky Nun

50.7k9 gold badges116 silver badges291 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 6, 2016 at 10:10

Rudier

2,09910 silver badges21 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2017-04-13 12:39:07Z

1

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.

edited Apr 13, 2017 at 12:39

CommunityBot

1

answered Aug 6, 2016 at 4:37

Leaky Nun

50.7k9 gold badges116 silver badges291 bronze badges

Add a comment |

ASCII-only · Accepted Answer · 2016-08-06 01:26:04Z

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)

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

answered Aug 6, 2016 at 1:26

ASCII-only

5,17922 silver badges43 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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}

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 6, 2016 at 2:33

Value Ink

13.6k1 gold badge18 silver badges46 bronze badges

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:07Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 6, 2016 at 14:43

Mama Fun Roll

10k1 gold badge38 silver badges48 bronze badges

Add a comment |

user58988 · Accepted Answer · 2016-11-20 22:27:03Z

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

alephalpha · Accepted Answer · 2017-01-08 11:14:56Z

1

Mathematica, 30 bytes

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

answered Jan 8, 2017 at 11:14

alephalpha

52k7 gold badges75 silver badges198 bronze badges

Add a comment |

caird coinheringaahing · Accepted Answer · 2021-02-12 16:16:56Z

1

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

answered Feb 12, 2021 at 16:16

caird coinheringaahing♦

51.1k11 gold badges134 silver badges365 bronze badges

Add a comment |

Stack Exchange Network

Compute the Fibonomial Coefficient

Background

Task

Test Cases

Rules

Related

16 Answers 16

Haskell, 46 bytes

Python 67 bytes

Haskell, 77 57 55 52 50 bytes

C, 206 bytes:

Cheddar, 75 64 bytes

Usage

MATL, 25 23 bytes

Explanation

R, 120 bytes

Java: 304 260 257

Jelly, 16 bytes

JavaScript (ES6), 70 bytes

Ruby, 72 bytes

dc, 67 bytes

Julia, 53 bytes

Type: Tuple Fraction Integer

Mathematica, 30 bytes

Jelly, 10 bytes

How it works

Linked

Hot Network Questions