[Math] Calculating the number of iterations in a variable number of nested for-loops

programmingsummation

My goal is to calculate the number of iterations made in a variable number of for-loops following this structure:

for(i = 0; i <= x; i++)
  for(j = 0; j <= i + 1; j++)
    for(k = 0; k <= j + 1; k++)
      ...
        for(n = 0; n <= (n - 1) + 1; n++)

For example, how many iterations will be made when x = 10 with 5 loops?

To try forming an equation for this problem, I searched for a pattern by simplifying summations. Here are my results:

One for-loop:

  • Summation: $$\sum_{i=0}^x 1$$
  • Simplified: $$x+1$$

Two for-loops:

  • Summation: $$\sum_{i=0}^x \sum_{j=0}^{i+1} 1$$
  • Simplified: $$\frac{x^2+5x+4}{2}$$

Three for-loops:

  • Summation: $$\sum_{i=0}^x \sum_{j=0}^{i+1} \sum_{k=0}^{j+1} 1$$
  • Simplified: $$\frac{x^3+12x^2+41x+30}{6}$$

The only patterns that I see are:

  • The denominator could be represented as $n!$
  • The numerator is a polynomial of degree $n$

How can I represent a variable number of these nested loops as an equation?

Best Answer

Let us consider the problem with $p$ summations and counting as you did the formulae are $$\left( \begin{array}{cc} p & S_p \\ 1 & (x+1) \\ 2 & \frac{1}{2} (x+1) (x+4) \\ 3 & \frac{1}{6} (x+1) (x+5) (x+6) \\ 4 & \frac{1}{24} (x+1) (x+6) (x+7) (x+8) \\ 5 & \frac{1}{120} (x+1) (x+7) (x+8) (x+9) (x+10) \\ 6 & \frac{1}{720} (x+1) (x+8) (x+9) (x+10) (x+11) (x+12) \end{array} \right)$$ from which seems to appear the general pattern

$$\color{red}{S_p=\frac 1{p!}(x+1)\prod_{i=p+2}^{2p}(x+i)}$$ Using Pochhammer symbols $$S_p=\frac{(x+1) }{p!}(x+p+2)_{p-1}$$ You also could use $$\frac{S_{p+1}}{S_p}=\frac{(x+2 p+1) (x+2 p+2)}{(p+1) (x+p+2)}$$ For $p=5$ and $x=10$, this would give $10659$.

Related Question