2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Try: $$\sum_{i=0}^n\sum_{j=0}^{n-i} c_{ij}x^iy^j$$ for a degree $n$ polynomial in $x, y$ $\endgroup$ Nov 18, 2020 at 19:49
  • $\begingroup$ 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. $\endgroup$ Nov 19, 2020 at 20:24

1 Answer 1

2
$\begingroup$

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.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .