Fibonacci polynomials

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.

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

The usual 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.

This is , 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]

• I assume a coefficient list for $n=0$ may be [0] rather than empty? Commented Jun 27, 2022 at 2:49
• @UnrelatedString Both are OK. For other $n$ you can also pad the results with $0$, e.g., [0,1] for $n=1$. Commented Jun 27, 2022 at 2:51
• 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? Commented Jun 30, 2022 at 3:59
• @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$. Commented Jun 30, 2022 at 4:01

J, 13 11 bytes

$1j1#]!&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. $1j1#]!&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)
$1j1# Insert a zero after each number and take first n numbers  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.  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. Factor + math.polynomials, 45 bytes { } .s { 1 } [ dup . tuck "\0"p* p+ t ] loop  Try it online! Prints the sequence forever as ascending coefficients. 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. JavaScript (Node.js), 37 bytes f=(n,k)=>n>1?f(n-1,k-1)+f(n-2,k):!k*n  Try it online! 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. • -2 bytes with [1]*n => [n] Commented Jun 27, 2022 at 6:07 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

+₌∷½⌊⁰ƈ*


Try it Online!

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.

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!

• 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. Commented Jun 27, 2022 at 21:23

Charcoal, 32 bytes

ＮθＦ⊕θ⊞υ⎇‹ι²ιΣＥ…⮌υ²×κ∨λＸχθＩ↨⊟υＸχθ


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

Ｎθ


Input n.

Ｆ⊕θ


Repeat n+1 times.

⊞υ⎇‹ι²ιΣＥ…⮌υ²×κ∨λＸχθ


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

Ｉ↨⊟υＸχθ


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

Python, 5852 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!

• 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. Commented Jun 27, 2022 at 13:16
• 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. Commented Jun 27, 2022 at 13:17
• Also using math.comb and import math rather than from math import* gives you -1 byte. Commented Jun 27, 2022 at 13:23
• Order of operations: //2 and >>1 are equivalent, but the latter have lower priority than addition, so you can drop parenthesis. Commented Jun 27, 2022 at 20:30

K (ngn/k), 22 bytes

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


Try it online!

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:

Ý¨Âc€¾RI£


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

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
€¾    # 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)

• +DÉ*<;²c also works for 8 bytes, outputting the k-th coefficient in the n-th polynomial Commented Jun 30, 2022 at 4:12
• @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. Commented Jun 30, 2022 at 7:23
• 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 Commented Jun 30, 2022 at 12:02
• @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. Commented Jun 30, 2022 at 12:05

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

APL (Dyalog Unicode), 22 bytes SBCS

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


Try it on APLgolf!