Question

To clarify: by unique I mean disregarding permutation of variables. Say I have n variables, and want to generate all "unique" polynomials of degree 2 and 1 (powers are excluded). For example, for n = 3, x1 x2 and x3 are the variables.

x1x2 or x1x2 + x2x3 or x1x3 + x1 or x3 are all example polynomials.

But, x1x2 + x3 can be considered the same polynomial as x1x3 + x2, since variables are simply swapped. I'd like to generate only the "unique" polynomials, (in this case, x1x2 + x3, x1x3 + x2, x2x3 + x1 would all be considered the same under permutation of variables).

I think the polya enumeration theorem is applicable here, but i'm not quite sure how to use it.

Thanks for the help!

Answer 1

A similar thing is done in this paper: http://arxiv.org/pdf/1104.0589 (I am one of the authors), where one consider homogeneous polynomials, which are unique w.r.t permutation of variables, and translation. These corresponds one-to-one with multigraphs. The translation-invariance can be removed by a change of variables, reducing the number of variables by 1, and adding different homogeneous parts should give arbitrary polynomials.