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.

How many ways are there to arrange $m$ distinct flags on a row of $r$ flagpoles? The order of the flags on the flagpoles (from top to bottom) matters.

My argument is: I have $mr$ points and I have to decide where to put the $m$ flags, so the result should be $\binom{mr}{m}$. But the second point of the exercise let me think that the right answer might be $m(m+1)\cdots(m+r-1)$ or $r(r+1)\cdots(r+m-1)$.

Is my argument wrong? And if it is, where is the mistake?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

What I would do is introduce the flags to the layout in a fixed order (say, alphabetical by the official French name of the country). For each flag, I have the option of either placing at the top of one of the $r$ flagpoles, or placing it immediately below one of the flags I have already positioned. The total number of different choices I can make is then $$r(r+1)(r+2)\cdots(r+m-1) = \frac{(r+m-1)!}{(r-1)!}$$

So if I'm right, then your argument must be wrong. But it is impossible to see what your mistake is when you don't present the reasoning we're asked to find mistakes in, but only its bare (and wrong) conclusion.

share|improve this answer
    
It seems you are right. My reasoning was: I have $mr$ position for the $m$ flags, some of this position will be empty, I have to choose $m$ of those positions that are not-empty. And the result is $\binom{mr}{m}$, where is the mistake? –  Alex M Sep 5 '11 at 21:58
    
Two problems with that. First, knowing which positions are non-empty will not tell you which flags go where. Second, the empty positions are not visible in the final result -- for example, you don't want to count "Spain at the bottom of pole 1, the rest of pole 1 empty" as different from "Spain at the top of pole 1, the rest of pole 1 empty". –  Henning Makholm Sep 5 '11 at 22:02
    
Why do you have $mr$ positions? –  gary Sep 5 '11 at 22:08
    
ok you're right, I was wrong –  Alex M Sep 5 '11 at 22:11
    
A very good way to explain, particularly the choice of French names. –  André Nicolas Sep 5 '11 at 22:28

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.