Chained sums with Nest

Question

I'm looking to calculate a chained sum like this $$ C_m = \sum\limits_{i_1=1}^N \;\sum\limits_{i_2=i_1+1}^N \;\sum\limits_{i_3=i_2+1}^N \cdots \;\sum\limits_{i_m=i_{m-1}+1}^N A_{i_1}A_{i_2}A_{i_3}\cdots A_{i_m} $$ For example, when $m=3$, this becomes $$ C_3 = \sum\limits_{i=1}^N \;\sum\limits_{j=i+1}^N \;\sum\limits_{k=j+1}^N A_i A_j A_k $$ Of course the point is I want $m$ to remain unspecified in the algorithm. Now, I know how to implement this by manually making the iterator lists (e.g. with Tuples) and applying Sum on it. But to me that feels more like a hack than elegant code.

As I always try to get my code as elegant as possible, I see this as a good opportunity to learn.One of the concepts I always have difficult to grasp (but would love to master), is the use of Nest and Fold. A this sum can be seen as a function nesting on itself $$ C_m = \sum\limits_{i_1=1}^N A_{i_1} \left[ \;\sum\limits_{i_2=i_1+1}^N A_{i_2} \left[ \;\sum\limits_{i_3=i_2+1}^N A_{i_3} \left[ \cdots\vphantom{\sum\limits_{i_3=i_2+1}^N} \right]\right]\right] $$ I'd expect Nest to be an ideal candidate. I've tried a bit, but the best I could come up with is

