On the number of ways to draw kissing circles

So I was watching Numberphile with Neil Sloane of OEIS fame on the number of ways to make circles intersect. During the intro, he explicitly forbid kissing (touching, tangent) circles. This made me think about the number of ways to draw circles that must all kiss, where intersections are not allowed. Kind of the dual problem, if you will. So in a nutshell:

• Circles in the affine plane can be of any finite size
• Circles must kiss at least one other (no separate circles, all must be connected)
• Solutions that can be transformed into each other through mirroring, rotation, stretching, moving circles without making new tangent points, are considered the same

For $n=2$ circles there are two ways: touching on the outside, and touching on the inside of the larger circle.

For $n=3$ I believe the answer is 9. Try it, should be easy.

For $n=4$ I started drawing and came up with, so far, and with help from you guys, 38, 39, 42, 43, 44, 45, 47, 44 ways. The colored dots represent the number of kissing circles at the tangent points.

Questions:

• Did I miss any? I'm sure I did.
• Do I have inadvertent duplicates?
• Does an integer sequence exist, or even a formula mapping $n = 2, 3, 4, ...$ to $2, 9, 44, ...$?

Solution 1:

Let's be a little systemic about drawing these.

For $n=4$, there are 9 hierarchies of circles (I think this is from OEIS A000081).

1. (((()))) the circles are all nested inside each other.

There are four of these: the differences come from whether the points of tangency coincide or not. You have them labelled as #26, #28, #29, and #30 in the diagram when I started writing this.

2. ((()())) two innermost circles surrounded by a nested pair.

There are six of these: the two innermost circles can either 1. each touch only their parent, 2. touch each other but only one touch the parent, or 3. touch each other and both touch the parent, and then the point of tangency with the grandparent can be involved or not. Of these, only one is included in your diagram, as #34.

3. ((())()) two children, one grandchild.

I'll call the child with its own child A, and the child without its own child B. The children can touch just the parent (and the grandchild can touch or not the outer circle); A can touch only B and not parent (and the grandchild can touch or not B); B can touch only A and not parent (and the grandchild can touch B, the outer circle, or neither); A and B can touch both each other and the parent (and the grandchild can touch B, the outer circle, or neither), for a total of 10. Of these, you have five: #22, #23, #31, #32, and #33.

4. ((()))() one with child and grandchild, one empty.

There are four of these: the grandchild can touch or not the grandparent, and the child can touch or not its uncle. Of these you have two, #27 and #45.

5. (()()()) one parent with three children.

The three children can be in four layouts: they can not touch at all; there can be one pair and one lonely one; there can be three in a line; there can be all three in a triangle. This leads to eleven in the whole class: the three independent siblings can all touch parent #16, the pair can both touch #13 or only one can #35, the line can touch once on the end or in the middle (you have neither) or twice on both ends #12 or end and middle #25 or three times #19, the triangle can touch once (not present) twice (double counted #15 and #24) or three times (#11)

6. (()())() one with two children, one empty.

This lineup is basically the same as type 2; the only difference is that the "outermost circle" in 2 has become an uncle instead of a grandparent. You have five of these #14 #17 #18 #39 #43, and have double counted two as #20 and #21 - you're missing the uncle-tangent counterpart to #14.

7. (())(()) two with one child each.

There's only three of these: the question is how many children touch their uncles. It could be zero #38, one #37, or two #36.

8. (())()() one with one child, two empty.

Geometry finally comes into play! The three outer circles can be in a line or triangle. If they're in a line, the child can be in one of the ends, or in the middle, and it can touch or not an uncle #6, #7, #8, #44; if they're in a triangle, the child can touch one of the uncles #10, or outside the triangle formed by the uncles #9, or inside that triangle (not present)

9. ()()()() four empties.

I think you actually have all of these: there's line #5, triangle plus tail #1, rhombus #2, square #3, star #40, and then there are three that are a triangle with circle in the middle that touches one #42 two #41 or three #4 of the outer circles.

