Vtyjkyuk

My textbook says that "statement" executes $10+(3-1)choose3$ times for the following pseudocode without giving any details on why (I know that $n=10$ and $r=3$). I have verified this to be correct with a simple script.

for i = 1 up to 10
 for j = 1 up to i
 for k = 1 up to j
 statement

How can I visualize how many times "statement" is run through the use of stars and bars or any other combinatorial argument?

This is not the same as this or this - they are only calculating how many times it is run without using stars and bars.

Stars and Bars:

If there are $n$ identical objects and $r$ distinct containers, then there are $n + (r-1)chooser$ possibilities to distribute the objects.

If there are $5$ objects and $3$ containers, then $3$ objects in container 1, $1$ object in container 2 and $1$ object in container 3 can be represented with stars and bars by $***|*|*$

Let $10 =a+b+c+d+1, i=b+c+d+1, j=c+d+1, k=d+1$.

where $a,b,c,d$ each represents the 'stars' in every container:

For example in $(∗∗∗|∗|∗∗|∗∗∗)$ $a=3, b=1, c=2, d=3$

Then $mathrmthe number of permutations = 9+(4-1)choose (4-1) = 12choose 3 $which apparently is the same as the given one in the textbook.

Then $i$ will be any number from $1$ to $10$, $j$ will be any number from $1$ to $i$, and $k$ will be any number from $1$ to $j$.

*Your formula for stars and bars is not correct.

Source: Brilliant.org

The number of ways to place $n$ indistinguishable balls into $r$ labelled urns is

$$ binomn+r-1n = binomn+r-1r-1. _square $$

---

which is not the same as the formula you have given, i.e. $n + (r-1)chooser$