Anatoly Anatoly - 2 months ago 23
C Question

How implement trinomial expansion without nested loops.

I'm in process of writing program for equation simplifications. In this program in want to use binomial and trinomial theorems.

With binomial expansion:

(x+y)^r

Sum(k -> r) x^[r-k] y^[k],

where k is 0 and r is degree of binomial.

I can do it like this:

for (k=0; k<=r; k++) {
x_degree=r-k;
y_degree=k;
}


Otherwise, if i want to implement trinomial theoreme i should satisfy constraints of form:

(a+b+c)^n

Sum(n choose i, j, k) a^i b^j c^k,

where n is degree of trinomial and i+j+k=n.

I think about it for a while, but i can't figure out something better than loop through all possible combinations, as follows:

for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
for (int k=0; k<=n; k++) {
if((i+j+k)==n) {
find_coefficient(i,j,k);
set_degree_values(i,j,k);
proceed();
}
}


So my questions is: how implement trinomial expansion without looping through all possible combinations of degrees?

Thank you.

Answer

Taking the fourth degree as an example, the powers of the three variables can be listed as

004, 013, 022, 031, 040, 
103, 112, 121, 130, 
202, 211, 220,
301, 310, 
400

The logics is to decrement the rightmost digit and increment the one to its left. When the latter reaches r, you increment the one to its left and reset the right digits (that's a modified carry operation).

This scheme can be implemented by means of n counters and generalizes to the multinomial theorem. I wouldn't be surprised that the coefficients can be computed incrementally as well. (Actually, the counters will simulate nested loops.)

Comments