This post extends the generating-function technique from the two-variable recursion to a three-variable case. I originally wrote this as an answer to a Math Stack Exchange question; here it is adapted for the blog with clearer exposition and code.
We want to solve the recurrence
$a_{n,m,k} = 2a_{n-1,m-1,k-1} + a_{n-1,m-1,k}$ $ + a_{n,m-1,k-1} + a_{n-1,m,k-1}$
where $m$, $n$, $k$ are nonnegative integers, with boundary conditions:
A subtlety: $a_{1,0,1}$ is not defined by the recurrence alone, since it would require values like $a_{0,-1,0}$. We take $a_{n,m,k} = 0$ whenever any subscript is negative.
In the previous post, we implemented the closed form $F_{n,m} = \binom{n-m+1}{m}$ using Python’s math.factorial, and with scipy and sympy. Here we cover the common competitive-programming case: computing the answer modulo a large prime $M$ (e.g. $M = 10^9+7$).
In counting problems, the result can be huge even for moderate input. Often the problem asks for the answer modulo a big prime so that it fits in a standard integer type. We could compute the full number and then take the remainder, but that forces expensive long-integer arithmetic. Computing everything modulo $M$ from the start is much faster.
In the previous post, we derived the closed form for the non-adjacent selection problem:
$$ F_{n, m} = {n - m + 1 \choose m} $$
Now we discuss how to implement this efficiently in Python—from a simple factorial-based solution to library implementations. For the common case of computing the answer modulo a large prime (e.g. in competitive programming), see the next post.
We can reflect the closed form in very trivial Python code:
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.
Compute the number of ways to choose $m$ elements from $n$ elements such that selected elements in one combination are not adjacent.
The notion of generating functions and its application to solving recursive equations are very well-known. For reader who did not have a chance to get familiar with the topics, I recommend to take a look at very good book: Concrete Mathematics: A Foundation for Computer Science, by Ronald L. Graham, Donald E. Knuth, Oren Patashnik.
Generating functions are usually applied to single variable recursive equations. But actually, the technique may be extended to multivariate recursive equations, or even to a system of recursive equations. Readers who are familiar with one-variable case, may jump directly to the next post: Cracking Multivariate Recursive Equations Using Generating Functions.
In the post, we discuss the basics of Recursion, Dynamic Programming (DP), and Memoization. As an example, we take a combinatorial problem, which has very short and clear description. This allows us to focus on DP and memoization. Note that the topics are very popular in coding interviews. Hopefully, this article will help to somebody to prepare for such types of questions.
In the next posts, we consider more advanced topics, like The Art of Generating Functions and Cracking Multivariate Recursive Equations Using Generating Functions. The methods can be applied to the same combinatorial question. Let’s start from presenting the problem.