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 thefalling 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 theStirling 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*xin 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 iscode-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
- 1\$\begingroup\$I think
[1, 0, -2, 0, 1] -> [1, 6, 5, -1, 1]\$\endgroup\$att– att2025-11-03 04:36:14 +00:00CommentedNov 3 at 4:36 - \$\begingroup\$@att Thanks. Fixed.\$\endgroup\$alephalpha– alephalpha2025-11-03 05:35:42 +00:00CommentedNov 3 at 5:35
10 Answers10
Wolfram Language (Mathematica), 28 bytes
\!\(\_{x,#}#2\)/#!/.x->0&Input[k, p], wherep is a polynomial in terms ofx. Outputs\$c_k\$.
is\[DifferenceDelta]. This character has code pointU+F4A4; the documentation incorrectly claims that it has code pointU+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&Input[n, k, p], wheren is the degree of the polynomial andp is an ascending list of coefficients . Outputs\$c_k\$.
Jelly, 16bytes
Ḣ;J€×J+ŻƲ{\×"⁸SƲA monadic Link that accepts a list of integers, the monomial coefficients inascending order and yields the falling factorial coefficients inascending order.
Try it online! Or see thetest-suite (showing I/O indescending 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Ḣ;ȧJ€×J+ŻƲ{\×"⁸SƲ$ 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$$
Ḣ;J€×J+ŻƲ{\×"⁸SƲ - 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 ×"⁸ - {that} zipwise multiplied by {Rest} S - column-wise sum ; - {N} concatenate {that}
Jelly,14 11 bytes
LḶµ³ḅIƬZḢ÷!Input a list of coefficients in descending order. Output a list of coefficients in ascending order.
Port of myMathematica solution, since I was sad no one tried that approach.
I don't know Jelly. I spenthalf an hour clicking around the language spec trying to figure out how to do things.
LḶµ³ḅ evaluate p at 0..n I take successive differences Ƭ until stable, keeping intermediate values ZḢ first element of eachLḶµ ÷! divide by 0..n !- 1\$\begingroup\$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!\$\endgroup\$Unrelated String– Unrelated String2025-11-05 16:36:31 +00:00Commented14 hours ago
R,126114 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)))
Jelly, 26 bytes
cŻ$Ø-ṁ×Ɗׯ*¥SA:!{J’çþ`æ×@This is embarassingly long.
Takes and outputs the coefficients in little-endian order.
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 ddef 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
- \$\begingroup\$452 bytes\$\endgroup\$ceilingcat– ceilingcat2025-11-05 05:32:43 +00:00Commentedyesterday
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.
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.
ＦＬθLoop for\$ k \$ from\$ 0 \$ to\$ n \$.
⊞υＥθ⎇ι↨…§υ⊖ιλι¬λ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 arrayS[k][n].
ＩＥυΣ×θιOutput the dot product of each row ofS with the input.
JavaScript (ES6), 77 bytes
Expects an array of coefficients in ascending order. Returns an array in the same format.
a=>a.map((_,k)=>a.reduce((t,v,n)=>t+v*(s=n=>n?s(--n,k--)+ ++k*s(n):!k)(n),0))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 ordera.map((_, k) => // for each coefficient at index k in a[]: a.reduce( // for each coefficient v at index n in a[], (t, v, n) => // with t as the accumulator: t + // add to 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 is not 0: s(--n, k--) // compute S(n - 1, k - 1) + ++k * s(n) // + k * S(n - 1, k) : // else: !k // return 1 if k = 0, or 0 otherwise )(n), // initial call to s 0 // start with t = 0 ) // end of reduce()) // end of map()
Nekomata, 9 bytes
xbᶦ∆haxF/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 examplex 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]Explore related questions
See similar questions with these tags.