# Recurrences and Generating Functions in Algorithms

Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex cover set in a graph might just inspect all $\binom{n}{k}$ possible subsets. While the binomial functions grows exponentially, if $k$ is some fixed constant we end up with a polynomial time algorithm by asymptotic analysis.

Often times real-life problems require more complex combinatorial mechanisms which we may define in terms of recurrences. One famous example is the fibonacci sequence (naively) defined as:

$f(n) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n = 0 \\ f(n-1) + f(n-2) & \text{otherwise} \end{cases}$

Now computing the value of the $n$th term grows exponentially using this recurrence, but thanks to dynamic programming, we may compute it in linear time. Now, not all recurrences lend themselves to DP (off hand, the factorial function), but it is a potentially exploitable property when defining some count as a recurrence rather than a generating function.

Generating functions are an elegant way to formalize some count for a given structure. Perhaps the most famous is the binomial generating function defined as:

$(x + y)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

Luckily this has a closed form solution. Not all generating functions permit such a compact description.

Now my question is this: how often are generating functions used in design of algorithms? It is easy to see how they may be exploited to understand the rate of growth required by an algorithm via analysis, but what can they tell us about a problem when creating a method to solve some problem?

If many times the same count may be reformulated as a recurrence it may lend itself to dynamic programming, but again perhaps the same generating function has a closed form. So it is not so evenly cut.

-
"if k is some fixed constant we end up with a linear time algorithm by asymptotic analysis". I don't follow this... don't you end up with a $O(n^k)$ time algorithm if $k$ is a fixed constant? –  Artem Kaznatcheev May 18 '12 at 19:37
D'oh. For some reason I was thinking $O(2^k n) = O(n)$. You are correct though, I will edit. –  Nicholas Mancuso May 18 '12 at 19:41
I am not perfectly sure what you are getting at. Is it: "Ah, so quantity $a_n$ that comes up in my algorithm has OGF $A(z)$. By the form of $A$ is see that algorithmic technique X can be applied to compute it." Is that correct? –  Raphael May 18 '12 at 20:33
@Raphel After giving it some more thought, I realized I had conflated a few key issues. Namely applying combinatorial techniques in design of an algorithm, and its utilization in analysis of some algorithm's runtime. It appears that it these "combinatorial techniques" once fleshed out in my mind, were really just more tools of analysis. So what is left now is what you suggest. Which seems to be somewhat awkward; as I can't imagine why we would need to do that (other than laziness in analysis). I'm curious as how to salvage this question. –  Nicholas Mancuso May 18 '12 at 20:47
@NicholasMancuso: Maybe focus the question on computing combinatoric expressions? But then, the answer is (kind of) obvious, I guess. –  Raphael May 19 '12 at 10:37

Generating functions are useful when you're designing counting algorithms. That is, not only when you're looking for the number of objects having a certain property, but also when you're looking for a way to enumerate these objects (and, perhaps, generate an algorithm to count the objects). There is a very good presentation in chapter 7 of Concrete Mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik. The examples below are from these books (the mistakes and lack of clarity are mine).

Suppose that you're looking for the ways to make change with a given set of coins. For example, with common US denominations¹, the possible coins are $[1], [5], [10], [25], [100]$. To give ¢42 in change, one possibility is $[25][10][5][1][1]$; another possibility is $[10][10][10][10][1][1]$. We'll write $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$. More generally, we can write a generating function for all the ways to give change: $$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$ In more technical terms, $H$ is a term in the space of power series over the five variables $[100], [25], [10], [5], [1]$. Define the valuation of a monomial in this space by $$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$ Then the ways to give $v$ cents in change are the number of monomials whose valuation is $v$. We can express $H$ in an incremental fashion, by first writing down the ways $P$ to give change in pennies only, then the ways $N$ to give change in pennies and nickels, and so on. ($I$ means no coin.) $$\begin{gather*} P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\ N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\ D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\ Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\ H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\ \end{gather*}$$ If you want to count and not just enumerate the ways to give change, then there is a simple way to use the formal series we've obtained. Apply the homomorphism $$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100}$$ The coefficient of $X^v$ in $S(C)$ is the number of ways to give $v$ cents in change.

