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?



Function on two variables that restricts to a polynomial
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.


