Fibonacci polynomials

Question

The Fibonacci polynomials are a polynomial sequence defined as:

• \$F_0(x) = 0\$
• \$F_1(x) = 1\$
• \$F_n(x) = x F_{n-1}(x) + F_{n-2}(x)\$

The first few Fibonacci polynomials are:

• \$F_0(x) = 0\$
• \$F_1(x) = 1\$
• \$F_2(x) = x\$
• \$F_3(x) = x^2 + 1\$
• \$F_4(x) = x^3 + 2x\$
• \$F_5(x) = x^4 + 3x^2 + 1\$

When you evaluate the Fibonacci polynomials for \$x=1\$, you get the Fibonacci numbers.

Task

Your task is to calculate the Fibonacci polynomial \$F_n(x)\$.

The usual sequence rules apply. So you may:

• Output all the Fibonacci polynomials.
• Take an input \$n\$ and output the \$n\$-th Fibonacci polynomial.
• Take an input \$n\$ and output the first \$n\$ Fibonacci polynomial.

You may use \0ドル\$-indexing or \1ドル\$-indexing.

You may output the polynomials in any reasonable format. Here are some example formats:

• a list of coefficients, in descending order, e.g. \$x^9+8x^7+21x^5+20x^3+5x\$ is represented as [1,0,8,0,21,0,20,0,5,0];
• a list of coefficients, in ascending order, e.g. \$x^9+8x^7+21x^5+20x^3+5x\$ is represented as [0,5,0,20,0,21,0,8,0,1];
• a function that takes an input \$n\$ and gives the coefficient of \$x^n\$;
• a built-in polynomial object.

You may pad the coefficient lists with \0ドル\$s. For example, the polynomial \0ドル\$ can represented as [], [0] or even [0,0].

You may also take two integers \$n, k\$, and output the coefficient of \$x^k\$ in \$n\$-th Fibonacci polynomial. You may assume that \$k<n\$.

This is code-golf, so the shortest code in bytes wins.

Testcases

Here I output lists of coefficients in descending order.

0 -> []
1 -> [1]
2 -> [1, 0]
3 -> [1, 0, 1]
4 -> [1, 0, 2, 0]
5 -> [1, 0, 3, 0, 1]
6 -> [1, 0, 4, 0, 3, 0]
7 -> [1, 0, 5, 0, 6, 0, 1]
8 -> [1, 0, 6, 0, 10, 0, 4, 0]
9 -> [1, 0, 7, 0, 15, 0, 10, 0, 1]
10 -> [1, 0, 8, 0, 21, 0, 20, 0, 5, 0]
11 -> [1, 0, 9, 0, 28, 0, 35, 0, 15, 0, 1]
12 -> [1, 0, 10, 0, 36, 0, 56, 0, 35, 0, 6, 0]
13 -> [1, 0, 11, 0, 45, 0, 84, 0, 70, 0, 21, 0, 1]
14 -> [1, 0, 12, 0, 55, 0, 120, 0, 126, 0, 56, 0, 7, 0]
15 -> [1, 0, 13, 0, 66, 0, 165, 0, 210, 0, 126, 0, 28, 0, 1]

• Unrelated String: I assume a coefficient list for \$n=0\$ may be [0] rather than empty?
• alephalpha: @UnrelatedString Both are OK. For other \$n\$ you can also pad the results with \0ドル\,ドル e.g., [0,1] for \$n=1\$.
• Command Master: Instead of output a function that takes an input m and gives the coefficient of x^m, can I take m as an additional input and give the coefficient of x^m?
• alephalpha: @CommandMaster Yes. You may also take two integers \$n, k\,ドル and output the coefficient of \$x^k\$ in \$n\$-th Fibonacci polynomial. You may assume that \$k<n\$.

Answer 1

J, ^{(削除) 13 (削除ここまで)} 11 bytes

1ドルj1#]!&i.-

Attempt This Online!

^{-2 bytes thanks to @ovs}

Looking at the nonzero columns, some keen eyes may have noticed that the columns look like binomial coefficients. And it actually is. (A related fact: summing the coefficients of nth polynomial gives nth Fibonacci number, which you can prove nicely in Lean)

...though we also need to handle the zero columns.

1ドルj1#]!&i.- A train that takes n, and gives a vector of descending coeffs
 ] - n and -n respectively
 &i. Apply range to both sides; 0..n-1 and n-1..0
 ! (right)C(left)