So in total you appear to have (in the diagram when I started writing this answer double counted three (#20 is the same as #18, #21 is the same as #17, and #24 is the same as #15), and missed sixteen, for a grand total of 58 that I can count.

Solution 2:

Thanks to @DanUznanski here is the complete solution with 58 ways, using his sibling relation to group diagrams.

Solution 3:

This is not a complete answer, but a look at ways of describing these drawings and forming larger drawings from smaller ones.

Slightly abusing notation, let's say $A \sim B$ if circles $A$ and $B$ touch externally, or $A < B$ if circle $A$ is inside and tangent to circle $B$. Square brackets around a "formula" of three or more circles mean that they all meet at a common tangent point; otherwise, each relation symbol is a tangent point for only two circles.

Then for $n=2$, the two ways are $C_1 \sim C_2$ and $C_1 < C_2$.

For $n=3$, there are $9$ ways:

• $[C_1 < C_2 < C_3]$
• $C_1 < C_2 < C_3$
• $C_1 \sim C_2 < C_3$
• $C_1 < C_3$ and $C_2 < C_3$
• $C_1 \sim C_2 < C_3$ and $C_1 < C_3$
• $[C_1 < C_2 \sim C_3]$
• $C_1 < C_2 \sim C_3$
• $C_1 \sim C_2 \sim C_3$
• $C_1 \sim C_2 \sim C_3 \sim C_1$

Note for any connected diagram of this sort with three or more circles, it's always possible to remove some circle with empty interior so that the remaining diagram is still connected. Proof:

Given a circle $C$, call its "inner depth" the largest integer $n$ such that there is a sequence of circles $C_i$ with $C_1 < C_2 < \cdots < C_n < C$. A circle with empty interior has inner depth zero.

If all circles in a diagram of at least three circles have inner depth zero, consider the graph defined by identifying the circles as vertices, with edges between vertices where the circles are tangent. A finite graph with at least two vertices always has at least two vertices which are either a leaf or within a graph cycle, and removing such a vertex from the graph leaves the remainder of the graph connected. So a corresponding circle can be removed and leave the remaining diagram connected, and in this case all the circles have empty interiors.

If not all circles in a diagram of at least three circles have inner depth zero, then there is at least one circle $C_0$ with inner depth $1$. Consider the graph whose vertices are $C_0$ and the circles it contains. There is at least one contained circle, and all these contained circles have inner depth $0$. This graph again has at least two vertices which can be removed without disconnecting the graph. Remove a circle which is not $C_0$ from the diagram. This circle has inner depth zero and empty interior. Since the graph remains connected, all the other remaining circles contained in $C_0$ are connected to $C_0$. All the diagram's circles outside $C_0$ are connected to $C_0$ via paths entirely outside $C_0$ (up to a tangent point), and those paths have not been affected. So the diagram is still connected.

The other way around, then, when looking for diagrams of $n+1$ circles, we can simplify by considering where to add a circle to a diagram of $n$ circles so that the added circle does not enclose any other circle. In the above list of diagrams for $n=3$, the first $5$ can be found from adding the minimal $C_1$ to a diagram $C_2 < C_3$, the next $2$ from adding to a diagram $C_1 < C_2$ OR $C_2 \sim C_3$, and the last $2$ from adding to a diagram $C_2 \sim C_3$.

Without looking back at the OP's drawings, I came up with 52 drawings for $n=4$. They're ordered by the nature of the diagram for $C_2,C_3,C_4$. A parenthesized color code matches the OP's convention of "r" for a point with two circles, "g" a point with three, or "b" a point with 4. A number after that indicates the equivalent drawing in the OP, if any.

• (b 45): $[C_1 < C_2 < C_3 < C_4]$
• (gr 37): $[C_2 < C_3 < C_4]$ and $C_1 < C_2$
• (gr): $[C_2 < C_3 < C_4]$ and $C_1 \sim C_2$
• (grr 43): $[C_2 < C_3 < C_4]$ and $C_2 \sim C_1 < C_3$
• (gr): $[C_2 < C_3 < C_4]$ and $C_1 < C_3$
• (gr 36): $[C_2 < C_3 < C_4]$ and $C_1 \sim C_3$
• (grr 41): $[C_2 < C_3 < C_4]$ and $C_3 \sim C_1 < C_4$
• (gr 38): $[C_2 < C_3 < C_4]$ and $C_1 < C_4$
• (b 46): $[C_2 < C_3 < C_4 \sim C_1]$
• (gr): $[C_2 < C_3 < C_4]$ and $C_1 \sim C_4$
• (gr 35): $[C_1 < C_2 < C_3]$ and $C_3 < C_4$
• (rrr 5): $C_1 < C_2 < C_3 < C_4$
• (rrr 9): $C_1 \sim C_2 < C_3 < C_4$
• (rrrr): $C_2 < C_3 < C_4$ and $C_2 \sim C_1 < C_3$
• (rrr): $C_2 < C_3 < C_4$ and $C_1 < C_3$
• (gr): $[C_2 < C_3 \sim C_1]$ and $C_3 < C_4$
• (grr 44): $[C_2 < C_3 \sim C_1]$ and $C_1 < C_4$ and $C_3 < C_4$
• (rrr): $C_2 < C_3 < C_4$ and $C_1 \sim C_3$
• (rrrr 19): $C_2 < C_3 < C_4$ and $C_3 \sim C_1 < C_4$
• (rrr 4): $C_2 < C_3 < C_4$ and $C_1 < C_4$
• $C_2 < C_3$ and $[C_3 < C_4 \sim C_1]$
• (rrr 12): $C_2 < C_3 < C_4 \sim C_1$
• (rrrr 15): $C_4 > C_2 \sim C_3 < C_4 \sim C_1$
• (grr 39=40): $[C_3 < C_4 \sim C_1]$ and $C_3 \sim C_2 < C_4$
• (rrrrrr 30): $C_1 \sim C_2 \sim C_3 \sim C_1$ and $C_1 < C_4$ and $C_2 < C_4$ and $C_3 < C_4$
• (rrrrr 26): $C_1 \sim C_2 \sim C_3 \sim C_1$ and $C_2 < C_4$ and $C_3 < C_4$
• (rrrrr 25): $C_1 \sim C_2 \sim C_3$ and $C_1 < C_4$ and $C_2 < C_4$ and $C_3 < C_4$
• (rrrr 22): $C_1 \sim C_2 \sim C_3$ and $C_2 < C_4$ and $C_3 < C_4$
• (rrrr 20): $C_4 > C_2 \sim C_3 < C_4$ and $C_1 < C_4$
• (gr): $[C_1 < C_2 \sim C_3]$ and $C_3 < C_4$
• (rrr): $C_1 < C_2 \sim C_3 < C_4$
• (rrr): $C_1 \sim C_2 \sim C_3 < C_4$
• (rrrr 17): $C_4 > C_1 \sim C_2 \sim C_3 < C_4$
• (rrrr): $C_3 \sim C_1 \sim C_2 \sim C_3 < C_4$
• (rrr 7): $C_1 < C_4 > C_3 \sim C_2$
• (gr): $[C_3 < C_4 \sim C_1]$ and $C_2 \sim C_3$
• (rrr 11): $C_2 \sim C_3 < C_4 \sim C_1$
• (rrr 6): $C_1 < C_4$ and $C_2 < C_4$ and $C_3 < C_4$
• (gr 34): $[C_3 < C_4 \sim C_1]$ and $C_2 < C_4$
• (rrr 13): $C_2 < C_4$ and $C_3 < C_4$ and $C_1 \sim C_4$
• (grr 42): $[C_2 < C_3 \sim C_4]$ and $C_3 \sim C_1 \sim C_4$
• (gr 32): $[C_2 < C_3 \sim C_4]$ and $C_1 \sim C_3$
• (gr 33): $[C_2 < C_3 \sim C_4]$ and $C_1 \sim C_4$
• (rrrr 21): $C_1 \sim C_3 \sim C_4 \sim C_1$ and $C_2 < C_3$
• (rrr 8): $C_1 \sim C_3 \sim C_4$ and $C_2 < C_3$
• (rrr 2): $C_3 \sim C_4 \sim C_1$ and $C_2 < C_3$
• (rrr 1): $C_1 \sim C_2 \sim C_3 \sim C_4$
• (rrr 10): $C_2 \sim C_3 \sim C_4$ and $C_1 \sim C_3$
• (rrrr 14): $C_1 \sim C_2 \sim C_3 \sim C_4 \sim C_1$
• (rrrr 18 (and 23)): $C_2 \sim C_3 \sim C_4 \sim C_2$ and $C_1 \sim C_4$
• (rrrrr 24 (and 27)): $C_2 \sim C_3 \sim C_4 \sim C_2$ and $C_1 \sim C_3$ and $C_1 \sim C_4$
• (rrrrrr 29): $C_2 \sim C_3 \sim C_4 \sim C_2$ and $C_1 \sim C_2$ and $C_1 \sim C_3$ and $C_1 \sim C_4$

Comparing to the OP's drawings, I see that my descriptions for numbers 18 and 24 also describe 23 and 27, respectively. Among the OP's drawings, I also missed

• (rrr 3): $C_2 < C_3 \sim C_4 > C_1$
• (gr 31): $[C_2 < C_3 \sim C_4]$ and $C_1 < C_4$
• (b 47): $[C_1 < C_2 \sim C_3 > C_4]$

So this is at least 57 drawings for $n=4$. I think the 58th mentioned by @DanUznanski's answer is the variation of (rrrr 21: $C_1 \sim C_3 \sim C_4 \sim C_1$ and $C_2 < C_3$) where $C_2$ touches $C_3$ inside the triangle formed by the other three tangent points.

I don't think this notation is sufficient alone for higher numbers. With a loss of symmetry, it can matter which order the tangent points come in for a circle with three or more tangent points. We already see this sort of trouble for $n=4$ with pairs $18, 23$ and $24, 27$.