Multinomial Generation of Degree n

Question

I'm basically looking for a summation function that will compute multinomials given the number of variables and a degree.

Example

2 Variables; 2 Degrees:

x^2+y^2+x*y+x+y+1

Thanks.

Answer 1

Given N variables, and a maximum degree of D, you have an array of D slots to fill with all possible combinations of variables.

[_, _, ..., _, _]

You are allowed to fill the slots with any of the N variables any number <= D times total. Since multiplication is commutative, it suffices to not care about ordering of variables. As such, this problem is reduced to generating (1) partitions of an integer and (2) subsets of a set.

I hope this is at least a start to your solution.

Answer 2

See Knuth The Art of Computer Programming, Vol. 4, Fascicle 3 for a comprehensive answer.

Short answer: it's enough to generate all multinomial expressions in n variables with degree exactly d. Then, for your problem, you can either put together the answers with degrees ≤d, or add a dummy variable "1".

The problem of generating all expressions with degree exactly d is thus simply one of generating all ordered partitions (i.e., all nonnegative integer solutions to x₁ + ... + x_n = d), and this can be done with a simple backtracking algorithm. ("Depth-first search")