Useful substitutions with generating functions

Правка en5, от adamant, 2023-06-13 02:52:43

Hi everyone!

Today I would like to write about some identities that might come handy when using generating functions to solve competitive programming problems. I will also try to include some useful examples about them.

Some notation

For brevity, we will sometimes skip the specific bounds in indexed sums, meaning that the summation happens among all valid indices. Please also read the information below if you're not familiar with generating functions, or want to brush up on some aspects.

Definitions and notation

Multinomial coefficients

If you're not familiar with them, multinomial coefficients are defined as

$$$ \large \binom{n}{a_1, \dots, a_r} = \frac{n!}{a_1! \dots a_r!}, $$$

where $$$a_1+\dots+a_r=n$$$. When dealing with identities that contain binomial coefficients, we often can combine them and "reshuffle" into another combination of binomial coefficients which is more convenient to us. This is because multinomial coefficients can be expanded as

$$$ \boxed{\binom{n}{a_1,\dots,a_n} = \binom{n}{a_1} \binom{n-a_1}{a_2} \binom{n-a_1-a_2}{a_3} \dots \binom{a_{r-1}+a_r}{a_{r-1}} = \binom{a_1+a_2}{a_2} \binom{a_1+a_2+a_3}{a_3} \dots \binom{n}{a_r}} $$$

In other words, we can represent any multinomial coefficient as a chain of binomial coefficients which account for each $$$a_i$$$ one piece at a time. We will see a lot of examples of this below, mostly with trinomial coefficients and for now we can look on the following one:

$$$ \binom{n}{k} \binom{n-k}{k} = \binom{n}{k,k,n-2k} = \binom{n}{2k} \binom{2k}{k}, $$$

which allows to fully exclude $$$n$$$ from one of the coefficients which will then simplify our work with the part that is related to $$$n$$$.

Binomial theorem

Let's start with the simplest substitution ever. We most likely know the binomial theorem:

$$$ \boxed{(x+y)^n = \sum\limits_k \binom{n}{k} x^k y^{n-k}} $$$

This allows us, whenever we have a binomial coefficient in our expression, to substitute it with

$$$ \boxed{\binom{n}{k} = [x^k] (1+x)^n = [x^{n-k}] (1+x)^n = [x^n] x^k (1+x)^n} $$$

The last identity is especially useful, as it allows to drag $$$[x^n]$$$ outside of the summation.

Example 1. Consider the sum from one of Elegia's blog posts:

$$$ \sum\limits_{k} \binom{n}{k}^2 \binom{3n+k}{2n}. $$$

Assume that you're given several values of $$$n$$$ and you need to compute it in $$$O(1)$$$ with $$$O(n)$$$ pre-processing.

Solution

Exercise 1: Solve ProjectEuler 831 — Triple Product.

Negative binomial expansion

Now, let's learn few more well-known expansions. You most likely know that

$$$ \frac{1}{1-x} = 1+x+x^2+\dots $$$

This expression is also the consequence of the binomial expansion, as it also allows to use values of $$$n$$$ that are not positive integer. So, being more general, we can write that

$$$ (1-x)^{-n} = \sum\limits_{k} \binom{-n}{k} (-1)^k x^k, $$$

but at the same time the binomial coefficient rewrites as

$$$ \binom{-n}{k} = \frac{(-n)(-n-1)\dots(-n-(k-1))}{k!} = (-1)^k \binom{n+k-1}{k}. $$$

The result above allows us to rewrite

$$$ \boxed{\frac{1}{(1-x)^{k+1}} = \sum\limits_t \binom{t+k}{k} x^t} $$$

This, in turn, means that while $$$\binom{n}{k}$$$ is often substituted with $$$[x^k]{}(1+x)^n$$$, there is another useful substitution:

$$$ \boxed{\binom{a+b}{a} = [x^a] \frac{1}{(1-x)^{b+1}} = [x^b] \frac{1}{(1-x)^{a+1}}} $$$

