Solving the "simple math problem" with generating functions

Правка en1, от adamant, 2023-06-11 18:30:19

Hi everyone!

Some time ago the following "simple math problem" was shared in a Discord chat:

As a lover of simple math problems, I couldn't just pass by this problem. It turned out much harder than any other genfunc problem that I solved before, as the structure of the answer depends on the parity of $$$n$$$ and $$$m$$$, and it's not very natural to track it through genfuncs. It took me few month, I even called for help from higher powers (i.e. sent a pm to Elegia) but I finally have a solution that I somewhat like.


Finding a closed-form genfunc

First of all, it's really inconvenient to sum up from $$$0$$$ to $$$\lfloor m/2 \rfloor$$$ or $$$\lfloor n/2 \rfloor$$$. What we can do is to introduce variables $$$a=n-2j$$$ and $$$b=m-2i$$$, after which the expression under the sum changes to

$$$ \binom{i+j}{j}^2 \binom{a+b}{a}. $$$

As we want to sum it up over all $$$i,j,a,b$$$ such that $$$a + 2j = n$$$ and $$$b + 2i = m$$$, we can keep track of these equations with two formal variables $$$x$$$ and $$$y$$$. Then, the sum that we're interested in expresses as

$$$ [x^n y^m] \sum\limits_{i,j,a,b} \binom{i+j}{i}^2 \binom{a+b}{a} x^{2j+a} y^{2i+b} = [x^n y^m]\left(\sum\limits_{a, b} \binom{a+b}{a} x^a y^b\right) \left(\sum\limits_{i,j} \binom{i+j}{i}^2 x^{2j} y^{2i}\right). $$$

This is the product of two generating functions. The first one is standard and collapses with $$$s=a+b$$$ substitution:

$$$ \sum\limits_{a, b} \binom{a+b}{a} x^a y^b = \sum\limits_s (x+y)^s = \frac{1}{1-x-y}. $$$

The second generating function is trickier, and collapses into

$$$ \sum\limits_{i,j} \binom{i+j}{i}^2 x^{2j} y^{2i} = \frac{1}{\sqrt{1-2(y^2+x^2)+(y^2-x^2)^2}}. $$$

Unfortunately, I don't have a simple explanation to it, as it is obtained via reduction to a well-known bivariate generating function for Legendre polynomials (see this Mathematics Stach Exchange question for details). So, the problem reduces to finding

$$$ \boxed{ [x^n y^m] \frac{1}{1-x-y}\frac{1}{\sqrt{1-2(y^2+x^2)+(y^2-x^2)^2}}} $$$

Adding series multisection

As I mentioned earlier, since the second function in the product only depends on $$$x^2$$$ and $$$y^2$$$, it would make sense to do a series multisection (aka roots of unity filter) to the first function to go back to $$$x$$$ and $$$y$$$ instead of $$$x^2$$$ and $$$y^2$$$. The multisection is generally done as

$$$ A(x) = \frac{A(x)+A(-x)}{2} + \frac{A(x)-A(-x)}{2}, $$$

where the first summand only has even powers of $$$x$$$, and the second summand only has odd powers of $$$x$$$. In our case, we need to apply it first to the variable $$$x$$$, and the to $$$y$$$. However, we can do a little shortcut, as we know that the common denominator of the resulting expression should be

$$$ (1-x-y)(1+x-y)(1-x+y)(1+x+y), $$$

meaning that the numerator must be

$$$ (1+x-y)(1-x+y)(1+x+y), $$$

which expands to

$$$ \boxed{\frac{1}{1-x-y} = \frac{[1-x^2-y^2] + [x-x^3+xy^2] + [y+x^2y-y^3] + [2xy]}{(1-x-y)(1+x-y)(1-x+y)(1+x+y)}} $$$

Solving for parities

The $$$4$$$ distinct summands in the numerator correspond to all possible combinations of parities of powers of $$$x$$$ and $$$y$$$. But what is really striking here is that the denominator expands to

$$$ (1-x-y)(1+x-y)(1-x+y)(1+x+y) = 1-2(y^2+x^2)+(y^2-x^2)^2, $$$

meaning that it is exactly the expression under the square root of the second function multiplier. Therefore, the full problem reduces to finding (and computing an appropriate linear combination of) $$$[x^n y^m]$$$ of the function

$$$ F(x, y) = [1-2(y+x)+(y-x)^2]^{-3/2}. $$$

This function is very similar to

$$$ G(x, y) = [1-2(y+x)+(y-x)^2]^{-1/2}, $$$

about which we already know that $$$[x^n y^m] G(x, y) = \binom{n+m}{n}^2$$$. Indeed, we can notice that

$$$ \begin{cases} \frac{\partial}{\partial x} G(x, y) = (1-x+y) F(x, y), \\ \frac{\partial}{\partial y} G(x, y) = (1+x-y) F(x, y), \end{cases} $$$

therefore

$$$ F(x, y) = \frac{1}{2}\left[\frac{\partial}{\partial x} G(x, y) + \frac{\partial}{\partial y} G(x, y)\right], $$$

from which it follows that

$$$ \boxed{[x^n y^m] F(x, y) = \frac{1}{2}\left[(n+1)\binom{n+m+1}{n+1}^2 + (m+1)\binom{n+m+1}{m+1}^2\right]} $$$

This allows to solve the problem in $$$O(1)$$$ per $$$(n, m)$$$ pair with $$$O(n+m)$$$ pre-computation:

code

Alternative approaches

The answer to the whole problem can be further simplified as

$$$ \boxed{f(n, m) = \left\lfloor(n+m)/2+1 \right\rfloor \binom{\lfloor n/2 \rfloor + \lceil m/2 \rceil}{\lfloor n/2 \rfloor} \binom{\lfloor m/2 \rfloor + \lceil n/2 \rceil}{\lfloor m/2 \rfloor}} $$$

Thanks to Endagorion for telling me about this form! One can prove it by inspecting how $$$f(n, m)$$$ relates to $$$f(n-1,m)$$$ and $$$f(n,m-1)$$$, but apparently there is also a bijective proof. You may also refer to this publication for further details and alternative proofs.

Теги generating function, simple math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский adamant 2023-06-14 23:51:41 19
en7 Английский adamant 2023-06-14 23:50:35 350
en6 Английский adamant 2023-06-12 18:16:02 1
en5 Английский adamant 2023-06-12 18:14:41 1438
en4 Английский adamant 2023-06-12 01:34:03 1
en3 Английский adamant 2023-06-11 19:33:08 2
en2 Английский adamant 2023-06-11 18:32:19 374
en1 Английский adamant 2023-06-11 18:30:19 5605 Initial revision (published)