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?
Solution 1:
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 :
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 .
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 .
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$$