# Does the functional equation $p(x^2)=p(x)p(x+1)$ have a combinatorial interpretation?

A recent question asked about polynomial solutions to the functional equation $p(x^2)=p(x)p(x+1)$. Subsequently, Robert Israel posted an answer showing that solutions are necessarily of the form $p(x)=x^m(x-1)^m$.

What I had hoped to do myself was provide a solution by interpreting $p(x)$ as a generating function, with the functional equation leading to some kind of counting argument for the form of $p(x)$. Robert's answer complicates this, however, because $x^m(x-1)^m$ has coefficients of alternating signs. I then thought to route around this by replacing $x\to-x$ in the functional equation. But, while $p(-x)$ has positive coefficients, $p(-x+1)$ does not and so runs into the same issue.

That's as far as my thinking lead me. My question is: Is there some way to understand $p(x)$ (or some transformation of it) so as to provide a useful combinatorial interpretation of the functional equation?

Assume $q(n)$ is the number of ways to coloring two squares of ordered $n$ squares by blue and red .

Theorem : Number of coloring of two $1\times 1$ squares in $n\times n$ square by blue and red , is $q(n+1)q(n)$ .

Proof : There is one-to-one correspondence between coloring of two $1\times 1$ squares in $n\times n$ square, and coloring of two $1\times 1$ squares in $n\times (n+1)$ square with the condition that two colored square is not in the same row or same column.
Here is the sketch of this correspondence :

1. If two colored squares in $n\times n$ square aren't in the same row or column then we correspond those to the same squares .

2. If they are in the same column , then we put the blue square in the same square , and move red square to the $n+1$th column and same row .

3. If they are in the same row , put $i=$ blue column . Now we put the red square in the same square , and move blue square to the $n+1$th column in the $i$th or $i+1$th row , depending on $i<$ red row or $i\geq$ red row (like above example) .

It's easy to check that this is an one-to-one correspondence .

Now the number of coloring $n\times (n+1)$ squares with mentioned condition , is $q(n+1)q(n)$ because we have $q(n+1)$ ordered choice of columns , and $q(n)$ ordered choice of rows . $\Box$

Thus $q(n^2)=q(n+1)q(n)$ .

If we have $m$ numbers of $n\times n$ squares , and we want to color two squares of each of them with blue and red , and $p(n)$ be the number of ways to do that , then by above conclusion we can conclude : $$p(n^2) = p(n+1)p(n)$$
and by combinatorics we know : $$p(n)=(n(n-1))^m$$

• Thanks for this answer! For the same row case, it seems like it'd be simpler to imitate the same column case: Add a row at the bottom, move the blue square to the the bottom of its column, then reflect the entire $(n+1)\times n$ rectangle along its diagonal to get the right shape. – Semiclassical Mar 9 '16 at 15:14
• I should also point out that this isn't quite the kind of answer I expected. My thought had been to find a combinatorial meaning for the coefficients of $p(x)$, rather than $p(n)$ itself. But I think your way of looking at it is quite satisfying. – Semiclassical Mar 9 '16 at 17:16
• @Semiclassical For your way for same rows, yes, at first I decided to say this , but at last I gave up! For coefficients of $p(x)$ , I will think about this . – user217174 Mar 9 '16 at 19:59