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$.