1ドルj1# Insert a zero after each number and take first n numbers

Answer 2

Jelly, 5 bytes

Ż+\¡1

Try it online!

Full program taking \$n\$ from STDIN and outputting coefficients ascending.

It's always felt a bit silly that the only "repeat" quick is designed for Fibonacci-like recurrences, but when it comes up I can't say it isn't useful.

 Since this is invoked as niladic, the initial left argument is 0.
 1 Starting with 1 on the right,
 ¡ repeat n times
 \ with the previous left argument replacing the right argument:
 + vectorized add the right argument to
Ż the left argument with a prepended 0.

Answer 3

R, 33 bytes

\(n,k,s=n+k)choose(s/2-.5,k)*s%%2

Attempt This Online!

Takes input as \$n,k\$ and outputs the coefficient of \$x^k\$ in \$n\$-th Fibonacci polynomial. Uses the formula from Wikipedia:

\$F(n,k) = {\frac{n+k-1}{2}\choose k}\$ if \$n\$ and \$k\$ have opposite parity.

Answer 4

Factor + math.polynomials, 45 bytes

{ } .s { 1 } [ dup . tuck "0円"p* p+ t ] loop

Try it online!

Prints the sequence forever as ascending coefficients.

Answer 5

Wolfram Language (Mathematica), 14 bytes

#~Fibonacci~x&

Try it online!

Returns a polynomial in \$x\$.

If \$n,x\$ were valid input, Fibonacci alone would do.

Answer 6

JavaScript (Node.js), 37 bytes

f=(n,k)=>n>1?f(n-1,k-1)+f(n-2,k):!k*n

Try it online!

Answer 7

Python, 62 bytes (@AnttiP)

f=lambda n:n>1and[*map(sum,zip(f(n-1)+[0]),[0,0]+f(n-2))]or[n]

Attempt This Online!

Old Python, 64 bytes

f=lambda n:n>1and[*map(sum,zip(f(n-1)+[0]),[0,0]+f(n-2))]or[1]*n

Attempt This Online!

Naive implementation of the defining recurrence.

• AnttiP: -2 bytes with [1]*n => [n]

Answer 8

Vyxal, 8 bytes

ʁḂ$ƈ0ZfẎ

Try it Online!

Same idea as Bubbler's J answer.

ʁḂ$ƈ0ZfẎ
ʁ # Exclusive zero range, 0..n-1
 Ḃ # Bifurcate, push reverse without popping
 $ # Swap
 ƈ # Binomial coefficients
 0Zf # Append zero after each
 Ẏ # Only keep the first input items

Porting pajonk's Python answer is 8 bytes as well:

Vyxal, 8 bytes

+=∷1⁄2⌊0ƈ*

Try it Online!

Answer 9

Python 2, 43 bytes

lambda n,k:2**(n*(n-~k))/(4**n-1)**-~k%2**n

Try it online!

Uses an arithmetic expression for the binomial adapted to \$ \binom{\frac{n+k-1}2}{k}\$ in a way that gives 0 if the top isn't a whole number.

Python 2, 48 bytes

f=lambda n,k:n>0and(k*k+n<2)+f(n-1,k-1)+f(n-2,k)

Try it online!

A recursive expression taken from tsh for Pascal's triangle but tilted.

Answer 10

Python3, 139 bytes:

def f(n):d={};F(n,d);return[d.get(i,0)for i in range(n-1,-1,-1)]
def F(n,d,c=0):
 if n==1:d[c]=d.get(c,0)+1
 if n>1:F(n-1,d,c+1);F(n-2,d,c)

Try it online!

• 301_Moved_Permanently: range(n-1,-1,-1) is range(n)[::-1] => -2; walrus operator lets you define a variable in a parameter list: F(n,d:={}) => -1; you can use else instead of if n==1 if you use +n instead of +1 => -3; changing f into a lambda lets you use or instead of ;return => -3. You are also technically allowed to return the coefficients in ascending order so you can use range(n) for an extra 6 bytes.

Answer 11

Charcoal, 32 bytes

×ばつκ∨λXχθI↨⊟υXχθ

Try it online! Link is to verbose version of code. Takes n as input and outputs the list of coefficients in descending order. Explanation:

