Is there an algorithm to get all possible decompositions of a monomial as the product of smaller monomials ?

For example $x^2y^3$ is $x∗xy^3$, $x^2∗y^3$, $xy∗xy^2$, and so on.

For a monomial in one inderminate, I know I can use an integer partitions of the monomial degree.

But this does not apply when there are at least two indeterminates.

(Sorry for misuse of vocabulary and may be uncomplete tags : I am french).

Note : this is a step in construction of an invariant polynomial as described in DOI : 10.1016/j.ijsolstr.2005.05.021.

  • $\begingroup$ Why not partition each indeterminate separately? $\endgroup$ – Kaveh Jul 4 '13 at 21:24
  • $\begingroup$ Integer partitionning of each indeterminate separately will provide me separated sets. My problem is to make the "product" of these sets. This product is not the cartesian product. E.g. xy must be decomposed in xy and xy.Integer partionning will provide only xy. $\endgroup$ – Dominique Jul 8 '13 at 8:13

For the moment, let's restrict to counting these factorizations, rather than listing them. Warming up with the one-variable case, integer partitions give the answer, as you point out. You can compute the number $p(n)$ of partitions of $n$ using the generating function $$\sum_n p(n)x^n = \prod_{i>0} \frac{1}{1-x^i}.$$ This generalizes easily to two variables. If $p(m,n)$ is the number of "partitions" of the 2-long vector $(m,n)$ (i.e. representations of $(m,n)$ as a sum of positive integral multiples of vectors of the form $(i,j)$ with $i,j\ge0$ and $i+j>0$), then $$\sum_{m,n} p(m,n)x^m y^n = \prod_{i,j\ge0;\ i+j>0} \frac{1}{1-x^i y^j}.$$ The sequence $p(m,n)$ appears as A054225 in the OEIS.

If you want to list the factorizations rather than count them, look instead at $$\prod_{i,j\ge0;\ i+j>0} \frac{1}{1-u_{i,j}\ x^i y^j}.$$ For example, the coefficient of $x^2 y^2$ here is $$u_{2,2} + u_{2,1}u_{0,1} + u_{2,0}u_{0,2} + u_{2,0}u_{0,1}^2 + u_{1,2}u_{1,0} + u_{1,1}^2 + u_{1,1}u_{1,0}u_{0,1} + u_{1,0}^2u_{0,2} + u_{1,0}^2 u_{0,1}^2,$$ corresponding to the 9 factorizations of the monomial $x^2 y^2$.

In principle you could write down a two-dimensional recurrence for $p(m,n)$ which is analogous to the recurrence for the ordinary partition numbers. However, for it to be algorithmically useful (e.g. more efficient than computing the series expansion above), one would need a closed form for the coefficient of $x^m y^n$ in the product $$\prod_{i,j\ge0;\ i+j>0} (1-x^i y^j).$$

  • 1
    $\begingroup$ Thanks for this answer. Unfortunately, my mathematics skills does not allow me to fully appreciate the help. I have to study your suggestions. $\endgroup$ – Dominique Jul 8 '13 at 8:21

You can use recursion carrying the account of the degree of each variable. That's an algorithm..to count them you would need partitions and multinomial to simulate commutativity

  • $\begingroup$ Sorry, I do not understand your suggestions. $\endgroup$ – Dominique Jul 8 '13 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.