Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  anon Jun 9 '12 at 5:05
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
This makes a lot of sense, thanks! –  Math_Illiterate Jun 9 '12 at 5:16
add comment

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.

share|improve this answer
    
This way took a little longer for me to see what was going on, but this answer is starting to make more sense as I look at it. Thanks for the response. –  Math_Illiterate Jun 9 '12 at 5:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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