1

I can draw $n$ circles on a straight line $OX$. I can either draw two circles some distance from each other (can't touch each other), or I can draw a circle inside another circle. Two arrangements of circles are the same iff there exists a bijection $f$ such that for given circles $C_1',...,C_n'$ and $C_1,...,C_n$:

1.If $C_i$ is inside $C_j$, then $C_i'$ is inside $C_j'$.

2.If $C_i$ is before $C_j$ (meaning it's center has smaller coordinate x then $C_j$), then $C_i'$ is before $C_j'$.

For example:

enter image description here

$1$ and $2$ are the same, but $3$ and $4$ are not.

Here's my solution:

We can clearly create a bijection between the arrangements of circles and strings of $0$ and $1$ of length n.

Given an arrangement of the circles we go from left to right an when we meet an outline of a circle we put $0$ when it's not inside another circle and $1$ when it is. Meaning $1$ and $2$ in the above picture is $010$, $3$ is $000$ and $4$ is $011$. We can create an arrangements of circles from the string similarly.

Therefore the number of different arrangements of $n$ circles is $2^{n-1}$ (since the first circle is outside, so it's $0$ by default.

Correct?

Arek Krawczyk
  • 2,114
  • $011$ can mean two things: Either it's picture number $4$, or it's two circles next to eachother, encircled by a bigger one. – Arthur Feb 06 '14 at 10:46
  • Heh, you're right :P I neglected the option of two circles being inside another for whatever reason. – Arek Krawczyk Feb 06 '14 at 10:50

2 Answers2

2

The answer you're looking for is the Catalan numbers. They're usually explained with nested parentheses instead of circles on a line, but it matters little.

Arthur
  • 199,419
2

What your describing can be interpreted as balanced brackets arrangements: we read $OX$ from left to right, with an open bracket if we start a new circle, and a close bracket if we close a circle.

E.g., your examples give $(())()$, $()()()$, $(())()$ again, and $((()))$, respectively.

These are counted by the Catalan numbers.

Rebecca J. Stones
  • 26,845