I'm trying to understand this problem as exposed in William Feller's An introduction to probability theory and its applications:

(d) Flags of one or two colors. In example (1.f) it was shown that r flags can be displayed on n poles in N = n(n+ 1) ... (n+r-1) different ways. We now consider the same problem for flags of one color (considered indistinguishable). Numbering the flags of such a display yields exactly r! displays of r distinguishable flags and hence r flags of the same color can be displayed in N/r! ways.

I understand that a group of r distinguishable elements yield r! ordered samples of size r. But I do not understand why is it that r undistinguished flags can be displayed in N/r! ways. As I think about it, since they are supposed to be undistinguished, shouldn't there be only one way to order them? Does N/r! always yield 1? If so, why?

Many thanks


Put stickers with numbers $1$ to $r$ on the flags. Now after displaying the $r$ flags on $n$ poles, you can rearrange the stickers in $r!$ ways. That is, $r!$ different ways to display distinguishable flags correspond to $1$ way to display indistinguishable flags. Hence, if there are $N$ ways to display distinguishable flags, then there are $N/r!$ ways to display indistinguishable flags. The number $N/r!$ is not always $1$. For example if there are $n=2$ poles and $r=3$ indistinguishable flags there are $4$ ways to display them (indexed by the number of flags on the first pole). In fact displaying $r$ indistinguishable flags on $n$ poles counts the number of ordered number partitions of $r$ into $n$ non-negative parts, in the example with $n=2$, $r=3$ the displays correspond to the $4$ partitions $$ 0+3, 1+2, 2+1, 3+0. $$


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.