f[g_,j_] := Sum[g[k]A[k], {k,j+1,n}]
F[x_] := f[x,#]&

c[m_] := f[Nest[F,1&,m-1],0]

I find this particularly ugly, especially the two function definitions that still need a pure function inside F, as well as the fact that I need to wrap an additional f around Nest. It gets even uglier if I try to avoid the need to define f and F:

c[m_] := Sum[
  Nest[ Function[var,Sum[var[k]A[k],{k,#+1,5}]&], 1&, m-1][l] A[l]
, {l,1,n}]

with the need to use Function and &.

So here's my question: is there a neater way to achieve this chained sum using Nest? If not, maybe by using Fold or another functional construct?

Answer 1

Table does this automatically. You should be able to adapt the following code:

f[m_, n_] := Sum[
   Product[A[i[j]], {j, 1, m}] // Evaluate, 
   Sequence @@ Prepend[Table[{i[j], i[j - 1] + 1, n}, {j, 2, m}], {i[1], 1, n}] // Evaluate
  ]

Thus

f[2, 3]
(* A[1] A[2] + A[1] A[3] + A[2] A[3] *)

and

f[3, 5]
(* A[1] A[2] A[3] + A[1] A[2] A[4] + A[1] A[3] A[4] + A[2] A[3] A[4] + A[1] A[2] A[5] + A[1] A[3] A[5] + A[2] A[3] A[5] + A[1] A[4] A[5] + A[2] A[4] A[5] + A[3] A[4] A[5] *)

---

Alternatively, generate the indices directly, and apply the function to them, like so:

f2[n_, m_] := Times @@@ Map[A, Subsets[Range[m], {n}], {2}] // Total
f2[3, 5]
(* A[1] A[2] A[3] + A[1] A[2] A[4] + A[1] A[3] A[4] + A[2] A[3] A[4] + A[1] A[2] A[5] + A[1] A[3] A[5] + A[2] A[3] A[5] + A[1] A[4] A[5] + A[2] A[4] A[5] + A[3] A[4] A[5] *)

and

f[3, 5] - f2[3, 5]
(* 0 *)

Or

f3[n_, m_] := Sum[Times @@ A /@ is, {is, Subsets[Range[m], {n}]}]

Answer 2

"Nest[f,expr,n] gives an expression with f applied n times to expr."

Nest takes a function, an expression, an n of positive Integers.

No more, no less.

Nest is somehow outdated.

It is superseded by Composition.

Composition is the mathematical elementary term from with Nest is derived.

There is an example in the documentation of Composition for a sum:

Composition[HoldForm, Plus] @@ Range[20]
___
\!\(
TagBox[
RowBox[{"1", "+", "2", "+", "3", "+", "4", "+", "5", "+", "6", "+", 
    "7", "+", "8", "+", "9", "+", "10", "+", "11", "+", "12", "+", 
    "13", "+", "14", "+", "15", "+", "16", "+", "17", "+", "18", "+", 
    "19", "+", "20"}],
HoldForm]\)

This clears that Sum and Nest are rather different.

Sum is derived from Plus in the above manner. The documentation page of Plus shows some alternative to Sum.

To built up complicated products Mathematica offers the built-in Product. There is neither a line with Nest on the documentation page of Product nor vice versa.

What does that imply for Your question? Now at first nothing. But it is a strong hint.

While Nest is iterative with n, the "times" constant at the third argument position, Product does not require a x" but an iterator i with start and end. That is what Your summands represent. I accept the examples in the documentation page for Product are far to easy or much the specialized.

There are some nice examples and methods, how to make this more efficient:

∑𝑖=2𝑁cos𝜃𝑖cos𝜃′𝑖∏𝑗=𝑖+1𝑀sin𝜃𝑗𝜃′𝑗

    NSum[Cos[θ[[i]]] Cos[Θp[[i]]] Product[    Sin[θ[[j]]] Sin[θp[[j]]], {j, i + 1, d - 1}], {i, 2,    d - 1}]


f[M_, n_] := Reverse[Table[Cos[θ[i]] Cos[θ'[i]], {i, 2, n}]].PadLeft[FoldList[
Sin[θ[M - #2] θ'[M - #2]] # &, Sin[θ[M] θ'[M]], Range[M - 3]], Max[n - 1, 0], 1]

This question is already concerned about sum or product with exclusions.

Sum is more essential for getting closed formulars like in this example:

Sum[Product[i^2, {i, 1, n}], {i, 1, n}]
n (n!)^2

n = 4;
Times @@ Flatten@Table[f[a[i] - a[j]], {i, 1, n - 1}, {j, i + 1, n}]

or

With[{n = 6}, Times @@ f /@ Subtract @@@ Subsets[Array[a, n], {2}]]

can be either done with an iterator or a list. The iterator needs the coefficients list to be already defined and iterates over it in a linear fashion. In more modern Mathematica versions the second version shall be faster in most contexts.

The formula makes use of different operators @, @@ and @@@ that are different to Composition @*.

This is a highly rated answer about scan vs map vs apply. This answer explains some differences between Composition and Apply. This answers go much deeper in the topics related: v10s operator forms what are they good for?

Some common misconception is addressed in this answers: how do i designate arguments in a nested map.

ClearAll[list1, list2, a, b, c, x, y, z, f]
list1 = {a, b, c}
list2 = {x, y, z}
___
Map[Map[f[#1, #2] &, list1] &, list2]
__
list2
___
Map[Function[x, Map[f[#1, x] &, list1]], list2]
___
list2

But the desired result is this

Outer[f, list1, list2]
(*
  {{f[a, x], f[a, y], f[a, z]}, 
   {f[b, x], f[b, y], f[b, z]}, 
   {f[c, x], f[c, y], f[c, z]}}
*)

Map[Function[p2, Map[Function[p1, f[p1, p2]], list1]], list2]

(* {{f[a, x], f[b, x], f[c, x]}, {f[a, y], f[b, y], f[c, y]}, {f[a, z], f[b, z], f[c, z]}} *)

If f in not listable this can be too written this way:

Distribute[f[{a, b, c}, {x, y, z}], List]
(*
  {{f[a, x], f[b, x], f[c, x]}, 
   {f[a, y], f[b, y], f[c, y]}, 
   {f[a, z], f[b, z], f[c, z]}}
*)

The next alternative is

Tuples[{{a, b, c}, {x, y, z}}] ({{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}, {c, x}, {c, y}, {c, z}})

Apply[f, Tuples[{{a, b, c}, {x, y, z}}], {1}]

({f[a, x], f[a, y], f[a, z], f[b, x], f[b, y], f[b, z], f[c, x], f[c, y], f[c, z]})

And this, in turn, allows for the desired Nest:

Nest[f, #, 1] & /@ Tuples[{{a, b, c}, {x, y, z}}] ({f[{a, x}], f[{a, y}], f[{a, z}], f[{b, x}], f[{b, y}], f[{b, z}], f[{c, x}], f[{c, y}], f[{c, z}]})

This question about nest-fold-is-there-an-extension-for-more-than-2-arguments refers to a chapter 5.5.3 Restriction of Fold-ed function to two arguments is spurious of an online book by Leonid Shifrin and an example with three slots:

multiFoldList[f_, start_, args__List] := 
 FoldList[f @@ Prepend[#2, #] &, start, {args}\[Transpose]] 
____
multiFoldList[#1 (1 + #2) - #3 &, 1000, {.01, .02, .03}, {100, 200, 
  300}]
___
{1000, 910., 728.2, 450.046}

These are very special but these make the trick and the extensions are already included.

For now finally, I like to refer to this overview article

alternatives-to-procedural-loops-and-iterating-over-lists-in-mathematica/

that includes some examples using Fold and Nest and compare this in different situations to alternative built-ins. This is all quite nice and offers deeper knowledge into what Nest does and can do and what not. I compare the built-in Nest to other built-ins and combinations and Compositions.

Search the Mathematica documentation for Iterator to get this as the better definition for the input value n and some explanation for the Mathematica paradigm selection about that.

There are two definitions for Expression in the Mathematica documentation one for the cells and one for the Wolfram Language interpreter. So such a search guide into inputs dedicated for the helpfulness of WolframAlpha

Have a look at FixedPoint a built-in historically grouped with Nest and for the generation of Mathematica users as the limiting built-in of Nest for infinite iterations, applications. The famous tutorial was Applying functions repeatedly.

defines the ranges for the indices that can Mathematica based on the Wolfram Language cope with.

So that is what Nest and alike is lacking and Prodcut has.