Finding multinomial coefficients by evaluation?

[Stephen Tashi]

TL;DR

Suppose we have a computer program that evaluates a multinomial. We known the general form, but do not know the coefficients. Is there a convenient way to deduce the coefficients by evaluating the multinomial at particular values of its variables?

Suppose we know the general form of a multinomial function (for example $f(x,y,z) = k_1 x^2 y^3 z + k_2 x^3 z^5$) and we have access to a computer program that can evaluate $f$ at arbitrary values (for example, arbitrary values of $(x,y,z)$) where the coefficients ( for example, $k_1$ and $k_2$) are specific numbers that are used by the program, but unknown to us.

Can we conveniently deduce the values of the coefficients by evaluating $f$ at some set of values?

In the above example, we could use $f(1,0,1)$ to deduce $k_2$. Then we can find $k_1$ by using $f(1,1,1)$

Is there a general approach that works for more complicated examples? (I mean an approach that is more convenient that solving a system of simultaneous non-linear equations.)

 

[pbuk]

Summary:: Suppose we have a computer program that evaluates a multinomial. We known the general form, but do not know the coefficients. Is there a convenient way to deduce the coefficients by evaluating the multinomial at particular values of its variables?

Suppose we know the general form of a multinomial function (for example $f(x,y,z) = k_1 x^2 y^3 z + k_2 x^3 z^5$) and we have access to a computer program that can evaluate $f$ at arbitrary values (for example, arbitrary values of $(x,y,z)$) where the coefficients ( for example, $k_1$ and $k_2$) are specific numbers that are used by the program, but unknown to us.

Can we conveniently deduce the values of the coefficients by evaluating $f$ at some set of values?

In the above example, we could use $f(1,0,1)$ to deduce $k_2$. Then we can find $k_1$ by using $f(1,1,1)$

Is there a general approach that works for more complicated examples? (I mean an approach that is more convenient that solving a system of simultaneous non-linear equations.)

I'm not sure I understand what you are asking so this may not be the right answer.

For an equation with $n$ unknown coefficients k = $k_{1..n}$, select $n$ arbitrary points $(x_i, y_i \dots)$ and evaluate $f_i$ at each. For each point, calculate the values of the each of the multinomial terms at that point to give a linear equation $f_i = k_1\alpha_1 + k_2\alpha_2... +k_n\alpha_n$ You then have $n$ linear simultaneous equations for the coefficients k which can be solved by elimination.

Having written that down I am sure I must be missing the point?

 

[mathman]

Just make sure the n sets of points chosen are linearly independent.

 

[pbuk]

Just make sure the n sets of points chosen are linearly independent.

Well yes, and also there must (in general) be no zeros otherwise you are going to lose terms.

 

[Stephen Tashi]

For each point, calculate the values of the each of the multinomial terms at that point to give a linear equation $f_i = k_1\alpha_1 + k_2\alpha_2... +k_n\alpha_n$ You then have $n$ linear simultaneous equations for the coefficients k which can be solved by elimination.

I agree, but is there a way to get a very simple system of equations (e.g. a system whose matrix is triangular)? Can we look at the collection of sets of exponents involved in the terms ( e.g. {(0,1,1) (2,3,1),(2,2,3)} for $yz + x^2y^3z + x^2y^3z^3$) and deduce a set of values to use in our evaluations that make the system of equations very easy to solve?

 

[WWGD]

Summary:: Suppose we have a computer program that evaluates a multinomial. We known the general form, but do not know the coefficients. Is there a convenient way to deduce the coefficients by evaluating the multinomial at particular values of its variables?

Suppose we know the general form of a multinomial function (for example $f(x,y,z) = k_1 x^2 y^3 z + k_2 x^3 z^5$) and we have access to a computer program that can evaluate $f$ at arbitrary values (for example, arbitrary values of $(x,y,z)$) where the coefficients ( for example, $k_1$ and $k_2$) are specific numbers that are used by the program, but unknown to us.

Can we conveniently deduce the values of the coefficients by evaluating $f$ at some set of values?

In the above example, we could use $f(1,0,1)$ to deduce $k_2$. Then we can find $k_1$ by using $f(1,1,1)$

Is there a general approach that works for more complicated examples? (I mean an approach that is more convenient that solving a system of simultaneous non-linear equations.)

