2
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – hioqobipb Sep 9 '18 at 17:13
  • $\begingroup$ I have edited my solution $\endgroup$ – Vee Hua Zhi Sep 10 '18 at 1:07
  • $\begingroup$ 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}$ $\endgroup$ – hioqobipb Sep 10 '18 at 2:06
  • $\begingroup$ 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. $\endgroup$ – Vee Hua Zhi Sep 11 '18 at 3:44
  • $\begingroup$ You should read more to understand the reason behind stars and bars. brilliant.org/wiki/integer-equations-star-and-bars is a good wiki. $\endgroup$ – Vee Hua Zhi Sep 11 '18 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.