# Generating polynomials with conditions on coefficients

I want to define polynomials with coefficients given in some range.

Namely, let $p$ be a prime number and $n$ be a positive integer. For all positive integer $k\leq n$ I want to generate all polynomials of degree $k$ with integer coefficients

$$a[0]+a[1]x+...+a[k]x^k$$

such that $a[k]=1$, $a[0]\neq0$ and $0\leq a[i]\leq p-1$ for $1\leq i\leq k-1$.

How can I do this?

• …but no other restrictions on $a[0]$? There are a lot of integers $\ne 0$… Jun 24, 2015 at 19:55

I post this for illustration. As @Xilin has commented there is a combinatorial explosion from early. If some small number cases are desired and assuming $1\le a_0\le p-1$ and all polynomials of degree $1\le k\le n$,

poly[p_?PrimeQ, n_, x_] :=
PowerRange[1, x^n, x].# & /@ ({##, 1} & @@@
Tuples[({Range[p - 1], ##} & @@ Table[Range[0, p - 1], {n - 1}])])
poln[p_, n_] := (p - 1) p^(n - 1)


Example:

Grid[({#, Column[poly[3, #, s]], poln[3, #]} & /@ Range[1, 3]),
Frame -> All]


where the first column is $k$, the second column the desired polynomials and the number of polynomials for degree $k$:

You can do this, it's just that you're going to get a lot of polynomials. If your description of what you want is accurate, it's $(p-1)\times p^{k-1}$ polynomials for each $k$ and add that up for every $k ≤ n$. With $n = 5, p = 7$, you'll get 16806 polynomials. With $n=10, p=11$, the number is $25937424600$.