Calculer les coefficients de la série de puissance

24

Étant donné un polynôme p(x)avec des coefficients intégraux et un terme constant de p(0) = 1 or -1, et un entier non négatif N, renvoyer le N-ième coefficient de la série de puissance (parfois appelée "série Taylor") de f(x) = 1/p(x)développé à x0 = 0, c'est- à -dire le coefficient du monôme de degré N.

Les conditions données garantissent que la série de puissances existe et que ses coefficients sont des entiers.

Détails

Comme toujours, le polynôme peut être accepté dans n'importe quel format convenable, par exemple une liste de coefficients, par exemple p(x) = x^3-2x+5pourrait être représentée comme [1,0,-2,5].

La puissance d'une fonction fdéveloppée à 0est donnée par

et le N-ème coefficient (le coefficient de x^N) est donné par

dénote la ndérivée -ième def

Exemples

  • Le polynôme se p(x) = 1-xtraduit par la série géométrique f(x) = 1 + x + x^2 + ..., la sortie doit donc être 1pour tous N.

  • p(x) = (1-x)^2 = x^2 - 2x + 1entraîne la dérivée de la série géométrique f(x) = 1 + 2x + 3x^2 + 4x^3 + ..., donc la sortie pour Nest N+1.

  • p(x) = 1 - x - x^2 entraîne la fonction génératrice de la séquence de Fibonacci f(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...

  • p(x) = 1 - x^2se traduit par la fonction génératrice de 1,0,1,0,...ief(x) = 1 + x^2 + x^4 + x^6 + ...

  • p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3entraîne la fonction génératrice des nombres triangulaires, ce f(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ...qui signifie que le N-ème coefficient est le coefficient binomial(N+2, N)

  • p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3 résulte en f(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + ...

flawr
la source
Serait-il acceptable de prendre un polynôme comme une liste infinie de coefficients de série de puissance comme [1,-1,0,0,0,0,...]?
xnor
Oui, je pense que c'est un format acceptable.
flawr
Bons exemples choisis!
Greg Martin
Je suis content que vous l'appréciez, merci =)
flawr

Réponses:

9

Mathematica, 24 23 octets

1 octet enregistré grâce à Greg Martin

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

Fonction pure avec deux arguments #et #2. Suppose que le polynôme #2satisfait PolynomialQ[#2,x]. Bien sûr, il y a une fonction intégrée pour cela:

SeriesCoefficient[1/#2,{x,0,#}]&
ngenisis
la source
1
Bravo de battre le intégré! Je suppose que vous pouvez enregistrer un octet en supposant qu'il #s'agit de l'entier Net #2du polynôme.
Greg Martin
6

Matlab, 81 79 75 octets

Contrairement aux deux réponses précédentes, cela n'utilise pas de calculs symboliques. L'idée est que vous pouvez calculer itérativement les 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)

Essayez-le en ligne!

Explication

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
flawr
la source
4

GeoGebra , 28 octets

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

L'entrée est tirée des cellules de feuille de calcul A1 et B1 d'un polynôme et d'un entier respectivement, et chaque ligne est entrée séparément dans la barre d'entrée. La sortie se fait par affectation à la variable a.

Voici un gif montrant l'exécution:

Coefficients de Taylor

L'utilisation de builtins est beaucoup plus longue, à 48 octets:

First[Coefficients[TaylorPolynomial[1/A1,0,B1]]]
TheBikingViking
la source
4

Haskell, 44 octets

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

Un calcul direct sans intégration algébrique. Prend l'entrée comme une liste infinie de coefficients de série de puissance, comme p = [1,-2,3,0,0,0,0...](ie p = [1,-2,3] ++ repeat 0) pour 1-2*x+x^2. Appelez ça comme p%3, ce qui donne -4.0.

L'idée est que si p est un polynôme et q = 1 / p est-il inverse, alors nous pouvons exprimer l'égalité p · q = 1 terme par terme. Le coefficient de x n dans p · q est donné par la convolution des coefficients dans p et q :

p 0 · q n + p 1 · q n-1 + ... + p n · q 0

Pour que p · q = 1 soit maintenu, ce qui précède doit être égal à zéro pour tout n> 0 . Car ici, on peut exprimer q n récursivement en termes de q 0 , ..., q n-1 et les coefficients de p .

q n = - 1 / p 0 · (p 1 · q n-1 + ... + p n · q 0 )

C'est exactement ce qui est calculé dans l'expression sum[p!!i*p%(n-i)|i<-[1..n]]/head p, avec head ple coefficient dominant p 0 . Le coefficient initial q 0 = 1 / p 0 est traité arithmétiquement dans la même expression en utilisant 0^ncomme indicateur pour n==0.

xnor
la source
3

J, 12 octets

1 :'(1%u)t.'

Utilise l'adverbe t.qui prend un polynôme psous la forme d'un verbe sur le LHS et un entier non négatif ksur le RHS et calcule le ke coefficient de la série de Taylor de pat x = 0. Afin d'obtenir la série de puissance, l'inverse de pest pris avant de l'appliquer.

Essayez-le en ligne!

miles
la source
2

Érable, 58 26 octets

Il s'agit d'une fonction sans nom qui accepte un polynôme xet un entier N.

EDIT: Je viens de remarquer qu'il y a une fonction intégrée:

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

MATL , 19 octets

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

Traduction de la grande réponse Matlab de @ flawr .

Essayez-le en ligne!

Comment ça marche

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
Luis Mendo
la source
1

JavaScript (ES6), 57 octets

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

Réponse de Haskell de @ xnor. À l'origine, j'ai essayé une version itérative, mais elle s'est avérée être de 98 octets, mais elle sera beaucoup plus rapide pour les grands N, car je mémorise efficacement les appels récursifs:

(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+1des termes sont requis, qui sont enregistrés dans le tableau r. Il s'agit initialement de zéros qui permettent de réduire simultanément l'ensemble du tableau r, car les zéros n'affecteront pas le résultat. Le dernier coefficient calculé est le résultat final.

Neil
la source
1

PARI / GP, 31 27 octets

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