Stars and Bars Equivalence

combinatorics

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

Best Answer

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

Related Question