To differentiate between the two, the substitution $$$\binom{n}{k}=[x^k]{}(1+x)^n$$$ is typically more useful when $$$n$$$ is constant and summation goes over $$$k$$$. Conversely, when $$$k$$$ is constant and summation goes over $$$n$$$, it would likely be more convenient to use the substitution above.

Inverse square root expansion

Another important case of binomial expansion is when $$$n=-\frac{1}{2}$$$. Consider the expansion

$$$ \frac{1}{\sqrt{1-x}} = \sum\limits_{k} \binom{-1/2}{k} (-x)^k. $$$

We can rewrite the fractional binomial as

$$$ \binom{-1/2}{k} = \frac{(-1/2)(-1/2-1)\dots(-1/2-k+1)}{k!} = \frac{(-1)^k}{2^k} \frac{1\cdot3\cdot5\cdot\ldots\cdot(2k-1)}{k!} = \frac{(-1)^k}{2^k}\frac{(2k-1)!!}{k!}, $$$

where $$$k!! = k(k-2)(k-4)\dots$$$ is the double factorial of $$$k$$$. Note that $$$(2k)!! (2k-1)!! = (2k)!$$$ and that $$$(2k)!! = 2^k k!$$$.

Thus, multiplying the numerator and denominator with $$$2^k k!$$$, we get

$$$ =\frac{(-1)^k}{4^k} \frac{(2k)!}{k!^2} = \frac{(-1)^k}{4^k} \binom{2k}{k}, $$$

which means that

$$$ \boxed{\frac{1}{\sqrt{1-x}} = \sum\limits_k \frac{x^k}{4^k} \binom{2k}{k}} $$$

This identity allows to collapse some more complicated sums that involve $$$\binom{2k}{k}$$$, as it means that

$$$ \boxed{\binom{2k}{k} = [x^k] \frac{1}{\sqrt{1-4x}}} $$$

Example 2. The problem 446227I — O Andar do Trêbado reduces to computing

$$$ [x^n](1+x+x^2)^n. $$$

It's well known that this is doable in $$$O(n)$$$. But in this problem we need to do it for all $$$n$$$ up to some limit.

Solution

Note that the linked problem also allowed $$$O(n^2)$$$ solutions. Thanks to tfg for telling me about the problem!

Example 3. The function $$$f(n,m)$$$ defined below can be computed in $$$O(1)$$$ with $$$O(n+m)$$$ pre-computation:

$$$ f(n, m) = \sum\limits_{i,j} \binom{i+j}{i}^2 \binom{n+m-2i-2j}{n-2j}. $$$
Solution

Example 4. Find the closed form of a function

$$$ G(x, y) = \sum\limits_{i,j} \binom{i+j}{i}^2 x^i y^j. $$$
Solution

Example 5. Find the closed form of a function

$$$ G(t, x) = \sum\limits_n t^n P_n(x), $$$

where $$$P_n(x)$$$ is the sequence of Legendre polynomials, defined for this example as

$$$ P_n(x) = \frac{1}{2^n}\sum\limits_k \binom{n}{k}^2 (x-1)^k (x+1)^{n-k}. $$$
Solution

Note: Although examples 4 and 5 don't look useful for competitive programming, they can be used to solve the example 3, which is based on a real problem from some training camp (and also some prior publications, apparently).

Powers of $$$n$$$

Another less known, but quite useful substitution involves the exponential function:

$$$ e^{nx} = \sum\limits_k \frac{n^k x^k}{k!}, $$$

from which it follows that we can use the substitution

$$$ \boxed{n^k = \left[\frac{x^k}{k!}\right] e^{nx}} $$$

Let's see how it can be used to solve some problems.

Example 6. Given $$$m$$$, we want to compute $$$f(k)$$$ in $$$O(1)$$$ per $$$k$$$ with $$$O(k \log k)$$$ pre-computation:

$$$ f(k)=\sum\limits_{n=0}^{m-1} n^k. $$$

Solution: Using the substitution above, we turn the sum into the geometric progression:

