Calculate Power Series Coefficients

Question

Given a polynomial \$p(x)\$ with integral coefficients and a constant term of \$p(0) = \pm 1\$, and a non-negative integer \$N\$, return the \$N\$-th coefficient of the power series (sometimes called "Taylor series") of \$f(x) = \frac{1}{p(x)}\$ developed at \$x_0 = 0\$, i.e., the coefficient of the monomial of degree \$N\$.

The given conditions ensure that the power series exist and that the its coefficients are integers.

Details

As always the polynomial can be accepted in any convenient format, e.g. a list of coefficients, for instance \$p(x) = x^3-2x+5\$ could be represented as [1,0,-2,5].

The power series of a function \$f(x)\$ developed at \$0\$ is given by

$$f(x) = \sum_{k=0}^\infty{\frac{f^{(n)}(0)}{n!}x^n}$$

and the \$N\$-th coefficient (the coefficient of \$x^N\$) is given by

$$\frac{f^{(N)}}{N!}$$

where \$f^{(n)}\$ denotes the \$n\$-th derivative of \$f\$

Examples

• The polynomial \$p(x) = 1-x\$ results in the geometric series \$f(x) = 1 + x + x^2 + ...\$ so the output should be \$1\$ for all \$N\$.

• \$p(x) = (1-x)^2 = x^2 - 2x + 1\$ results in the derivative of the geometric series \$f(x) = 1 + 2x + 3x^2 + 4x^3 + ...\$, so the output for \$N\$ is \$N+1\$.

• \$p(x) = 1 - x - x^2\$ results in the generating function of the Fibonacci sequence \$f(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...\$

• \$p(x) = 1 - x^2\$ results in the generating function of \$1,0,1,0,...\$ i.e. \$f(x) = 1 + x^2 + x^4 + x^6 + ...\$

• \$p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3\$ results in the generating function of the triangular numbers \$f(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ...\$ that means the \$N\$-th coefficient is the binomial coefficient \$\binom{N+2}{N}\$

• \$p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3\$ results in \$f(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + \dots\$

Answer 1

Mathematica, 24 23 bytes

Saved 1 byte thanks to Greg Martin

D[1/#2,{x,#}]/#!/.x->0&

Pure function with two arguments # and #2. Assumes the polynomial #2 satisfies PolynomialQ[#2,x]. Of course there's a built-in for this:

SeriesCoefficient[1/#2,{x,0,#}]&

Answer 2

Matlab, 81 79 75 bytes

Unlike the previous two answers this doesn't make use of symbolic calculations. The idea is that you can iteratively calculate the coefficients:

function C=f(p,N);s=p(end);for k=1:N;q=conv(p,s);s=[-q(end-k),s];end;C=s(1)

Try it online!

Explanation

function C=f(p,N);
s=p(end);            % get the first (constant coefficient)
for k=1:N;           
    q=conv(p,s);     % multiply the known coefficients with the polynomial
    s=[-q(end-k),s]; % determine the new coefficient to make the the product get "closer" 
end;
C=s(1)           % output the N-th coefficient

Answer 3

GeoGebra, 28 bytes

Derivative[1/A1,B1]/B1!
f(0)

Input is taken from the spreadsheet cells A1 and B1 of a polynomial and an integer respectively, and each line is entered separately into the input bar. Output is via assignment to the variable a.

Here is a gif showing the execution:

Using builtins is much longer, at 48 bytes:

First[Coefficients[TaylorPolynomial[1/A1,0,B1]]]

Answer 4

Haskell, 44 bytes

p%n=(0^n-sum[p!!i*p%(n-i)|i<-[1..n]])/head p

A direct computation without algebraic built-ins. Takes input as an infinite list of power series coefficients, like p = [1,-2,3,0,0,0,0...] (i.e. p = [1,-2,3] ++ repeat 0) for 1-2*x+x^2. Call it like p%3, which gives -4.0.

The idea is if p is a polynomial and q=1/p is it inverse, then we can express the equality p·q=1 term-by-term. The coefficient of xⁿ in p·q is given by the convolution of the coefficients in p and q:

p₀· q_n + p₁· q_n-1 + ... + p_n· q₀

For p·q=1 to hold, the above must equal zero for all n>0. For here, we can express q_n recursively in terms of q₀, ..., q_n-1 and the coefficients of p.

q_n = - 1/p₀ · (p₁· q_n-1 + ... + p_n· q₀)

This is exactly what's calculated in the expression sum[p!!i*p%(n-i)|i<-[1..n]]/head p, with head p the leading coefficient p₀. The initial coefficient q₀ = 1/p₀ is handled arithmetically in the same expression using 0^n as an indicator for n==0.

Answer 5

J, 12 bytes

1 :'(1%u)t.'

Uses the adverb t. which takes a polynomial p in the form of a verb on the LHS and a nonnegative integer k on the RHS and computes the k^th coefficient of the Taylor series of p at x = 0. In order to get the power series, the reciprocal of p is taken before applying it.

Try it online!

Answer 6

Maple, 58 26 bytes

This is an unnamed function that accepts a polynomial in x and an integer N.

EDIT: I just noticed that there is a builtin:

(p,N)->coeftayl(1/p,x=0,N)

Answer 7

MATL, 19 bytes

0)i:"1GY+@_)_8Mh]1)

Translation of @flawr's great Matlab answer.

Try it online!

How it works

0)      % Implicitly input vector of polynomial coefficients and get last entry
i       % Input N
:"      % For k in [1 2 ... N]
  1G    %   Push vector of polynomial coefficients
  Y+    %   Convolution, full size
  @     %   Push k
  _     %   Negate
  )     %   Index. This produces the end-k coefficient
  _     %   Negate
  8M    %   Push first input of the latest convolution
  h     %   Concatenate horizontally
]       % End
1)      % Get first entry. Implicitly display

Answer 8

JavaScript (ES6), 57 bytes

(a,n)=>a.reduce((s,p,i)=>!i|i>n?s:s-p*f(a,n-i),!n)/a[0]

Port of @xnor's Haskell answer. I originally tried an iterative version but it turned out to be 98 bytes, however it will be much faster for large N, as I'm effectively memoising the recursive calls:

(a,n)=>[...Array(n+1)].fill(0).map((_,i,r)=>r[i]=r.reduce((s,p,j)=>s-p*(a[i-j]||0),!i)/a[0]).pop()

n+1 terms are required, which are saved in the array r. It is initially zeros which allows reducing over the entire array r at once, as the zeros will not affect the result. The last calculated coefficient is the final result.

Answer 9

PARI/GP, 31 27 bytes

f->n->Pol(Ser(1/f,,n+1))\x^n

Answer 10

Maxima, 31 25 bytes

Saved 6 bytes thanks to the comment of @alephalpha

f(e,R):=taylor(1/e,x,0,R)

Try it online!