Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

How to get recurrence formula of an array by it's generating function

Revision en1, by jianglyFans, 2020-07-24 14:13:19

zscoder introduced Generating functions in Competitive Programming in his blog, which give a method to get the formula of general term by it's generating function.

But sometime the generating function is somewhat complicated, for instance, the array http://oeis.org/A054726 which has generating function:

$$$ \frac{2 + 3 z - z^2 - z \sqrt{1 - 12 z + 4 z^2}{2} $$$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English jianglyFans 2020-07-25 06:37:06 42
en3 English jianglyFans 2020-07-25 06:24:18 1362
en2 English jianglyFans 2020-07-24 14:57:03 385 Tiny change: 'ction:\n\n3232\n\frac{3}{2}\n\n\n\n' -> 'ction:\n\n$$\n\frac{3}{2}\n$$\n\n\n' (published)
en1 English jianglyFans 2020-07-24 14:13:19 504 Initial revision (saved to drafts)