# Combinatorial problems which can be solved with polynomials

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

• Simultaneous posting on MSE. Commented Jan 19, 2020 at 21:26
• Not exactly the same thing, but possibly some of the answers at matheducators.stackexchange.com/questions/13099/… might help. Commented Jan 27, 2020 at 21:57
• I think the MSE has us beat pretty bad on this one. Commented Jan 31, 2020 at 4:09
• A surprising (and very nice) application is math.stackexchange.com/questions/3031612/… Commented Feb 11, 2020 at 1:05

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\}$$.

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