# Summation with constraints

I am trying to do the summation shown below, $\sum_{i_1=0}^{imax_1} \sum_{i_2=0}^{imax_2} \dots \sum_{i_k=0}^{imax_k} f(i_1,\dots,i_k)$

$k$ is a variable. Therefore $i$ and $imax$ are defined as arrays of length $k$.

Array[i,k]
Array[imax,k]


Is there a way to accomplish this?

-
Did you try Sum[f,{i,imin,imax},{j,jmin,jmax}]? Maybe you can take a look at this and this. – Rod Jun 14 '13 at 23:03
will that work when i is an array? – AIB Jun 14 '13 at 23:04
Do you have any code which you've already tried to use? As far as I know you could also use {i,imin,imax,di},where di is the step size. – Rod Jun 14 '13 at 23:08
If the terms of your sum are all in an array, you can do this: Total[Array[f[#1, #2, ...] &, {imax1, imax2, ...}, {0, 0, ...}], -1]. – J. M. Jun 15 '13 at 1:12

Quite neat solution (if indices are from 0 to imax):

imax = RandomInteger[{1, 5}, k]

{1, 2, 1, 1}

Total[f @@@ Tuples[Range[0, #] & /@ imax]]

f[0, 0, 0, 0] + f[0, 0, 0, 1] + f[0, 0, 1, 0] + f[0, 0, 1, 1] + ...


Extension for case with imin different from 0.

Total[f @@@ Tuples[Range[##] & @@@ Transpose[{imin, imax}]]]


Edit: I am struggling with question if Array[i,k] is argument for f or set of indices to Array with values. Above solution is for the former. Latter can be easily achieved by following definition:

f[x__] := g @@ (a /@ {x})


if it is not clear one should evaluate this and then Total[...:

g[a[1], a[1], a[0], a[1]] + ....


Maybe this way for the last case is clearer:

Composition[
Total,
Apply[f, #, {1}] &, (* {1,2} -> f[1,2] *)
Map[i, #, {2}] &, (* 1 -> i[1]*)
Tuples,
Map[Range[0, #] &, #] & (*creating sets of indices from 0 to imax_i*)
][imax]

f[i[0], i[0], i[0]] + f[i[0], i[0], i[1]] +...


So for more complicated cases I wolud choose halirutan's solution as shorter.

-
+1 ! Nice approach ! – Rod Jun 15 '13 at 0:23
i and imax are defined as arrays... so it might be possible to i to be, for instance, greater than imax. In this case I believe the code wouldn't work... – Rod Jun 15 '13 at 0:38
@RodLm It seems I was thinkging about something else. If I understand well Your concern: don't worry, if Length@i > Max@imax it is going to works too. – Kuba Jun 15 '13 at 7:23
I'd rather use e.g. Total[f @@@ Tuples[Range[0, #] & /@ imax]] // Short for appropriate formatting instead of .... – Artes Jun 15 '13 at 8:58
@AIB replace f@@@ on f/@: Total[f /@ Tuples[Range[0, #] & /@ imax]] – Kuba Jun 16 '13 at 14:17

Let's assume the following test data

k = 3;
vars = Array[i, k];
imax = RandomInteger[{1, 5}, k];
(*
vars is {i[1], i[2], i[3]}
imax is here {3, 5, 4}
*)


then the nested sum you try to achieve can be written as

Sum[f @@ vars, Evaluate[Sequence @@ ({#1, 0, #2} & @@@ Transpose[{vars, imax}])]]


Since I used a lot of operators which may not be easy to use by new Mathematica users, let me explain the approach in detail. What I want to create first is a list of your iterators. For this I first use Transpose[{vars, imax}] to create list which has the iteration variable and its upper bound side by side:

Transpose[{vars,imax}]
(* Out[5]= {{i[1],1},{i[2],3},{i[3],2}} *)


Now I need to transform this into the form {i[n],0,imaxn}. Therefore I use an anonymous function {#1, 0, #2}&. This function needs to be called like {#1, 0, #2}&[i[1],1] to work but we have sublist elements. They are in the form List[i[1],1]. If I would replace the List head with the anonymous function, everything would be fine. This is the reason why @@@ is used which replaces the heads of the elements inside the main list.

{#1,0,#2}&@@@Transpose[{vars,imax}]
(* Out[6]= {{i[1],0,1},{i[2],0,3},{i[3],0,2}} *)


In the above step we get a list of iteration bounds. This is not useful because we need to give them as Sequence to Sum. Therefore, we again replace a head but this time we replace the List head of the main iterator list by Sequence. Therefore @@ is used in contrast to @@@ which we used to replaced the heads of the elements of the list.

This very same trick is used to apply f to all iteration variables. We have them in a list vars and writing f@@vars creates f[i[1],i[2],...,i[k]].

In a last step we have to remember, that Sum has the attribute HoldAll. Therefore, it does not evaluate our iterator bounds we created so nicely. Instead it sees the whole expression

Sequence @@ ({#1, 0, #2} & @@@ Transpose[{vars, imax}])


which would lead to an error message because Sum expects appropriate bounds. The required evaluation of the above, before Sum sees it can be forced by Evaluate.

-
I didn't take a careful look at your code (I"m at work right now... a little bit short of time...), but I think it is important to put a constraint in the code (I don't know if it already has!) so that i[1] is smaller than imax[1], i[2] smaller than imax[2], etc... – Rod Jun 14 '13 at 23:44
@RodLm i[1] is the iteration variable. It has no value. Every nested sum runs from 0 to imax[n]. – halirutan Jun 14 '13 at 23:57
Oh, I see... +1 ! Initial iteration value is always zero! – Rod Jun 15 '13 at 0:13
k = 3;
Table[{x@i, 0, RandomInteger[{1, 5}]}, {i, k}] /.
it_ :> {First /@ it, it} /.
{{var__}, {it__}} :> Sum[f@var, it]

-