2
$\begingroup$

Alright, so I've been working through a couple combinatorics problems and I'm having trouble understanding the underlying reason for why a formula is written in a certain way. So here's the problem:

Suppose that r flags of different colors are to be displayed on n poles in a row. In how many ways can this be done?

Now this problem was solved by basically treating each flag like a divider and every time you place a flag, you create $n+1$ more choices of position for the next flag to placed which makes total sense. The final answer then is: $n(n+1)(n+2)...(n+r-1)$

What I'm confused about is how to know that $(n+r-1)$ always gives the final number of choices. I drew out a sample case and it does work out but I'm not sure why. This type of formula ending comes up a lot and I really want to understand how it works and when it applies.

  • 0
    You only create one more choice of the position for the next flag after each flag you put down. After putting down $k$ flags, you have $n+k$ choices for the next one. After you put down the $r-1$th flag, your final - $r$th - selection will come from $n+r-1$ choices.2012-06-09

2 Answers 2

2

You have $r$ flags. There are $n+0$ places to put the first flag.

After putting in the first flag, there are now $n+1$ places for the second flag.

After putting the second flag, there are now $n+2$ places for the third flag.

After putting the third flag, there are now $n+3$ places for the fourth flag.

You see a pattern? After putting the 10th flag, there will be $n+10$ places for the eleventh flag. After putting the 57th flag, there will be $n+57$ places for the $58$th flag.

So, just before you finish, you will have placed the $(r-1)$st flag; that means that there will be $n+(r-1)$ places where you can put the $r$th flag. And once you put the $r$th flag, you are done. There are no more choices to be made. So the last time you needed to count, you had $n+r-1$ ways.

So in total you had $n\times (n+1)\times\cdots \times (n+r-1)$ ways of doing it.

  • 0
    This makes a lot of sense, thanks!2012-06-09
1

Since you’re placing $r$ flags, there must be $r$ factors in the product $n(n+1)(n+2)\dots(n+r-1)$, so your question amounts to asking why an increasing list of $r$ consecutive integers that starts with $n$ must end with $n+r-1$. There are several ways to see this.

One is to subtract $n-1$ from each number in the list:

$\begin{array}{c} n&n+1&n+2&\dots&n+r-3&n+r-2&n+r-1\\ 1&2&3&\dots&r-2&r-1&r \end{array}$

The two lists have exactly the same number of items, and the lower list clearly has $r$ items, so the upper list must also have $r$ items.

Another expression of the same idea: your factors are the numbers $n+k$ such that $0\le k\le r-1$; as $k$ runs from $0$ through $r-1$, $k+1$ runs from $1$ through $r$, so $k$ must be running through exactly $r$ different numbers. Or you could say that $k$ runs through $r-1$ numbers in getting from $1$ through $r-1$, and in addition there’s $k=0$, for a total of $r$ values.

  • 0
    This way took a little longer $f$or me to see what was going on, but this answer is starting to make more sense as I look at it. Thanks $f$or the response.2012-06-09