Circular orientation of $n$ identical red balls and $n + 1$ identical black balls

Question

I encountered a question as follows:

In how many ways may $n$ identical red balls and $n + 1$ identical black balls be arranged in a circle (This number is called a Catalan number)?

While trying to analyze it

$1^{st}$ I considered linear arrangement of $\underline {n\ \textit{identical red balls}}$ and $\underline {n\ \textit{identical black balls}}$. It's same as writing $n$ 'R's & $n$ 'B's in a row. So from those $2n$ positions; the task is to choose $n$ positions to put the 'R's (or the 'B's) in. This can be done in $2n\choose n$ ways.

E.g : for $n = 2$ the arrangements are $(RRBB), (BBRR), (RBRB), (BRBR), (RBBR)\ \&\ (BRRB)$

Here Catalan Number [which would be $\frac{1}{n+1}\times{2n\choose n}$]comes into picture if there $\underline {doesn't\ exist}$ any sequence where the number of 'R's (or 'B's) $\underline {in\ any\ prefix\ of\ the\ sequence}$ is greater than that of 'B's (or 'R's).

Please correct me if I'm wrong.

Now for the original problem we are given a $\underline{circular\ arrangement}$ & $\underline{1\ extra\ black\ ball}$.

So taking that extra ball as fixed reference in circular orientation, we again have the same question of finding $n$ places out of $2n$ places to put the red (or black) balls in. This according to me is again results into $2n \choose n$, with only difference being the equivalent clock-wise & counter clock-wise orientation. So I've come up with $\frac{1}{2}\times {2n\choose n}$.

I've not been able to understand why in the question they've mentioned the answer to be the Catalan Number i.e $\frac{1}{n+1}\times{2n\choose n}$.

Can anyone help me figure out what I'm missing ?

Answer 1

The simple explanation: In a linear arrangement of $n$ red and $n+1$ black balls, there are ${2n+1 \choose n} = \frac{(2n+1)!}{n!(n+1)!}$ possibilities. Now consider put this line into a circle: $2n+1$ line patterns will produce the same circle since the line can start at any of the $2n+1$ points of the circle, so there are $\frac{1}{2n+1}{2n+1 \choose n} = \frac{(2n)!}{n!(n+1)!} = \frac{1}{n+1}{2n \choose n}$ possible circles.

In fact the difficult part is showing that at least (and so exactly) $2n+1$ different lines can be produced from any circle: the equivalent statement for $2n$ lines would not always be true of circles with $n$ red and $n$ black balls, for example where they interleaved perfectly.

You also need to take care to maintain direction around the circle and along the line: this is the difference between a necklace and a bracelet.

Answer 2

This problem may be solved using the Polya enumeration theorem. We have $2n+1$ slots and distribute red and black into these slots. We are interested in the coefficient of $R^n B^{n+1}$ of the corresponding generating function.

Now if no flips are permitted the group that acts on the slots is the cyclic group of order $2n+1$ with cycle index $$Z(C_{2n+1}) = \frac{1}{2n+1} \sum_{d|2n+1} \varphi(d) a_d^{(2n+1)/d}.$$ Thus we need to evaluate the quantity $$[R^n B^{n+1}] \frac{1}{2n+1} \sum_{d|2n+1} \varphi(d) (R^d+B^d)^{(2n+1)/d}.$$ Now consider the term $(R^d+B^d)^{n/d}.$ The exponents of all powers of $R$ that appear are multiples of $d$ as are those of the powers of $B.$ Hence only those divisors $d$ of $2n+1$ contribute that also divide $n$ and $n+1$. This eliminates everything except $d=1,$ and our sum becomes $$[R^n B^{n+1}] \frac{1}{2n+1} (R+B)^{2n+1} = \frac{1}{2n+1} {2n+1\choose n}\\ = \frac{1}{2n+1} \frac{(2n+1)!}{n!(n+1)!} = \frac{(2n)!}{n!(n+1)!} = \frac{1}{n+1} {2n \choose n},$$ the Catalan numbers as claimed.