The pairing function f(a,b) = (a + b)(a + b + 1)/2 + b is the one that arises by drawing diagonals on the natural number lattice, and marching up them from lower right to upper left. See the picture [here](http://books.google.com/books?id=2iJnkaFSojEC&pg=PA443&lpg=PA443&dq=%22polynomial+pairing+function%22&source=bl&ots=2vNse7wfsf&sig=SG_Zy32gr2-ySyjxNuL-ixBlijw&hl=en&ei=nMG8S7XBHoPe9ASnnfGBCA&sa=X&oi=book_result&ct=result&resnum=2&ved=0CAsQ6AEwAQ#v=onepage&q=%22polynomial%20pairing%20function%22&f=false).

In that book, it is noted that Polya has proved that any surjective polynomial pairing function is equal to this function or to its dual form f(b,a). (And someone gave a talk here at CUNY a few weeks ago on precisely this fact.) So if this function is not acceptable to you, then you will find no polynomial surjective function.