TITLE: Understanding Formula for Sampling without Ordering and without Replacement
QUESTION [1 upvotes]: 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.

REPLY [2 votes]: 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.

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 1, "question_id": 155911}