# Efficient way to assemble polynomial terms with more than one variable?

Assume that I have a scalar variable $$x$$. For this variable, I can write down a second degree polynomial:

$$f(x) = c_0 + c_1x + c_2x^2$$

where $$c_0$$, $$c_1$$, and $$c_2$$ are scalar coefficients. Now assume that my polynomial does not only depend on $$x$$, but also on two other variables $$y$$ and $$z$$. For simplicity, assume that we wish to limit the order of terms of each summand to 2, so we get:

$$f(x,y,z) = c_0 + c_{1}x + c_{2}y + c_{3}z + c_{4}x^2 + c_{5}y^2 + c_{6}z^2 + c_{7}xy + c_{8}yz + c_{9}xz$$

Obviously, the first seven terms are simply the independent polynomial terms of all three variables. The remaining terms are cross-variable terms, whose (summed) order I somewhat arbitrarily limited to 2 (different limitations would of course also be possible).

Now my question: Is there an easy version to find all combinations of variables for the remaining terms for arbitrary numbers of particles and upper order limits?

A brute-force solution would be to create all possible combinations, then discard the ones which violate the order limit:

$$\require{cancel}x+y+z+x^2+y^2+z^2+xy+xz+yz+\cancel{x^2y}+\cancel{x^2z}+\cancel{xy^2}+\cancel{y^2z}+\cancel{xz^2}+\cancel{yz^2}+\cancel{x^2y^2}+\cancel{x^2z^2}+\cancel{y^2z^2}$$

However, this quickly becomes infeasible for larger variable counts.

• Try: $$\sum_{i=0}^n\sum_{j=0}^{n-i} c_{ij}x^iy^j$$ for a degree $n$ polynomial in $x, y$ Nov 18, 2020 at 19:49
• You can identify the terms with the ordered partitions of the total degree bound $N$ into $v$ parts, where $v$ is the number of variables, allowing zeroes. Those terms might help you search the internet for a description or count that serve your needs. Nov 19, 2020 at 20:24

I don't quite know what you mean by "find" in your question. Do you mean how to list or name them all? The general term of a polynomial in $$k$$ variables $$x_1, \dots x_k$$ has the form
$$c_{i_1, i_2, \dots i_k} x_1^{i_1} x_2^{i_2} \dots x_k^{i_k}$$
with total degree $$\sum_{j=1}^k i_j$$. If you want to bound the total degree then you just enforce a bound on this sum, so the general polynomial in $$k$$ variables of degree at most $$n$$ is
$$\sum_{i_1, i_2, \dots i_k \in \mathbb{Z}_{\ge 0} : \sum i_j \le n} c_{i_1, i_2, \dots i_k} x_1^{i_1} x_2^{i_2} \dots x_k^{i_k}.$$
Writing all those subscripts can get annoying so it's convenient to use multi-index notation instead: we package up the tuple $$(i_1, i_2, \dots i_k)$$ of indices into a single vector index $$I$$ and similarly package up the tuple $$(x_1, x_2, \dots x_k)$$ of variables into a single vector variable $$x$$, then define $$x^I = x_1^{i_1} x_2^{i_2} \dots x_k^{i_k}$$. If we also write $$|I| = \sum_{j=1}^k i_j$$ for the total degree then the above summation can be written in the simplified form
$$\sum_{I \in \mathbb{Z}_{\ge 0}^k : |I| \le n} c_I x^I.$$