Function on two variables that restricts to a polynomial Lets say that I have a function $F(x,y)$ that is defined on nonnegative integers (or at least those are the values I care about) and is symmetric, so that $F(x,y)=F(y,x)$.  Moreover, I know that for any fixed value of $y$ I have that $F(x,y)$ is a polynomial in $x$ of degree $y$.  What can I say about the form of the function $F(x,y)$?  
Does it change what we would know if I just know that for any fixed $y$ we have that $F(x,y) = O(x^y)$ rather than a polynomial?
 A: With the polynomiality assumption a characterization is possible. I doubt that much can be said without it.
Theorem: Assuming that $F(x,y)$ is a polynomial in $x$ of degree $y$ for any $y\in \mathbb Z_{\geq 0}$ we have that
$$F(x,y)=\sum_{k\geq 0}\alpha_k (x+y)^k\binom{x+y-2k}{y-k}$$
for some arbitrary sequence $\alpha_0,\alpha_1,\dots.$
Proof: There exist coefficients $\alpha_{k,y}$ such that for each $y\in \mathbb Z_{\geq 0}$ we can write
$$F(x,y)=\sum_{0\le k\le y} \alpha_{k,y}(x+y)^k \binom{x+y-2k}{y-k}.$$
Notice that the terms in this expression are nonzero only if $k\le \min{x,y}$. We can prove by induction on $k$ that $\alpha_{k,y}$ doesn't depend on $y$. For the base case $k=0$ we have $F(x,0)=F(0,x)$ which gives $\alpha_{0,0}=\alpha_{0,x}$. For the general case, assume we have shown our claim for $k\le m-1$. Looking at $F(x,m)=F(m,x)$
for arbitrary $x\geq m$, we cancel out the equal terms that we have from the induction hypothesis and we are left with
$$\alpha_{m,m}(x+m)^m\binom{x-m}{0}=\alpha_{m,x}(m+x)^m\binom{x-m}{x-m}\implies \alpha_{m,m}=\alpha_{m,x}$$
finishing our proof.
A: The general solution for the polynomial case is
$$F(x,y) := \sum_{k=0}^{\textrm{min}(x,y)} a_k {x \choose k}{y \choose k}. \tag1$$
where $a_k$ are any coefficients. Clearly it is symmetric in $x$ and $y$. For a fixed $y$ the function is a polynomial in $x$ with maximum degree $y$, and iff all of the $a_k$ are non-zero, then the degree is exactly $y$.
For the $O(x^y)$ case, $F(x,y)$ as defined in equation $(1)$ is a solution, but otherwise the solutions are very general. In brief, they should not grow too fast, but there does not seem to be a simple way to describe the general solution except to state the obvious. That is,
 $$F(x,0) = O(1),\, F(x,1) = O(x),\, F(x,2) = O(x^2),\, \dots. \tag2$$