A harder example: suppose that you want to study all the ways to tile rectangles with 2×1 dominoes. For example, there are two ways to tile a 2×2 rectangle, either with two horizontal dominoes or with two vertical dominoes. Counting the number of ways to tile a $2 \times n$ rectangle is fairly easy, but the $3 \times n$ case quickly becomes nonobvious. We can enumerate all the possible tilings of a horizontal band of height 3 by sticking dominoes together, which quickly yields repetitive patterns: $$\begin{cases} U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\ V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\ \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\ \end{cases}$$ where the funny shapes represent elementary domino arrangements: $\mathsf{o}$ is no domino, $\mathsf{L}$ is a vertical domino on top of the left part of a horizontal domino, $\substack{\strut\\\mathsf{I}}$ is a vertical domino aligned with the bottom of the band of height 3, $\substack{\:-\\=}$ is a horizontal domino aligned with the top of the band plus two horizontal dominoes below it and one step to the right, etc. Here, multiplication represents horizontal concatenation and is not commutative, but there are equations between the elementary patterns that form variables in this power series. As before with the coins, we can substitute $X$ for every domino and get a generating series for the number of tilings of a $3 \times (2n/3)$ rectangle (i.e. the coefficient of $X^{3k}$ is the number of ways to tile a rectangle of area $6k$, which contains $3k$ dominoes and has the width $2k$). The series can also be used in more versatile ways; for example, by distinguishing vertical and horizontal dominoes, we can count the tilings with a given number of vertical and horizontal dominoes.

Again, read Concrete Mathematics for a less rushed³ presentation.

¹ I know my list is incomplete; assume a simplified US suitable for mathematical examples.²
² Also, if it comes up, assume spherical coins.
³ And better typeset.

-

While developing an algorithm for monotone submodular maximization over a matroid, we had to solve the recurrence $$\ell \gamma^{(m)}_{\ell+1} = (2\ell-m) \gamma^{(m)}_\ell + (m - \ell + 1) \gamma^{(m)}_{\ell-1}, \quad \gamma^{(m)}_0 = 1, \quad \gamma^{(m)}_{m+1} = e.$$ After noticing that $\gamma^{(m)}_\ell = m(\gamma^{(m-1)}_\ell - \gamma^{(m-1)}_{\ell-1})$, we reduced the problem to computing some universal sequence $\gamma^{(0)}$. The latter was accomplished using generating functions, and from there we got an explicit formula for $\gamma^{(m)}$, again using generating functions. You can find the solution in the paper if you're curious, though we never bothered to include this derivation.

-

Perhaps the extensive study of Quicksort, and its many variants, is the clearest example. There combinatoric considerations governed the consideration of alternatives, and analyzing the solutions to quite complex equations shows performance advantages (or not) of them.

-

ran across this other ref in the answer to another question & seems to answer your question. it particulary focuses on (advanced) generating functions wrt computer science & has sections on applications. FREE PDF DOWNLOAD

Analytic Combinatorics by Flajolet & Sedgewick, HTML TOC

-
This is pretty much a standard reference. How do you think it uses generating function in the context of design of algorithms? –  Juho Sep 22 '12 at 19:27
it answers the 2nd more general question, "what can they tell us about a problem when creating a method to solve some problem"? ie they give a precise count of the # of solutions of the problem, which tells very much about the problem. imho the original question liberally interpreted is basically asking about applications of generating functions. more details in the book. anyway NM says in comments (didnt notice those before posting answer) he didnt ask the question quite in the way he wanted but its clearly about the larger context of generating functions in CS etc. –  vzn Sep 22 '12 at 19:52
That book does contain a plethora of examples and methods [It's sitting on my shelf waiting for coursera course next semester ;)]. However, next time please discuss the material if you link to it. This style of answer is more suited for a comment. Reserve answers for properly introducing and explaining actual content. [Plus it wouldn't hurt to start using proper grammar, i.e., capitalize beginnings of sentences and not use slang]. –  Nicholas Mancuso Sep 26 '12 at 4:29
oh right! explain it better than the book! examples from the book. 1st 100 pages. generating functions are closely tied with enumerations. if it can be counted, it can lead to an enumeration strategy/algorithm. eg (1) partitions of integers, (2) # of words in a regular language, (3) set partitions, (4) trees, (5) polygons (6) graphs, etc –  vzn Sep 26 '12 at 4:55
@vzn, Whoa. I'm not asking you to explain it better than the book. But contrast your answer to Gilles, who also cites a book, but then gives a great display of generating functions' capabilities. Citing and linking is fine, just give concrete examples next time, and I will happily upvote. –  Nicholas Mancuso Sep 26 '12 at 14:09