Multivariate Function

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.

The Problem

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_{0,0,0} = a_{0,1,0} = a_{1,0,0} = a_{0,0,1} = 1$
• $a_{n,0,0} = a_{0,n,0} = a_{0,0,n} = 0$ for any $n > 1$
• $a_{n,m,k}$ is symmetric in $n$, $m$, $k$

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

The Problem

Compute the number of ways to choose $m$ elements from $n$ elements such that selected elements in one combination are not adjacent.