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

Question

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?

Answer 1

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

Answer 2

Main Solution

Using notation for falling factorials, let $$\begin{align} f(x)\quad\; &=\frac {x+1}{(p+1)!}(x+mp+m)^\underline{p}\\ &=\frac {x+1}{(p+1)!}(x+mp+m-1)^\underline{p-1}(x+mp+m)\\ \Rightarrow\quad f(x-1) &=\frac x{(p+1)!} (x-1+mp+m)^\underline{p}\\ &=\frac x{(p+1)!}(x+mp+m-p)(x+mp+m-1)^\underline{p-1}\\ \text{Subtracting,}\hspace{3.5cm}\\ f(x)-f(x-1) &=\frac {(x+mp+m-1)^\underline{p-1}}{(p+1)!}\big[(x+1)\ (x+mp+m)-x\ (x+mp+m-p)\big]\\ &=\frac {(x+mp+m-1)^\underline{p-1}}{(p+1)!}\big[(x+m)(p+1)\big]\\ &=\frac {(x+m)}{p!} \big(x+mp+m-1\big)^\underline{p-1} \\ &=\bigg\langle {x,p\atop p}\bigg\rangle_m \hspace{5cm}\text{(assigned notation)}\\ \text{Summing by telescoping gives}\hspace{0cm}\\ \sum_{x=0}^{y+m-1}\bigg\langle {x,p\atop p}\bigg\rangle_m &=f(y+m-1)\\ &=\frac {(y+m)}{(p+1)!}\big(y+mp+2m-1\big)^\underline{p}\\ &=\frac {(y+m)}{(p+1)!}\big(y+m(p+1)+m-1\big)^\underline{p}\\ &=\bigg\langle {y,p+1\atop p+1}\bigg\rangle_m \hspace{6cm}\cdots (1)\\ \end{align}$$

For $m=2$,

$$\begin{align} &\sum_{x=0}^{y+1}\bigg\langle {x,p\atop p}\bigg\rangle_2 &&=\bigg\langle {y,p+1\atop p+1}\bigg\rangle_2\\ \text{i.e.}\qquad\qquad &\sum_{x=0}^{(y+1)}\frac {x+2}{p!}(x+2p+1)^{\underline{p-1}} &&=\frac {(y+2)}{(p+1)!}(y+2p+3)^\underline{p}\\ p=1:\;\; &\sum_{x=0}^{y+1}(x+2) &&=\frac 12(y+2)(y+5)&\\ p=2:\;\; &\sum_{r=0}^{y=1}\frac 12(x+2)(x+5) &&=\frac 16(y+2)(y+6)(y+7)&\\ p=3:\;\; &\sum_{r=0}^{y=1}\frac 16(x+2)(x+6)(x+7) &&=\frac 1{24}(y+2)(y+7)(y+8)(y+9)& \\ \end{align}$$

(*) The angle bracket coefficient notation facilitates the cascading of summation, e.g. $$\begin{align} \sum_{x=0}^{y+1}\sum_{i=0}^{x+1}\sum_{j=0}^{i+1}\sum_{k=0}^{j+1}1 &=\sum_{x=0}^{y+1}\sum_{i=0}^{x+1}\sum_{j=0}^{i+1}\bigg\langle {j,1\atop 1}\bigg\rangle_2\\ &=\sum_{x=0}^{y+1}\sum_{i=0}^{x+1}\bigg\langle {i,2\atop 2}\bigg\rangle_2\\ &=\sum_{x=0}^{y+1}\bigg\langle {x,3\atop 3}\bigg\rangle_2\\ &=\bigg\langle {y,4\atop 4}\bigg\rangle_2\\ &=\frac 1{24}(y+2)(y+7)(x+8)(x+9) \end{align}$$

NB - for the outermost summation, if the upper limit is $y$, then the answer is $\frac 1{24}(y+1)(y+6)(y+7)(y+8)$.

---

Relationship with Binomial Coefficients

The above may also be represented using binomial coefficients, e.g.

$$\bigg\langle {x,p\atop p}\bigg\rangle_m=\frac {(x+m)}p\binom {x+mp+m-1}{p-1}$$

When $m=1$, the angle-bracket coefficient reduces to a binomial coefficent

$$\bigg\langle {x,p\atop p}\bigg\rangle_1=\binom {x+p}p$$ thus equation ($1$) reduces to the familiar $$\sum_{x=0}^y\binom {x+p}p=\binom{y+p+1}{p+1}$$

---

Addendum

A friend who is an excellent mathematician pointed out, with a neat combinatorial proof, that the final solution for (*) can be expressed as $$\binom {y+2p+2}{p+1}-\binom {y+2p+2}{p-1}$$

Using this insight we can actually derive that solution more directly for the case where $m=2$ as follows:

$$\begin{align} \sum_{x=0}^{y+1}\bigg\langle {x,p\atop p}\bigg\rangle_2 &=\sum_{x=0}^{y+1}\frac{x+2}p\binom {x+2p+1}{p-1}\\ &=\sum_{x=0}^{y+1}\binom {x+2p}p-\binom {x+2p}{p-2}\\ &=\sum_{x=0}^{y+1}\left[\binom {x+2p+1}{p+1}-\binom {x+2p}{p+1}\right]-\left[\binom {x+2p+1}{p-1}-\binom {x+2p}{p-1}\right]\\ &=\left[\binom {y+2p+2}{p+1}-\binom {2p}{p+1}\right]-\left[\binom {y+2p+2}{p-1}-\binom {2p}{p-1}\right]\\ &=\binom{y+2p+2}{p+1}-\binom {y+2p+2}{p-1} \qquad\qquad\scriptsize\text{as }\binom {2p}{p+1}=\binom {2p}{p-1}\\ &=\frac {y+2}{p+1}\binom {y+\overline{2p+1}+1}p\\ &=\bigg\langle {y,p+1\atop p+1}\bigg\rangle_2 \end{align}$$ which allows us to go to (*) directly.