# Calculate Power Series Coefficients

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\$$

• Would it be acceptable to take a polynomial as an infinite list of power-series coefficients like [1,-1,0,0,0,0,...]? – xnor Jan 1 '17 at 21:48
• Yes, I think that this is an acceptable format. – flawr Jan 1 '17 at 21:54
• Nice examples chosen! – Greg Martin Jan 1 '17 at 22:02
• I'm glad you appreciate it, thank you=) – flawr Jan 2 '17 at 12:38

## 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,#}]&

• Well done beating the built-in! I guess you can save a byte by assuming that # is the integer N and #2 is the polynomial. – Greg Martin Jan 1 '17 at 22:04

# 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


# 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]]]


## 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 xn in p·q is given by the convolution of the coefficients in p and q:

p0· qn + p1· qn-1 + ... + pn· q0

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

qn = - 1/p0 · (p1· qn-1 + ... + pn· q0)

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 p0. The initial coefficient q0 = 1/p0 is handled arithmetically in the same expression using 0^n as an indicator for n==0.

# 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 kth 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!

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


# 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


## JavaScript (ES6), 57 bytes

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


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).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.

# PARI/GP, 31 27 bytes

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