combinarotics

Cracking Multivariate Recursive Equations Using Generating Functions

In this post, we return back to the combinatorial problem discussed in Introduction to Dynamic Programming and Memoization post. We will show that generating functions may work great not only for single variable case (see The Art of Generating Functions), but also could be very useful for hacking two-variable relations (and of course, in general for multivariate case too). For making the post self-contained, we repeat the problem definition here.