# How many planar arrangements of $n$ circles?

Is there a known formula or recursion for the number of distinct arrangements of $n$ distinct circles in a plane, where two arrangements are regarded as distinct unless one can be obtained from the other by translating (sliding) and/or scaling (expanding or contracting) some of the circles without altering the number of intersections in any stage of the translation and/or scaling. (Is there a better way to express this in topological terms?)

For $n=1$ there is of course only one such arrangement, and for $n=2$ there are $5$ such arrangements:

For $n=3$ there are at least $49$ such arrangements, as in the following picture (corrections/additions are welcome):

EDIT: Thanks to @fuzzy for discovering the rightmost cases in rows $(1\ 0\ 0)$ and $(2\ 0\ 0)$ of the above table.

In these pictures, I've classified the arrangements according to the number of intersections of three possible types. Each intersection is either

• purely kissing (all circles intersecting there have the same tangent there),
• purely crossing (all circles intersecting there have different tangents there), or
• mixed (neither of the above).

Thus, the sequence begins $1,5,49(?),...\$ Any ideas about a formula or recurrence relation?

• Not very helpful, but almost certainly not. It's not in the OEIS. If you google it, you'll find www.math.tau.ac.il/~nogaa/PDFS/alps.pdf, which is a very rough draft about this. Rather, it is in the OEIS, but none of the entries there contain the word "circle". Commented May 31, 2015 at 21:26
• @EricTressler - Thanks for the link. I've only just glanced at that paper, but it seems to require all intersections to be what I've called "purely crossing" -- no tangent points. OEIS A250001 also forbids tangent points and "multiple intersections". Re OEIS, please note that my $f(3)$ might be greater than $45$, as I keep getting surprised by cases I hadn't thought of before. Commented May 31, 2015 at 22:45
• You can try a classification between 2 circles as: tangent, intersect, inner and outer... and after that you must see when some arrangements are impossible between more than 2 circles. You must classify the impossibilities, or at least this is an idea. Example: tangent circles just can intersect inner circles if they are inner too.
– user173262
Commented Jun 1, 2015 at 9:19
• @r.e.s.: Your $f(3)$ is definitely greater than $45$, assuming that there are no errors in your tabulation so far: the cases that you’ve tabulated actually sum to $47$. Commented Jun 1, 2015 at 20:15
• @wythagoras - That's not a case, because of the stated requirement of "$n$ distinct circles". Commented Jun 21, 2015 at 19:34

I have a partial solution excluding tangenciality, an upper bound for the setups.

Basically you can divide the relations between circles in three excluding types: inclusion, exclusion and intersection, i.e., a circle can cut other in two points, can be completely separated of other or it can be into some one.

If some circle is into the other both circles have the same property of exclusion respect to an exterior circle, i.e., $(A\cap B=\emptyset)\land (C\subset B)\implies C\cap A=\emptyset$.

Tangenciality can be thought as a particular case for inclusion or exclusion. Try to see the circles as open sets.

So the properties of inclusion or exclusion are "inherited" by subsets. I know an analogy on number theory: divisibility and co-primality. Some number can be co-prime of other OR can divide one to the other (in some direction) OR neither, this is analogous to inclusion/exclusion/intersection from before.

So I have some number N of circles and I want to characterize every circle with a number completely unique. Each number will be composed by some combination of factors.

I need, at least, one prime factor completely different for each number so I can have all numbers completely different one of each other if I want.

### UPDATE:

I discovered that you need, for some setup of circles, more than just N factors. You cant express all possible configurations with just N factors, by example in a chain of circles. Example: for 3 circles, linked like a chain (one cut other in a line) you need at least $ab$, $bc$ and $cd$... so you need 4 factors for 3 circles.

I can represent a valid setup with a (0,1)-matrix, where every row represent a circle and every column represent existence of some same prime factor. So a setup of circles S are all the valid and not redundant squared (0,1)-matrix with dimension N, where N is the number of circles:

$$\mathbf{S_{N\times N}} = \left( \begin{array}{rrrr} 1 & x & \cdots & x \\ x & 1 & \cdots & x \\ \vdots & \vdots & \ddots & \vdots \\ x & x & \cdots & 1 \end{array} \right).$$

where $x\in \{0, 1\}$

A matrix S is valid if:

1. It have the diagonal full of ones.
2. No one row is identical to other (the circles are different circles).

But the big problem here is redundancy: a matrix is redundant to other if it is equivalent to any other trough any number of rows and columns swap.

And here is where lies the big problem to count these matrices: the classes of equivalence for a (0,1)-matrix under swaps of rows and columns is analogous to the graph isomorphism problem [1] [2].

So we have, IMO, two main strategies here: try to define some bound for these number of matrices (and if possible include tangenciality) or just evaluate these numbers trough experimentation with some statistical program like R.

In any case it seems that doesnt exist a closed form to evaluate the number of these setups with circles.

P.S.: alternatively you can represent setup of circles with a complete graph.

In the case kiss = 1, cross = 0, mix = 0.

Have you missed A internal to and kissing B which is inside C?

Also I'm not sure I'd count all three kissing at the same point as one kiss, I see it as three. But perhaps you have good reason for doing it your way?

Have we all kissing cases? I think so (once we add case k = 2, A in B in C). Here's my attempt at a proof.

We can place 3 non-kissing circles on a sphere in only two ways. We place circle A so as it forms an equator. Then we can (a) place B and C on the same side or (b) on opposite sides of A. These are different as in case (a) each circle can shrink to a point without crossing another while in case (b) A cannot.

To convert the above to a plane we'll puncture the sphere at point p. I'll write A+B to mean A and B kiss.

Case a: A = B = C
k = 1 : A+B C : p in A, in C or in none : 3 ways
k = 2 : A+B+C : p in A, in B or in none : 3 ways
k = 3 : A+B+C+A : p in A or in none : 2 ways

Case b: A != B = C
k = 1 : A+B C : p in B, in C, with[1] B or with C : 4 ways
k = 2 : C+A+B : p in C or in none : 2 ways
k = 3 : C+A+B+C : p in C or in none : 2 ways

That's 16 ways in all.

[1] "p with B" means p is in the same hemisphere as B (but not in B).

• Good find! That's a case I did miss. I'll update the question to include it, making the total now $48$. Mostly just for display purposes, I chose to classify according to the three types of intersection point (rather than how many circles are intersecting there), but there are many alternative schemes. Commented Aug 22, 2015 at 1:43
• In the case kiss = 2, cross = 0, mix = 0. Missed A inside B inside C? Commented Aug 23, 2015 at 6:35
• Thanks! I've added your second discovery to the question, bringing the number of known cases to $49$. Commented Aug 23, 2015 at 15:11