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 :

enter image description here

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

  • 1
    $\begingroup$ 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. $\endgroup$ – Semiclassical Mar 9 '16 at 15:14
  • $\begingroup$ 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. $\endgroup$ – Semiclassical Mar 9 '16 at 17:16
  • $\begingroup$ @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 . $\endgroup$ – user217174 Mar 9 '16 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.