2 added 278 characters in body

Consider the graph obtained by assigning to each region a vertex, and two vertices being joined by an edge iff the two regions are neighbors. It is easy to see that this is a tree, with the empty circles as terminal vertices: once you crossed a circle, the only way to return to the same region is by the same edge.

The tree isomorphism corresponds to the equivalence of arrangements of circles.

So the cardinality of $\mathcal A_n$ is the same as for the unlabeled trees. In the same wiki reference is mentioned he asymptotic estimate given by Otter (1948). For the cardinality of $\mathcal A_n$ is no known formula.

For the $\mathcal S_n$, there are only two ways to color a tree so that each edge connects two vertices of opposite colors. They may be not distinct (i.e. may be selfdual), since it is possible to have a tree isomorphism automorphism which switches the colors. The asymptotics is similar to the uncolored case, because there are only one or two distinct colorings of the same tree.

The notion of randomness for trees depends on the purpose.

The answers are partial, mainly because the answers to the corresponding questions for the trees are partial known, but I hope that the connection with trees may help, although these interesting questions remain difficult for the trees too.

1

Consider the graph obtained by assigning to each region a vertex, and two vertices being joined by an edge iff the two regions are neighbors. It is easy to see that this is a tree, with the empty circles as terminal vertices: once you crossed a circle, the only way to return to the same region is by the same edge.

The tree isomorphism corresponds to the equivalence of arrangements of circles.

So the cardinality of $\mathcal A_n$ is the same as for the unlabeled trees.

For the $\mathcal S_n$, there are only two ways to color a tree so that each edge connects two vertices of opposite colors. They may be not distinct (i.e. may be selfdual), since it is possible to have a tree isomorphism which switches the colors. The asymptotics is similar to the uncolored case, because there are only one or two distinct colorings of the same tree.

The answers are partial, but I hope that the connection with trees may help, although these interesting questions remain difficult for the trees too.