The hint pretty much solves the problem. Basically, we dovetail on n, the degree of the polynomial, and on n+1 copies of the natural numbers to assign the n+1 coefficients. Formally, we proceed by induction. For n=0, the set of polynomials of degree 0 is just Z, which is known to be countable. Assume then that the set Pn-1 of all polynomials of degree not exceeding n-1 is countable (our inductive hypothesis) and consider the set Pn of all polynomials of degree not exceeding n. This set is the union of Pn-1, a countable set by inductive hypothesis, and of the set of all polynomials of degree equal to~n. Thus, by Exercise 2.42, we need only show that the set of polynomials of degree n is countable, since the union of two countable sets is itself countable. Any polynomial of degree n can be written as an xn + pn-1(x), where pn-1(x) is a polynomial of degree not exceeding n-1. by inductive hypothesis, we have a procedure to enumerate the latter type of polynomial; the first term is simply a matter of choosing an in Z. Thus we can dovetail on the value of an (all integers) and on all polynomials of degree not exceeding n-1 and enumerate all polynomials of degree n. Now that we know that, for each fixed n, the set of all polynomials in one variable of degree not exceeding n is countable, we use one more level of dovetailing, on all positive integers n (degree), to enumerate the set of all polynomials in one variable.