<s>[INST] Sequence and polynomial power relationship I recently encountered this relationship between polynomial powers and a certain associated sequence and I am seeking any help or idea that might answer why the relationship is true.
Let $P(x)$ be a polynomial, say for instance $P(x)=1+3x+2x^2$. Consider the consecutive powers of $P(x)$ and arrange the numerical coefficients in order of appearance. For the given $P(x)$ we have for up to fifth power:
$P(x)^1=1+3x+2x^2$
$P(x)^2=1 + 6 x + 13 x^2 + 12 x^3 + 4 x^4$
$P(x)^3=1 + 9 x + 33 x^2 + 63 x^3 + 66 x^4 + 36 x^5 + 8 x^6$
$P(x)^4=1 + 12 x + 62 x^2 + 180 x^3 + 321 x^4 + 360 x^5 + 248 x^6 + 96 x^7 + 
 16 x^8$
$P(x)^5=1 + 15 x + 100 x^2 + 390 x^3 + 985 x^4 + 1683 x^5 + 1970 x^6 + 
 1560 x^7 + 800 x^8 + 240 x^9 + 32 x^{10}$.
Also, consider the sequence defined by
$a_{m,n}=a_{(m-1),n}+3a_{(m-1),(n-1)}+2a_{(m-1),(n-2)}$ with $a_{1,1}=1,a_{1,2}=3$ and $a_{1,3}=2$.
Observe that the sequence above completely determines the entries in the expansion of the polynomial power. For instance the number $63$ in the third power of $P(x)$ is equal to $63=12+3(13)+2(6)$.
I am wondering why is this TRUE. Thanks for your help and suggestion.
 [/INST] In the product $$(1 + 6 x + 13 x^2 + 12 x^3 + 4 x^4)(2x^2+3x+1)$$ if you try to compute the coefficient of $x^3$, note that $x^3$ can be formed in the following ways 
$12x^3$ from the first bracket, $1$ from the second bracket 
$13x^2$ from the first bracket, $3x$ from the second bracket 
$6x$ from the first bracket, $2x^2$ from the second bracket 
that is, you can form the power $3$ of $x$, in the following ways $$3+0,\ 2+1,\ 1+2$$ where the first term in these sums is the power of $x$ you are taking from the first bracket and the second term is that you are taking from the second bracket.
Hence, the coefficient of $\texttt{x^3}$ in $P(x)^3$ is 
$(\text{coeff. of x^2 in P(x)}=2)\times\text{coeff. of x in }P(x)^2$ 
$+(\text{coeff. of x^1 in P(x)}=3)\times\text{coeff. of x^2 in }P(x)^2$ 
$+(\text{coeff. of x^0 in P(x)}=1)\times\text{coeff. of x^3 in }P(x)^2$
$= 1\cdot a_{2,n} + 3\cdot a_{2,n-1} + 2\cdot a_{2,n-2}$ 
Basically, $a_{m,n}$ is the coefficient of $x^{n}$ in $P(x)^m$.
So, what your recurrence relation is doing is framing the distributive law of multiplication over addition in an interesting way. (This representation will be helpful to you in understanding how generating functions aid counting in combinatorics.)
</s>