Can someone please post some (relatively easy, high school level) combinatorial problems which can be solved with polynomials (but not generating functions).

Here is an example of one such problem:

We have $2n$ different numbers $a_1,\dotsc,a_n, b_1,\dotsc,b_n$. A table $n\times n$ is divided on $n^2$ unit cells and in cell $(i,j)$ we write a number $a_i+b_j$. Suppose that all products of numbers written in cells in each column are the same. Prove that then all products of numbers written in cells in each row are the same.

Idea for a solution: Observe a polynomial $$P(x) = (x+a_1)\dotsb(x+a_n)-(x-b_1)\dotsb(x-b_n)$$


1 Answer 1


An interesting example is Sicherman dice: A pair of 6-sided dice, with positive number of eyes on each face that are not the classic 1..6 ones; if you throw them, the distribution of total eyes is the same as for two regular dice.

To construct them, one die is represented by:

$\begin{align*} D(z) &= z + z^2 + z^3 + z^4 + z^5 + z^6 \\ &= z (1 + z) (1 - z + z^2) (1 + z + z^2) \end{align*}$

Throwing two dice gives the distribution:

$\begin{equation*} D^2(z) = z^2 (1 + z)^2 (1 - z + z^2)^2 (1 + z + z^2)^2 \end{equation*}$

So we want two dice, call them $D_1(z)$ and $D_2(z)$, such that $D^2(z) = D_1(z) \cdot D_2(z)$. The respective polynomials have to satisfy several conditions:

  • We want that all faces have some eyes, i.e., the constant term of the polynomial has to be zero. We need to assign a $z$ factor to each.
  • The coefficients have to be integers (number of faces with each number of eyes). It is a fun fact that if a polynomial with integer coefficients factors, the primitive factors have integer coefficients (from Gauss' lemma). So this isn't a restriction.
  • The number of faces of the dice has to be six. This is the sum of the coefficients in the polynomial, which is just $D_i(1)$. The respective factors at $z = 1$ are $1$, $2$, $1$ and $3$. We have to give a $1 + z$ and a $1 + z + z^2$ to each, we can shuffle the $1 - z + z^2$ factors around.

Thus the only solution (except for switching the dice, and classical dice) is:

$\begin{align*} D_1(z) &= z (1 + z) (1 + z + z^2) \\ &= z + 2 z^2 + 2 z^3 + z^4 \\ D_2(z) &= z (1 + z) (1 + z + z^2) (1 - z + z^2)^2 \\ &= z + z^3 + z^4 + z^5 + z^6 + z^8 \end{align*}$

This translates into dice with faces marked $\{1, 2, 2, 3, 3, 4\}$ and $\{1, 3, 4, 5, 6, 8\}$.

  • 1
    $\begingroup$ (this is neat, my above comment is not a comment about this) $\endgroup$ Commented Jan 31, 2020 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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