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

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 ?

• Or can I not take a ball as fixed reference from a set of identical balls? If not, then what approach should I take ? Commented Oct 4, 2013 at 14:47

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.
• Cool! Meanwhile I've come up with a different explanation. Suppose $x$ arrangements are possible. Now had all those $n$ red balls been distinct, for each such arrangement they would've been permuted in $n!$ ways. Similarly for each such $x\times n!$ arrangements the other $n+1$ black balls would've been permuted in $(n+1)!$ ways. So, for all these different balls, there are total $x\times n!\times (n+1)!$ orientations. This is equal to total circular permutations of $(2n+1)$ distinct balls which is $(2n)!$. So, $x\times n!\times (n+1)! = (2n)!$ and $x = \frac{1}{n+1}\times {2n\choose n}$ Commented Oct 4, 2013 at 16:59
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.