$$$ f(k) = \left[\frac{x^k}{k!}\right]\sum\limits_{n=0}^{m-1} e^{nx} = \left[\frac{x^k}{k!}\right] \frac{1-e^{mx}}{1-e^x}. $$$

Well, not exactly new, as I already wrote a blog about it quite some time ago...

Example 7. Given $$$A(x) = a_0 + a_1 x + \dots$$$, we want to quickly compute $$$f(k)$$$ defined as

$$$ f(k) = \sum\limits_{n} a_n n^k. $$$

Solution: Using the same substitution, we get

$$$ f(k) = \left[\frac{x^k}{k!}\right] \sum\limits_n a_n e^{nx} = \left[\frac{x^k}{k!}\right] A(e^x). $$$

Well, still not new, as I had another blog about it some time ago.

At the same time, the result above assumes that we're able to compute series expansion of $$$A(e^x)$$$ up to $$$k$$$ sufficiently quickly. Which might turn out to be quite problematic if $$$A(x)$$$ is sufficiently arbitrary. However, when $$$A(x)$$$ is sufficiently nice, there is an interesting side effect of such solution. It allows $$$A(x)$$$ to have quite a large amount of terms if it still can be represented in a "nice" way.

For this, we rely on the following statement:

Conjecture: Let $$$F(x)$$$, $$$G(x)$$$ and $$$H(x)$$$ be formal power series, and let $$$G_0 = [x^0] G(x)$$$. Then the following implication stands:

$$$ \boxed{F(x) \equiv H(x) \pmod{(x-G_0)^k} \implies F(G(x)) \equiv H(G(x)) \pmod{x^k}} $$$

In particular, as $$$[x^0] e^x = 1$$$, it means that

$$$ \boxed{F(x) \equiv H(x) \pmod{(x-1)^k} \implies F(e^x) \equiv H(e^x) \pmod{x^k}} $$$
Proof

From the result above it follows that to find first $$$k$$$ elements of $$$F(e^x)$$$, we can instead find $$$H(x)$$$ such that

$$$ F(x) \equiv H(x) \pmod{(x-1)^k}, $$$

and compute first $$$k$$$ elements of $$$H(e^x)$$$ instead. This allows to efficiently solve the following problem:

Example 8. 392C - Yet Another Number Sequence. Let $$$f_n=f_{n-1} + f_{n-2}$$$. Given $$$m$$$ and $$$k$$$, compute $$$f(k)$$$ in $$$O(k \log k)$$$:

$$$ f(k) = \sum\limits_{n=0}^{m-1} f_n n^k. $$$
Solution

Note: Apparently, this problem is also a subject of one of Elegia's blogs, but it is difficult for me to translate on my own...

Exercise 2. Find a way to solve example 8 in $$$O(k)$$$.

Exercise 3. Solve Library Judge — Sum of Exponential times Polynomial. The problem asks to, given $$$r$$$, $$$d$$$ and $$$n$$$, compute

$$$ \sum\limits_{i=0}^{n-1} r^i i^d. $$$

Exercise 4. Solve Library Judge — Sum of Exponential times Polynomial Limit. The problem asks to, given $$$r$$$ and $$$d$$$, compute

$$$ \sum\limits_{i=0}^{\infty} r^i i^d. $$$

It seems that they're also solvable with this technique (except for $$$r=1$$$ which should be accounted for separately due to degeneracy).

Теги generating function, tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский adamant 2023-06-13 23:53:53 210
en8 Английский adamant 2023-06-13 17:12:41 2028
en7 Английский adamant 2023-06-13 03:01:43 122
en6 Английский adamant 2023-06-13 02:59:03 367
en5 Английский adamant 2023-06-13 02:52:43 62
en4 Английский adamant 2023-06-13 02:38:38 170
en3 Английский adamant 2023-06-13 02:10:48 313
en2 Английский adamant 2023-06-13 02:09:30 150
en1 Английский adamant 2023-06-13 01:57:41 17285 Initial revision (published)