This is a Project Euler question, projecteuler.net/problem=324.

I wondered if it was only known as that in Canada, but I looked it up and found some results, so I used it. $\sum_{j=0}^i \binom{n+j}{j} = \binom{n+i+1}{i}$, because the relevant terms in Pascal's triangle look like a hockey stick.

You're asking for partial tilings of a rectangle with squares. Since you're allowed to use $1 \times 1$ squares, any partial tiling can be filled in with those to a complete tiling. So instead you can find all the complete tilings, a.k.a. tilings, and then count the ways to remove $1 \times 1$ squares from them, which is easy. There is much more literature on complete tilings than partial tilings.

I suspect the poster means the norm inherited from the field extension, rather than the absolute value, i.e. $|a+b\sqrt{-3}| = a^2+3b^2|$, akin to the Gaussian integers. That way the set $P_3$ corresponds to "primes", and the question is about unique factorization in this "deformation". Unfortunately for the poster, this is not the ring of integers for this extension; instead one should consider the Eisenstein integers, where the statement holds after accounting for units. As stated, the question can be resolved by taking two conjugates as the distinct elements, e.g. $2\pm \sqrt{-3}$.

For example, if I haven't made any mistakes, then taking $n=i$ makes all the binomial coefficients of the final term on the left $0$, and taking $i=2$ makes the first summation empty and leaves the others with just one term each, $2x^{i−2}$ and $(i-2)x^{i−1}/2$. So when $n=i=x=2$, the left side is $2$. If the upper index and binomial coefficient in the final term are changed to be in line with the other terms, then everything cancels, and $(x−2)$ divides the left side.

Is the upper index $i$ and the binomial choosing $i-j$ in the last term on the left correct? It seems that taking $x=2$, the second term cancels with the $-2$ part of the $(i-2-l)$ part of the third term, and leaves something remarkably close to the final term, but not equal to it.

@Ralph: how would one verify anything other than a complete set of $9$ elements? You can check that subsets of them do not contain repeats, but knowing that can only verify a full array after you check at least $3$ subsets (when the subsets are 8/9), which seems to be a lot more work.

I think you can do $1$ better for s, assuming I have the right construction in mind which works except on a corner set (flip pairs of elements along each side of the rectangle, so that rows keep the same elements on horizontal flips, and the number of vertical flips is even, and vice versa for columns). This just requires an even number of squares be chosen in each row and column, which you do with a corner set, taking $2$, $2$, and $0$. You can make the same construction with $2$ squares in each row and column (like the complement of a minimal set of squares that meets all corner sets).

However it's defined (monic or not), surely you must have $P/D$ and $Q/D$ polynomials with integer coefficients. What do you take for $2x$ and $2x^2+x$? Either it's a counterexample, or you aren't requiring the quotients to be in $\mathbb{Z}[x]$.