Are your x,y,z Integer-valued variables? You were using (1,1,1) and (1,0,1) as examples, but just to make sure.

 

[pbuk]

I agree, but is there a way to get a very simple system of equations (e.g. a system whose matrix is triangular)?

Jacobian elimination on the initial (generally) non-triangular matrix - and if there is difficulty with convergence replace some of the points? Again I think I must be missing the point (excuse the pun).

Can we look at the collection of sets of exponents involved in the terms ( e.g. {(0,1,1) (2,3,1),(2,2,3)} for $yz + x^2y^3z + x^2y^3z^3$) and deduce a set of values to use in our evaluations that make the system of equations very easy to solve?

Oh I think I see now - that would be quite an interesting trick but it's way beyond my algebra comfort zone to even contemplate I'm afraid!

 

[Stephen Tashi]

Are your x,y,z Integer-valued variables? You were using (1,1,1) and (1,0,1) as examples, but just to make sure.

I'd be interested in the most general case, where only the exponents are required to be integers and the coefficients and variables need not be.

However, the less general case where coefficients are integers would be interesting. For example, sometimes we have a mutinomial function expressed as a product such as $f(x,y,z) = (xy + 9xz^2 + 2xyz)(x^3 y^2 z + 4yz)(6xzy^2 -3 zy^3)$ We can list the types of terms that are produced by the multiplication insofar as the different combinations of exponents that will result. It would be nice to have a method for deducing the coefficients of the terms without multiplying out the factors.

Of course, computers can do both symbolic multiplication and numerical evaluation. So this is a question about a pre-computer age trick - analogous to pre-computer calculation tricks like synthetic division.

 

[WWGD]

I'd be interested in the most general case, where only the exponents are required to be integers and the coefficients and variables need not be.

However, the less general case where coefficients are integers would be interesting. For example, sometimes we have a mutinomial function expressed as a product such as $f(x,y,z) = (xy + 9xz^2 + 2xyz)(x^3 y^2 z + 4yz)(6xzy^2 -3 zy^3)$ We can list the types of terms that are produced by the multiplication insofar as the different combinations of exponents that will result. It would be nice to have a method for deducing the coefficients of the terms without multiplying out the factors.

Of course, computers can do both symbolic multiplication and numerical evaluation. So this is a question about a pre-computer age trick - analogous to pre-computer calculation tricks like synthetic division.

For the case of integer variables and exponents, I believe some work has been done in Algebraic Geometry. Maybe @mathwonk knows something about this?

 

[mathwonk]

i don't know anything offhand, but i would ask myself how to find the coefficients of something like axyz + b x^2yz + cxy^2z + dxyz^2 first off. presumably one looks at values of the polynomial and its derivatives.

 

[mfb]

You can get shorter equations by keeping several parameters zero if that still gives you some information. For $f(x,y,z) = k_1 x^2 y^3 z + k_2 x^3 z^5$, choose one point with y=0 to find k₂, then pick any other point where the first term doesn't vanish to determine k₁. This doesn't always work, and for many coefficients you'll need equations that include all parameters simply because no component will be zero. That's unavoidable.

 

[Stephen Tashi]

presumably one looks at values of the polynomial and its derivatives.

If we have only a program that evaluates the multinomial, the values of its derivatives are not given information. However, finite differences such as f(1,1,1) - f(0,1,1) would be available.

 

[mathwonk]

sounds promising.

 

[Stephen Tashi]

sounds promising.

Yes, it looks like we can use finite differences to find the coefficients individually without solving simultaneous equations. I don't know of any texts that work out a multivariable version of the calculus of finite differences. It seems straightforward.

Define $\Delta_x f(x,y,..) = f(x+1,y,..) - f(x,y,..)$ and use notation like $\Delta^3_x f(x,y) = \Delta_x( \Delta_x( \Delta_x f(x,y,...))$

By analogy with McLaurin series, I'd think that

$f(x,y,z) = f(0+x,0+y,0+z) = f(0,0,0) + \sum_{i=1,j=1,k=1}^{n_x,n_y,n_z} \frac{1}{i!j!k!} k_{i,j,k} x^i y^j z^k$ with $k_{i,j,k} = \Delta_x^i \Delta_y^j \Delta_z^k f(x,y,z)$ evaluated at $(x,y,z) = (0,0,0)$.