La Organización De Las Burbujas

Question

Recientemente, he logrado bastante habilidad en la aparición de burbujas. En primer lugar me gustaría burbujas de golpe como este:

Pero luego las cosas empezaron extraño:

Después de un tiempo, yo estaba soplando algunas bastante extrañas burbujas:

Después de soplar cientos, tal vez incluso miles de burbujas, mi frente, de repente arrugada con la pregunta: Dado n burbujas, de cuántas maneras diferentes se puede arreglar? Por ejemplo, si n = 1, sólo hay 1 arreglo. Si n = 2, hay 2 arreglos. Si n = 3, 4 arreglos. Si n = 4, hay 9 arreglos (creo, pero no totalmente seguro).

Aquí están los 9 arreglos de 4 burbujas:

Por alguna razón, mi arrugada la frente no tiene suficiente neuronas dentro de él, para averiguar la respuesta a mi pregunta. Puede alguien tratar las arrugas de su frente para ver si podría ser capaz de obtener una respuesta?

N dado burbujas, de cuántas maneras diferentes se puede arreglar?

Answer 1

Como Arthur señala en un comentario, esto es A000081 en la OEIS, "Número de etiqueta árboles de raíces con $n$ nodos . . . También, el número de maneras de organizar $n-1$ superpuestas de los círculos".

Seleccionado fórmulas de la página enlazada:

La generación de la función $A(x) = \sum\limits_{n\ge1} a(n) x^n$ satisface $$A(x) = x\exp\left(A(x)+\frac12A(x^2)+\frac13A(x^3)+\frac14A(x^4)+\cdots\right)$$ [Poli]

También se $$A(x) = \frac x{\prod\limits_{n\ge1} (1-x^n)^{a(n)}}.$$

Recurrencia: $$a(n+1) = \frac1n \sum_{k=1}^n \Bigl( \sum_{d|k} da(d) \Bigr) a(n-k+1).$$

Asintóticamente $c d^n n^{-3/2}$ donde $c = 0.439924\ldots$ $d = 2.955765\ldots$ [Polya; Knuth, sección 7.2.1.6].

Recordatorio: $a(n)$ es el número de maneras de organizar $n-1$ círculos, no $n$ círculos. Así que tenemos $a(5)=9$.

Answer 2

Deje $b(n)$ el número de arreglos de n burbujas, y deje $b_k(n)$ el número de arreglos de n burbujas que hay exactamente k de burbujas no encerrada dentro de otra burbuja. Las burbujas no encerrada dentro de otra burbuja son llamados de nivel superior burbujas

$$b(n) = 1 + \sum_{i=1}^{n-1} b_i(n)$$

Deje $P_k(n)$ el conjunto de particiones de n en k partes.

Deje $b_k \langle p \rangle$, para una partición p, se define como el número de acuerdos de burbujas que:

1. Hay k de nivel superior burbujas
2. Existe un uno-a-uno el mapeo entre los no-vacío de nivel superior burbujas y partes de p, donde el número de burbujas contenidas dentro de cada uno de los ex es igual a la parte correspondiente.

Tenga en cuenta que $b_j \langle p \rangle = b_k \langle p \rangle$ cuando j y k son mayores que o igual al número de elementos de p. Definir $b \langle p \rangle$ este valor único.

$$b_k(n) = \sum_{i=1}^k \sum_{p \in P_i(n-k)} b \langle p \rangle$$

Una partición de n va a ser escrito en la forma $a^i, b^j, c^k, \ldots$ donde todos los de a, b, c, etc. son distintos, y $ai + bj + ck + \ldots = n$.

$$b \langle a^i,b^j,c^k, \ldots \rangle = b \langle a^i \rangle \cdot b \langle b^j \rangle \cdot b \langle c^k\rangle\cdot\ldots$$

$$b \langle a^i \rangle = \left(\!\!\binom{b(a)}{i}\!\!\right) = \binom{b(a)+i-1}{i}$$

Las ecuaciones anteriores formar una relación de recurrencia para $b(n)$.