Finding the number of possible combinations for polynomial coefficients

586 Views Asked by At

For example, if I have two numbers

$m=\text{max power of each coefficient}$

$n=\text{max sum of the power of the coefficients}$

so for $~m=2~$ and $~n=3~$, the polynomial(which consists of two variables $~x~$ and $~y~$) would look like

$=c_{1}+c_{2}x+c_{3}y+c_{4}x^2+c_{5}y^2 +c_{6}xy+c_{7}xy^2+c_{8}x^2y$

Is there a good way to find the number of terms in the polynomial.

1

There are 1 best solutions below

5
On

Assuming my interpretation above is correct, after rephrasing and generalizing further the number of available variables (and renaming the variables from $x$ and $y$ to instead $x_1,x_2,\dots,x_k$) you are trying to count the number of non-negative integer solutions to the system:

$$\begin{cases}x_1+x_2+\dots+x_k\leq n\\ 0\leq x_i\leq m~~\forall i\end{cases}$$

If so, then introduce an additional variable, I'll call $y$ equal to $n-x_1-x_2-\dots-x_k$ and you now are working with the system $$\begin{cases} x_1+x_2+\dots+x_k+y \color{red}{=}n\\0\leq x_i\leq m~~\forall i\\ 0\leq y\end{cases}$$

From there, apply inclusion-exclusion over the events that an $x_i$ exceeded the value of $m$ and use stars-and-bars to calculate each case.

You get as a result a total of:

$$\sum\limits_{i=0}^k (-1)^i\binom{k}{i}\binom{n-i(m+1)+k}{k}$$