How to define a bijection between natural numbers and the set of all polynomials with natural coefficients and finite variables? Is there an explicit algorithm which establish a bijection between polynomials with finite variables and natural coefficients and natural numbers. Does anyone have one of these?Thanks.
 A: For this question, I'm going to gloss over the question of whether or not $0\in\mathbb N$. There's a clear bijection between the two options in any case, so I'll only refer to positive integers and non-negative integers.
To understand how to do what you ask, it's probably easiest to understand how to encode finite sequences of non-negative integers as a positive integer, and then how to encode your polynomials as those.
The usual way of doing the former is in prime factorisations. Since prime factorisations are unique, if I have $a_1\dots a_n$ non-negative integers and $p_1 \dots p_n$ prime numbers, I can recover the $a_k$ from the prime factorisation of the positive integer $p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}$.
With regards to the latter, you just need to pick an ordering of your terms and read off the coefficients. I might as well pretend you have infinitely many variables, and just all but finitely many have zero coefficients, but now there's some subtlety in how I order them so that I do eventually get to every one. I think what I'll do is call the variables $x_1, x_2 \dots$ and then define the combined degree of a term to be its degree plus the sum of the subscripts used in that term. That way, every term has finite combined degree, but crucially there are only finitely many terms of each combined degree, so if I just list the terms by increasing combined degree, any term will eventually be listed. Pedantically, I do also need to choose an ordering within each collection of terms of given combined degree, but that's not actually difficult - lexicographic order is as good as any. The listing would start $1, x_1, x_1^2, x_2, x_1^3, x_2^2, x_3, x_1^4, x_1x_2, x_2^3, x_3^2, x_4, \dots$
Under this correspondence, I encode $4 + 2x_3^2 + x_1x_2$ as the sequence $4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2$ and hence as the integer $p_1^4p_9p_{11}^2=2^4\times23\times31^2=353648$.
