Is there any convenient way to index the monomials up to a given order by a number?

128 Views Asked by At

One canonical way of indexing a monomial of $n$ variables is to use a $n$-tuple of the powers, i.e., using $(\alpha_1, \ldots, \alpha_n)$ to index $x_1^{\alpha_1}\ldots x_n^{\alpha_n}$. I'm wondering whether there is a convenient way to use one number to index $x_1^{\alpha_1}\ldots x_n^{\alpha_n}$.

For instance, for $2$ variables, we can align all the possible monomials as $1, x_1, x_2, x_1^2, x_1x_2, x_2^2, \ldots$, so that the index for $x_1^{\alpha_1}, x_2^{\alpha_2}$ is $\frac{1}{2}(\alpha_1 + \alpha_2 +1)(\alpha_1+\alpha_2) +\alpha_2 +1 $. And more importantly, given an index $k$ in this order of monomials, we can compute the corresponding $\alpha_1, \alpha_2$. Is there a generalization of this idea to $n$ variable monomials?

1

There are 1 best solutions below

2
On

The best you can do is an ordered pair $(n, a)$ for $n$ defining the number of indeterminates of your multivariate polynomial and $a$ being its position with respect to some ordering.

For graded lexicographic ordering with ordering among the indeterminates as $x_1 < x_2 < x_3 < \cdots$, we have

\begin{align*} F[x_1, x_2] \\ \begin{array}{|c|c|c|c|} \hline \text{Monomial} & a & (\alpha_1, \alpha_2) \\ \hline x_1^{0} x_2^{0} & 0 & (0, 0) \\ \hline x_1^{0} x_2^{1} & 1 & (0, 1)\\ \hline x_1^{1} x_2^{0} & 2 & (1, 0)\\ \hline x_1^{0} x_2^{2} & 3 & (0, 2)\\ \hline x_1^{1} x_2^{1} & 4 & (1, 1)\\ \hline x_1^{2} x_2^{0} & 5 & (2, 0)\\ \hline x_1^{0} x_2^{3} & 6 & (0, 3)\\ \hline \vdots & \vdots & \vdots \\ \hline \end{array} \end{align*} and \begin{align*} F[x_1, x_2, x_3] \\ \begin{array}{|c|c|c|c|} \hline \text{Monomial} & a & (\alpha_1, \alpha_2) \\ \hline x_1^{0} x_2^{0} x_3^0 & 0 & (0, 0, 0) \\ \hline x_1^{0} x_2^{0} x_3^{1} & 1 & (0, 0, 1)\\ \hline x_1^{0} x_2^{1} x_3^{0} & 2 & (0, 1, 0)\\ \hline x_1^{1} x_2^{0} x_3^{0} & 3 & (1, 0, 0)\\ \hline \vdots & \vdots & \vdots \\ \hline \end{array} \end{align*} There are $\binom{n}{d}$ monomials of degree $d$ and you can use this fact to help implement such a conversion between the multi-index $\mathbf{\alpha}$ and the ordered-pair ordering.