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?

Solution 1:

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.

Solution 2:

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).