Polynomial Basis Conversion

Question

The most common way to represent a polynomial is writing it as a linear combination of monomials, i.e., powers of the variable. For example, the polynomial \$p(x) = x^3 + 2x^2 + x + 1\$ is a linear combination of the monomials \$x^3\$, \$x^2\$, \$x\$, and \1ドル\$, with coefficients \1ドル\$, \2ドル\$, \1ドル\$, and \1ドル\$ respectively.

However, the monomial basis is not the only possible basis for polynomials. Another interesting basis, useful in combinatorics and some other areas of mathematics, is the falling factorial basis. The falling factorial of degree \$k\$ is defined as:

$$(x)_k = x (x - 1) (x - 2) \ldots (x - k + 1) = \prod_{i=0}^{k-1} (x - i).$$

In particular, \$(x)_0 = 1\$.

Any polynomial \$p(x)\$ of degree \$n\$ can be uniquely expressed as a linear combination of falling factorials \$(x)_0, (x)_1, \ldots, (x)_n\$. For example, the polynomial \$p(x) = x^3 + x^2 + x + 1\$ can be expressed in the falling factorial basis as:

$$p(x) = (x)_3 + 4 (x)_2 + 3 (x)_1 + (x)_0 = x (x - 1) (x - 2) + 4 x (x - 1) + 3 x + 1.$$

A possible way to find the coefficients in the falling factorial basis is using the Stirling numbers of the second kind. In fact,

$$x^n = \sum_{k=0}^{n} S(n, k) (x)_k,$$

where \$S(n, k)\$ is the Stirling number of the second kind, which counts the number of ways to partition a set of \$n\$ items into \$k\$ non-empty subsets.

Task

In this challenge, you are given a polynomial \$p(x)\$, and you need to find its representation in the falling factorial basis. Specifically, you need to find the coefficients \$c_0, c_1, \ldots, c_n\$ such that:

$$p(x) = c_n (x)_n + c_{n-1} (x)_{n-1} + \ldots + c_1 (x)_1 + c_0 (x)_0.$$

You may take the input polynomial \$p(x)\$ in any reasonable format. For example, the polynomial \$x^4 - 4x^3 + 5x^2 - 2x\$ may be represented as:

• a list of coefficients, in descending order: [1,-4,5,-2,0];
• a list of coefficients, in ascending order:[0,-2,5,-4,1];
• a string representation of the polynomial, with a chosen variable, e.g., "x^4-4*x^3+5*x^2-2*x";
• a built-in polynomial object, e.g., x^4-4*x^3+5*x^2-2*x in PARI/GP.

You may take the degree \$n\$ or the number of coefficients \$n + 1\$ as an additional input.

You may output the list of coefficients \$[c_n, c_{n-1}, \ldots, c_1, c_0]\$ in either ascending or descending order. You may also take an additional input \$k\$, and output the \$k\$-th coefficient \$c_k\$ only.

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

Test cases

Here the input polynomials are represented as lists of coefficients in descending order. The output are also in descending order.

[1] -> [1] # 1 => (x)_0
[1, 1] -> [1, 1] # x + 1 => (x)_1 + (x)_0
[1, 0, 0] -> [1, 1, 0] # x^2 => (x)_2 + (x)_1
[1, 2, 1] -> [1, 3, 1] # x^2 + 2 * x + 1 => (x)_2 + 3 * (x)_1 + (x)_0
[1, 1, 1, 1] -> [1, 4, 3, 1] # x^3 + x^2 + x + 1 => (x)_3 + 4 * (x)_2 + 3 * (x)_1 + (x)_0
[1, 2, 3, 4] -> [1, 5, 6, 4] # x^3 + 2 * x^2 + 3 * x + 4 => (x)_3 + 5 * (x)_2 + 6 * (x)_1 + 4 * (x)_0
[1, -1, 1, -1, 1] -> [1, 5, 5, 0, 1] # x^4 - x^3 + x^2 - x + 1 => (x)_4 + 5 * (x)_3 + 5 * (x)_2 + (x)_0
[1, 0, -2, 0, 1] -> [1, 6, 5, -1, 1] # x^4 - 2 * x^2 + 1 => (x)_4 + 6 * (x)_3 + 5 * (x)_2 - (x)_1 + (x)_0
[5, 4, 3, 2, 1] -> [5, 34, 50, 14, 1] # 5 * x^4 + 4 * x^3 + 3 * x^2 + 2 * x + 1 => 5 * (x)_4 + 34 * (x)_3 + 50 * (x)_2 + 14 * (x)_1 + (x)_0

