¿Cuántos arreglos planares de círculos de $n$?

Question

Hay un conocido o de fórmula de recursión para el número de los distintos acuerdos de $n$ distintos círculos en un avión, donde dos arreglos son considerados como distintos, a menos que uno puede ser obtenido a partir de la otra mediante la traducción (deslizamiento) y/o la escala (expandir o contraer) algunos de los círculos , sin alterar el número de intersecciones en cualquier etapa de la traducción y/o escala. (¿Hay una mejor manera de expresar esto en términos topológicos?)

Para $n=1$ no es, por supuesto, sólo uno de tales acuerdos, y para $n=2$ hay $5$ de tales acuerdos:

Para $n=3$ hay al menos $49$ este tipo de acuerdos, como en la siguiente imagen (las correcciones o adiciones son bienvenidos):

EDIT: Gracias a @aproximada para descubrir la situada más a la derecha de los casos en las filas de $(1\ 0\ 0)$ y $(2\ 0\ 0)$ de la tabla anterior.

En estas fotos, he clasificado los arreglos según el número de intersecciones de tres tipos posibles. Cada intersección es

• puramente besos (todos los círculos en intersección no tienen la misma tangente),
• puramente cruce (todos los círculos en intersección hay diferentes tangentes), o
• mixto (ninguno de los anteriores).

Por lo tanto, la secuencia comienza de $1,5,49(?),...\ $ Las ideas acerca de una fórmula o de la recurrencia de la relación?

Answer 1

Tengo una solución parcial, excluyendo tangenciality, una cota superior para las configuraciones.

Básicamente se puede dividir a las relaciones entre los círculos en tres excluyendo tipos: inclusión, exclusión, intersección, es decir, un círculo puede cortar en dos puntos, puede ser completamente separado de los demás, o puede ser en una.

Si algún círculo está en el otro tanto de los círculos tienen la misma propiedad de exclusión respecto a un exterior del círculo, es decir, $(A\cap B=\emptyset)\de la tierra (C\subconjunto B)\implica C\cap a=\emptyset$.

Tangenciality puede ser pensado como un caso particular para la inclusión o la exclusión. Trate de ver los círculos como abrir sets.

Por lo que las propiedades de la inclusión o exclusión son "heredadas" por subconjuntos. Sé que una analogía en la teoría de números: divisibilidad y co-primalidad. Un número que puede ser co-prime de otros O puede dividir una a la otra (en una dirección) O ninguno de los dos, esto es análogo a la inclusión/exclusión/intersección de los de antes.

Así que tengo algún número N de círculos y quiero caracterizar cada círculo con un número único. Cada número estará compuesto por una combinación de factores.

Necesito, al menos, un primer factor completamente diferente para cada número para que yo pueda tener todos los números completamente diferentes una de la otra si quiero.

ACTUALIZACIÓN:

He descubierto que usted necesita, para algunos de instalación de los círculos, más que N factores. Usted no puede expresar todas las configuraciones posibles con sólo N factores, por ejemplo, en una cadena de círculos. Ejemplo: para 3 círculos, vinculadas como una cadena (un corte a los otros en una línea) se necesitan al menos $ab$, $bc$ y $cd$... por lo que necesita 4 factores de 3 círculos.

Me puede representar un válido el programa de instalación con un (0,1)-matriz, donde cada fila representa un círculo y cada columna representan la existencia de algún misma el primer factor. Para una instalación de círculos de S son todos válidos y no redundante cuadrado (0,1)-matriz de dimensión N, donde N es el número de círculos:

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

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

Una matriz S es válida si:

1. Tiene la diagonal llena de.
2. No hay una fila es idéntica a la de otros (los círculos son diferentes círculos).

Pero el gran problema aquí es la redundancia: una matriz es redundante si es equivalente a cualquier otro comedero cualquier número de filas y columnas de intercambio.

Y aquí es donde radica el gran problema para el recuento de estas matrices: las clases de equivalencia para un (0,1)-matriz bajo swaps de filas y columnas es similar a la gráfica de isomorfismo problema [1] [2].

Así tenemos, en mi opinión, dos de las principales estrategias de aquí: tratar de definir algunos obligado por estos número de matrices (y si es posible incluir tangenciality) o para evaluar a estos números comedero experimentación con algún programa estadístico como R.

En cualquier caso, parece que no existe una forma cerrada para evaluar el número de estas configuraciones con círculos.

P. S.: también puede representar a la instalación de los círculos con un grafo completo.

Answer 2

En el caso de kiss = 1, cruz = 0, mix = 0.

Has perdido Una interna y besar a la B, que es en el interior de C?

También no estoy seguro de que me cuente todos los tres besos en el mismo punto, como un beso, yo lo veo como tres. Pero tal vez usted tiene una buena razón para hacerlo a su manera?

---

Todos hemos besos casos? Yo creo que sí (una vez se añade el caso de k = 2, en B, en C). Aquí está mi intento de prueba.

Podemos colocar 3 no besar círculos en una esfera en sólo dos maneras. Colocamos Un círculo así como los formularios de ecuador. Entonces podemos (a) lugar B y C en el mismo lado o (b) en los lados opuestos de A. Estos son diferentes, como en el caso de que (a) cada círculo puede reducir a un punto sin cruzar otro, mientras que en el caso (b) no.

Para convertir la anterior a un avión que va de la punción de la esfera en el punto p. Voy a escribir a+B a decir a y B de Un beso.

Caso a: A = B = C
k = 1 : a+B + C : p en A, en C o en ninguno : 3 maneras
k = 2 : a+B+C : p en A, en B o en ninguno : 3 maneras
k = 3 : a+B+C+A : p en Una o en ninguno : 2 maneras

Caso b: A != B = C
k = 1 : a+B + C : p en B, en C, con[1] B o C : 4 maneras
k = 2 : C+a+B : p en C o en ninguno : 2 maneras
k = 3 : C+a+B+C : p en C o en ninguno : 2 maneras

16 maneras en todos.

[1] "p con B" significa que p está en el mismo hemisferio, como B (pero no en B).