adamant's blog

By adamant, history, 6 months ago, In English

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 months, 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 Stack 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

Since the second function in the product only depends on $$$x^2$$$ and $$$y^2$$$, we have an expression of form $$$G(x, y) = A(x, y) \cdot B(x^2, y^2)$$$.

It would make sense to do a series multisection (aka roots of unity filter) to represent it as a combination of summands that look like $$$A'(x^2, y^2) \cdot B(x^2, y^2)$$$, so that we can go back from $$$(x^2, y^2)$$$ to $$$(x, y)$$$ and analyze them as $$$A'(x, y) \cdot B(x, y)$$$. This way we detach from possible dependence on the parities of the powers of coefficients. 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 after doing so, 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} $$$


$$$ 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:


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.

Follow-up questions to interested audience
  1. Is there a sufficiently simple way to solve this problem without just "observing" some weird facts?
  2. Is there a more direct way to find the closed form on the second function? (see this question).

UPD: I found out how to compute the genfunc for $$$\binom{i+j}{i}^2$$$ directly, without using Legendre polynomials.

Consider a bivariate polynomial $$$Q_n(x, y)$$$ defined as

$$$ Q_n(x, y) = \sum\limits_{k=0}^n \binom{n}{k}^2 x^k y^{n-k} = [t^n] (x+t)^n (y+t)^n. $$$

We need to sum it up over all $$$n$$$, and we know from Legendre polynomials that $$$Q_n(x) = (y-x)^n P_n(\frac{y+x}{y-x})$$$.

But let's analyze $$$Q_n(x, y)$$$ on its own:

$$$ [t^n](x+t)^n (y+t)^n = [t^n](t(t+x+y)+xy)^n. $$$

This expands into

$$$ \sum\limits_k \binom{n}{k} x^k y^k [t^k] (t+x+y)^{n-k} = \sum\limits_k \binom{n}{k} \binom{n-k}{k} x^k y^k (x+y)^{n-2k}. $$$

Note that

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

hence we want to compute the sum

$$$ \sum\limits_{n, k} \binom{n}{2k} \binom{2k}{k} x^k y^k (x+y)^{n-2k}. $$$

Let's sum up over $$$n$$$ for each fixed $$$k$$$:

$$$ \sum\limits_{n} \binom{n}{2k} (x+y)^{n-2k} = \sum\limits_{t} \binom{2k+t}{2k} (x+y)^{t} = \frac{1}{(1-x-y)^{2k+1}}. $$$

Thus, we want to compute

$$$ \sum\limits_k \binom{2k}{k} \frac{x^k y^k}{(1-x-y)^{2k+1}}. $$$

On the other hand we know that

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

thus the sum above compacts into

$$$ \frac{1}{1-x-y} \frac{1}{\sqrt{1-4\frac{xy}{(1-x-y)^2}}}= \boxed{\frac{1}{\sqrt{(1-x-y)^2-4xy}}} $$$

which then expands into the same expression in the denominator.

  • Vote: I like it
  • +205
  • Vote: I do not like it

6 months ago, # |
  Vote: I like it +288 Vote: I do not like it


6 months ago, # |
  Vote: I like it +125 Vote: I do not like it

Great blog as usual (no sarcasm)

6 months ago, # |
  Vote: I like it +10 Vote: I do not like it


6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

I understood only the formula at the very end

6 months ago, # |
Rev. 3   Vote: I like it -23 Vote: I do not like it

did you try asking our polynomial god Karry5307

He can solve all polynomial problems that exist in this world, assuming there is an editor here.

6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What the fuck is even that?

6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

And I thought I was good at maths.