• att: I think [1, 0, -2, 0, 1] -> [1, 6, 5, -1, 1]
• alephalpha: @att Thanks. Fixed.
• Rosario: There is a problem, or the question has in test all result reversed, or all answer solution return result reversed. For example in question f 1 0 0 is 1 1 0 where in all answer I seen f 1 0 0 is 0 1 1
• Rosario: So for input there is a definition of polynomial and for output one other?

Answer 1

Wolfram Language (Mathematica), 28 bytes

\!\(\_{x,#}#2\)/#!/.x->0&

Try it online!

Input [k, p], where p is a polynomial in terms of x. Outputs \$c_k\$.

 is \[DifferenceDelta]. This character has code point U+F4A4; the documentation incorrectly claims that it has code point U+2206. That character, ∆, is actually the similar-looking \[Laplacian] (undocumented).

Returns \$\frac{\Delta^k p(0)}{k!}\$, where \$\Delta^k p\$ is the \$k\$th "discrete derivative" of \$p\$, with \$\Delta\$ defined by \begin{align*} \Delta f(x)&=f(x+1)-(x). \end{align*}

How does it work?

We can start by computing the discrete derivative of the basis elements: \begin{align*} \Delta_x (x)_i&=(x+1)_i-(x)_i \\ &=\big((x+1) \times \cdots \times(x-i+2)\big) - \big(x \times \cdots \times (x-i+1)\big)\\ &=\big((x+1)-(x-i+1)\big)\times x \times \cdots \times (x-i+2)\\ &=i (x)_{i-1},\\ \Delta_x^k(x)_i&=\overbrace{\Delta\cdots\Delta}^k (x)_i =(i)_k (x)_{i-k}. \end{align*} Since \$\Delta\$ is linear, we now have \begin{align*} \Delta^k p(0)&=\left.\Delta_x^k \left(\sum_{i=0}^n c_i(x)_i\right)\right|_{x=0}\\ &=\left.\sum_{i=0}^n c_i\Delta_x^k (x)_i\right|_{x=0}\\ &=\left.\sum_{i=k}^n c_i(i)_k (x)_{i-k}\right|_{x=0}\\ &=c_k(k)_k= c_k k!. \end{align*}

(This may look familiar - if \$p(x)={\sum_{i=0}^n}a_i x^i\$, the coefficient of the \$x^k\$ term can be obtained by differentiation: \$D^k p(0)=a_k k!\$)

Wolfram Language (Mathematica), 27 bytes

0~Range~#~StirlingS2~#2.#3&

Try it online!

Input [n, k, p], where n is the degree of the polynomial and p is an ascending list of coefficients . Outputs \$c_k\$.

Answer 2

Jelly, 16 bytes

×ばつ"8SƲ

A monadic Link that accepts a list of integers, the monomial coefficients in ascending order and yields the falling factorial coefficients in ascending order.

Try it online! Or see the test-suite (showing I/O in descending order).

Note: a constant polynomial (an input of length one) yields an additional, redundant zero coefficient at \$x_1\$, I'm guessing that's acceptable, if not ×ばつ"8SƲ$ would work for \18ドル\$ bytes.

How?

Effectively employs the recurrence relation of Stirling numbers of the second kind, \$S(n, k)\$:

$$S(n+1, k) = k S(n, k) + S(n, k-1) \space \vert \space 0 \lt k \lt n$$ $$S(n, 0) = S(0, k) = 0$$ $$S(n, n) = 1$$

×ばつ"8SƲ - Link: list of integers, C
Ḣ - behead C -> removes the constant term, N, from C
 Ʋ - last four links as a monad - f(Rest)
 J€ - range of length of each -> [[1], [1], ..., [1]]
 \ - cumulative reduce by:
 Ʋ{ - last four links as a monad - f(Current (initially [1])):
 J - range of length -> [1..length(Current)]
 ×ばつ - {Current} multiplied by {that} (vectorises) -> M
 Ż - prefix {Current} with a zero
 + - {M} add {[0]+Current} (vectorises) -> next Current
 ×ばつ"8 - {that} zipwise multiplied by {Rest}
 S - column-wise sum
 ; - {N} concatenate {that}

Answer 3

Jelly, (削除) 14 (削除ここまで) 11 bytes

LḶμ3ḅIƬZḢ÷!

Try it online!

Input a list of coefficients in descending order. Output a list of coefficients in ascending order.

Port of my Mathematica solution, since I was sad no one tried that approach.

^{_{I don't know Jelly. I spent (削除) half (削除ここまで) an hour clicking around the language spec trying to figure out how to do things.}}

LḶμ3ḅ evaluate p at 0..n
 I take successive differences
 Ƭ until stable, keeping intermediate values
 ZḢ first element of each
LḶμ ÷! divide by 0..n !

• Unrelated String: No bytes saved, but compatible with function input and therefore a test harness. So feels like something more can be shaved off, but I've been trying for half an hour with no luck!

Answer 4

Python3, 498 bytes

from itertools import*
def R(a):
 d={}
 for i in a:
 for j in i:d[j]=d.get(j,0)+i[j]
 return d
def x(k):
 if k==0:return{0:1}
 q=[{1:1,0:-i}for i in range(k)]
 while len(q)>1:
 a,b,*q=q;d={}
 for j in a:
 for J in b:d[j+J]=d.get(j+J,0)+a[j]*b[J]
 q=[d]+q
 return q[0]
def f(p):
 P=[x(i)for i in range(len(p))]
 for E in count():
 for c in product(*[range(E)for _ in p]):
 u=R([{i:C*B[i]for i in B}for C,B in zip(c,P)])
 if all(u.get(k,0)==p.get(k,0)for k in range(max(*u,*p)+1)):return c

Try it online!

• ceilingcat: 452 bytes

Answer 5

Charcoal, 26 bytes

×ばつθι

Attempt This Online! Link is to verbose version of code. I/O is a list of coefficients in ascending order. Explanation: Uses @Arnauld's formula along with dynamic programming to calculate the Stirling numbers of the second kind.

FLθ

Loop for \$ k \$ from \$ 0 \$ to \$ n \$.

⊞υEθ⎇ι↨...§υ⊖ιλι¬λ

Calculate \$ S(n, k) = S(n - 1, k - 1) + k S(n - 2, k - 1) + k^2 S(n - 3, k - 1) + \dots \$ as this is a more convenient way to generate a transposed array S[k][n].

×ばつθι

Output the dot product of each row of S with the input.

Answer 6

R, (削除) 126 (削除ここまで) (削除) 114 (削除ここまで) 107 bytes

\(v,`^`=\(n,k)`if`(n<1,k<1,k*(n-1)^k+(n-1)^(k-1))*(k>=0))lapply(l<-(seq(v)-1),\(k)sum(v*sapply(l,\(n)n^k)))

Attempt This Online!

Answer 7

Jelly, 26 bytes

c×ばつ@

Attempt This Online!

This is embarassingly long.

Takes and outputs the coefficients in little-endian order.

Answer 8

JavaScript (ES6), 76 bytes

Expects an array of coefficients in ascending order. Returns an array in the same format.

a=>a.map((t,k)=>t-=a.map((v,n)=>t-=v*(s=n=>n?s(--n,k--)+ ++k*s(n):!k)(n))|t)

Try it online!

Method

This is based on the formula suggested in the challenge.

Given the coefficients \$a_0\$, \$a_1\$, ... \$a_N\$, we compute:

$$b_k=\sum_{n=k}^N a_nS(n,k)=\sum_{n=0}^N a_nS(n,k)$$

where \$S(n,k)\$ is the Stirling number of the second kind with the usual convention \$S(n,k)=0\$ for \$n<k\$.

Commented

a => // a[] = coefficients in ascending order
a.map((t, k) => // for each coefficient t at index k in a[]:
 t -= // subtract the result from the initial value of t
 a.map((v, n) => // for each coefficient v at index n in a[]:
 t -= // subtract from t ...
 v * ( // ... v multiplied by S(n, k)
 // actually implemented as s(n) where s is
 s = n => // a recursive function taking only n explicitly:
 n ? // if n ≠ 0:
 s(--n, k--) // compute S(n - 1, k - 1)
 + ++k * s(n) // + k * S(n - 1, k)
 : // else:
 !k // S(0, 0) = 1, S(0, k) = 0 for k ≠ 0
 )(n) // initial call to s
 ) | t // end of inner map(); return the final value of t
) // end of outer map()

Answer 9

Maple, 47 bytes

(p,k)->add(p[i]*Stirling2(i-1,k),i=1..nops(p));

Takes a list p in ascending order and non-negative integer k, and outputs the kth coefficient, using @Arnauld's formula.

Answer 10

Nekomata, 9 bytes

xbɪ∆haxF/

Attempt This Online!

A port of @att's Jelly answer, which in turn is based on @att's Mathematica answer. So make sure to upvote those answers as well!

Takes input as a list of coefficients in descending order. Outputs a list of coefficients in ascending order.

xbɪ∆haxF/ Takes [5,4,3,2,1] as an example
x Enumerate
 [5,4,3,2,1] -> [5,4,3,2,1], [0,1,2,3,4]
 b Convert to base, automatically vectorized
 [5,4,3,2,1], [0,1,2,3,4] -> [1,15,129,547,1593]
 1 is [5,4,3,2,1] to base 0, 15 is to base 1, etc.
 ɪ∆ Take differences zero or more times until failure
 [1,15,129,547,1593] -> [14,114,418,1046]
 [14,114,418,1046] -> [100,304,628]
 [100,304,628] -> [204,324]
 [204,324] -> [120]
 [120] -> []
 h Head
 [1,15,129,547,1593] -> 1
 [14,114,418,1046] -> 14
 [100,304,628] -> 100
 [204,324] -> 204
 [120] -> 120
 a All possible results
 [1,14,100,204,120]
 x Enumerate
 [1,14,100,204,120] -> [1,14,100,204,120], [0,1,2,3,4]
 F Factorial
 [0,1,2,3,4] -> [1,1,2,6,24]
 / Divide
 [1,14,100,204,120], [1,1,2,6,24] -> [1,14,50,34,5]

---

There is also an interesting combinatorial approach, but unfortunately it only works for inputs with non-negative coefficients.

Nekomata + -n, 7 bytes

x$y~O$L

Attempt This Online!

Takes a list of coefficients in ascending order and a number k, and outputs the k'th coefficient.

This is basically a combinatorial interpretation of the Stirling number approach.

x$y~O$L Takes [1,2,3,4,5], 4 as an example
x Enumerate
 [1,2,3,4,5] -> [1,2,3,4,5], [0,1,2,3,4]
 $ Swap
 [1,2,3,4,5], [0,1,2,3,4] -> [0,1,2,3,4], [1,2,3,4,5]
 y RLE decode
 [0,1,2,3,4], [1,2,3,4,5] -> [0,1,1,2,2,2,3,3,3,3,4,4,4,4,4]
 ~ Choose any element
 [0,1,1,2,2,2,3,3,3,3,4,4,4,4,4] -> e.g. 4
 O Set partition (integers are automatically converted to ranges)
 4 -> e.g. [[3],[2],[1],[0]]
 $ Swap
 4, [[3],[2],[1],[0]] -> [[3],[2],[1],[0]], 4
 L Check if the length of the first argument equals the second
 [[3],[2],[1],[0]], 4 -> [[3],[2],[1],[0]]

-n counts the number of possible solutions (with repetition). 4 is the only number in the list [0,1,1,2,2,2,3,3,3,3,4,4,4,4,4] that can be chosen to create a partition of length 4. And there are 5 4s in the list, so the output is 5.