Nθ

Input n.

F⊕θ

Repeat n+1 times.

×ばつκ∨λXχθ

Except for the first two numbers (which are just 0 and 1) multiply the last number by a very large base (10n) and add on the penultimate number.

I↨⊟υXχθ

Interpret the last value as a number in that very large base and output the "digits".

Answer 12

Python, (削除) 58 (削除ここまで) (削除) 52 (削除ここまで) 50 bytes

Edit: -8 bytes thanks to 301_Moved_Permanently.

lambda n,k:(n+k)%2*math.comb(n+k>>1,k)
import math

Attempt This Online!

Port of my R answer.

• 301_Moved_Permanently: You can change the and to * for -3 bytes, you can also drop the -1 as n+k is guaranteed an odd number and //2 will floor the result.
• Kevin Cruijssen: If you change (n+k) to (n:=n+k) (Python 3.8+), you can change the (n+k-1) to ~-n for -1. EDIT: Nvm, removing the -1 is indeed shorter, as mentioned in the comment above.
• 301_Moved_Permanently: Also using math.comb and import math rather than from math import* gives you -1 byte.
• 301_Moved_Permanently: Order of operations: //2 and >>1 are equivalent, but the latter have lower priority than addition, so you can drop parenthesis.

Answer 13

K (ngn/k), 22 bytes

{(0 0,x)+y,0}\[;!0;,1]

Try it online!

Answer 14

05AB1E, (削除) 8 (削除ここまで) 6 bytes

λ0š0ζO

Outputs the infinite 1-based sequence. The inner coefficient-lists are output in ascending order for -2 bytes.

Try it online.

Since I was curious, a port of @Bubbler's J answer would be 9 bytes :

Ý ̈Âc3ドル⁄4RI£

Outputs the 0-based \$n^{th}\$ list, in descending order.

Try it online or verify all test cases.

Explanation:

λ # Create a recursive environment,
 # to result in the infinite sequence
 # Implicitly starting at a(0)=1
 # Where every following a(n) is calculated as:
 # (implicitly push the a(n-2)'th and a(n-1)'th terms
 # (where a(-1)=0 in the first iteration)
 0š # Prepend a 0 in front of the top a(n-1)'th term
 # (which implicitly converts integers to digit-lists first)
 ζ # Pair and zip/transpose the two lists,
 0 # with 0 as filler since the lists are of unequal lengths
 O # Sum each inner pair
 # (after which the infinite sequence is output implicitly)
Ý # Push a list in the range [0, (implicit) input]
 ̈ # Remove the last item to make the range [0,input)
 Â # Bifurcate; short for Duplicate & Reverse copy
 c # Calculate the binomial coefficient of the values in the two lists at
 # the same positions
 3ドル⁄4 # Prepend a 0 in front of each item
 R # Reverse this list
 I£ # Keep just the first input amount of items
 # (after which this list is output implicitly as result)

• Command Master: +DÉ*<;²c also works for 8 bytes, outputting the k-th coefficient in the n-th polynomial
• Kevin Cruijssen: @CommandMaster That seems to output the 0-based \$(n-k-1)^{th}\$ coefficient (or 1-based \$(n-k)^{th}\$) in the \$n^{th}\$ polynomial, though. E.g. n=11,k=2 outputs 15 instead of 9: try it online.
• Command Master: The 11-th Fibonacci polynomial is \$ x^{10} + 9 x^8 + 28 x^6 + 35 x^4 + 15 x^2 + 1\,ドル and 15 is the coefficient of \$ x^2 \,ドル so 15 is a correct answer
• Kevin Cruijssen: @CommandMaster Good point. I was still looking at it from the descending list perspective, but if you explain it like that it indeed makes total sense! But maybe it's better if you post it as a separated answer? It's quite a bit different than mine, and I also already golfed 2 bytes off it.

Answer 15

Desmos, (削除) 62 (削除ここまで) 41 bytes

L=[n...0]
f(n)=mod(L+n,2)nCr((n+L-1)/2,L)

Function f outputs a list of coefficients in descending order, with a leading zero.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 16

APL (Dyalog Unicode), ^{(削除) (削除ここまで)}22 bytes ^SBCS

{a← ̄1+⍳⍵⋄⍵↑,⍉↑(a!⌽a)0}

Try it on APLgolf!