# Stars and Bars Equivalence

My textbook says that "statement" executes ${10+(3-1)}\choose{3}$ 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)}\choose{r}$ 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 $***|*|*$

• Did the textbook give you ${10+(3-1)}\choose{3}$ or did it give you ${12\choose 3}$ and you changed it yourself? – Vee Hua Zhi Sep 10 '18 at 1:08
• It gave me ${10+3-1}\choose{3}$, without "(" and ")" – hioqobipb Sep 10 '18 at 2:04

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 $\mathrm{the\ number\ of\ permutations} = {9+(4-1)\choose (4-1)} = {12\choose 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

$$\binom{n+r-1}{n} = \binom{n+r-1}{r-1}. \ _\square$$

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

• But to use the formula, doesn't $a,b,c,d \ge 0$? This doesn't work when $a=10, b=0, c=0, d=0$ ($0 \not \ge 1$ as required by loop conditions) – hioqobipb Sep 9 '18 at 17:13
• I have edited my solution – Vee Hua Zhi Sep 10 '18 at 1:07
• The formula I gave is correct (from your formula, let $n = r$ and $k = n$). Then we have $\binom{r+n-1}{r} = \binom{n+(r-1)}{r}$ – hioqobipb Sep 10 '18 at 2:06
• The formula is NOT the same: My $r$ represents labelled urns and my $n$ represents indistinguishable balls, but yours is different. The change between $n$ and $r$ will make a huge difference. – Vee Hua Zhi Sep 11 '18 at 3:44
• You should read more to understand the reason behind stars and bars. brilliant.org/wiki/integer-equations-star-and-bars is a good wiki. – Vee Hua Zhi Sep 11 '18 at 3:45