Re: multinomials: a programming question

*To*: mathgroup at smc.vnet.net*Subject*: [mg3961] Re: multinomials: a programming question*From*: danl (Daniel Lichtblau)*Date*: Mon, 13 May 1996 01:46:02 -0400*Organization*: Wolfram Research, Inc.*Sender*: owner-wri-mathgroup at wolfram.com

In article <4menll$jva at dragonfly.wolfram.com> Jack Goldberg <jackgold at admin.lsa.umich.edu> writes: > Hello Mma users, > > I am concerned about some limitations in the Sum command. > Here is the example that motivated this message. Although > Mma can easily expand (a+b+c)^n for any specific non-negative > choice of integer n, I need to write the trinomial expansion > out in terms of Sum. Something like this: > > tri[a_,b_,c_,n_] := Sum[Multinomial[i,j,k]*a^i*b^j*c*k, ???] > where i+j+k = n. (Multinomial is a built-in function.) > > The problem is with the iterator(s). The condition i+j+k = n > is causing me great difficulty. What would be nice is a solution > that works in the general multinomial case, but perhaps that is asking > too much - I would be happy for the trinomial expansion. > > The more general issue here is this: Many sums in mathematics (most > more important than the above trivial problem) are indexed over more > complicated sets than allowed by the syntax of Sum. For example, > open any book on number theory - I opened my copy of An Introduction > To The Theory of Numbers, I. Niven et. al. - and found the Mobius > inversion formula, pg 194, part > of which reads (subject to the limitation of my keyboard) > > The sum over all divisors d of n of the product of > mu(d)*F(n/d) ... > > Instead of having to recast this remarkable formula into terms > understandable by Sum, wouldn't it be nice to have the set over > which the sum is taken be given as the iterator. Then my trinomial > problem would be solved like this: > > tri[a_,b_,c_,n_] := Sum["as above", {i+j+k=n}] > > Your thoughts are more than welcome! > > Jack Goldberg > University of Michigan > > This is along the lines of what you want, for the simple case of trinomials. In[72]:= tri[a_,b_,c_,n_] := Sum[Multinomial[i,j,n-i-j]*a^i*b^j*c^(n-i-j), {i, 0, n}, {j, 0, n-i}] In[73]:= tri[a,b,c,4] 4 3 2 2 3 4 3 2 Out[73]= a + 4 a b + 6 a b + 4 a b + b + 4 a c + 12 a b c + 2 3 2 2 2 2 2 3 3 4 > 12 a b c + 4 b c + 6 a c + 12 a b c + 6 b c + 4 a c + 4 b c + c For the more general case I believe the fragment below is correct. In[114]:= multinom[n_Integer, x___] := Module[ {len=Length[{x}], jj, indices, xx={x}, expons, iterators}, indices = Array[jj, {len-1}]; expons = {Apply[Sequence,indices], n-Apply[Plus,indices]}; iterators = Table[{indices[[j]], 0, n-Apply[Plus, Take[indices, j-1]]}, {j, len-1}]; Sum[Multinomial[Apply[Sequence,expons]] * Apply[Times, xx^expons], Evaluate[Apply[Sequence, iterators]]] ] In[115]:= multinom[3, w, x, y, z] 3 2 2 3 2 2 2 Out[115]= w + 3 w x + 3 w x + x + 3 w y + 6 w x y + 3 x y + 3 w y + 2 3 2 2 2 > 3 x y + y + 3 w z + 6 w x z + 3 x z + 6 w y z + 6 x y z + 3 y z + 2 2 2 3 > 3 w z + 3 x z + 3 y z + z Daniel Lichtblau Wolfram Research, Inc. danl at wolfram.com ==== [MESSAGE SEPARATOR] ====