Arranging Bubbles

Recently, I attained quite some skill at blowing bubbles. At first I would blow bubbles like this:

But then things started getting strange:

After a while, I was blowing some pretty weird bubbles:

After blowing hundreds, maybe even thousands of such bubbles, my forehead suddenly wrinkled with the question: Given n bubbles, how many different ways can you arrange them? For example if n = 1, there is only 1 arrangement. If n = 2, there are 2 arrangements. If n = 3, there are 4 arrangements. If n = 4, there are 9 arrangements (I think, but not completely sure).

Here are the 9 arrangements of 4 bubbles:

For some reason, my wrinkled forehead doesn't have quite enough neurons within it to figure out the answer to my question. Can someone else try wrinkling their forehead to see if they might be able to get an answer?

Given n bubbles, how many different ways can you arrange them?

Solution 1:

As Arthur points out in a comment, this is A000081 in the OEIS, "Number of unlabeled rooted trees with $n$ nodes . . . Also, number of ways of arranging $n-1$ nonoverlapping circles".

Selected formulas from the linked page:

Generating function $A(x) = \sum\limits_{n\ge1} a(n) x^n$ satisfies $$A(x) = x\exp\left(A(x)+\frac12A(x^2)+\frac13A(x^3)+\frac14A(x^4)+\cdots\right)$$ [Polya]

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

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

Asymptotically $c d^n n^{-3/2}$, where $c = 0.439924\ldots$ and $d = 2.955765\ldots$ [Polya; Knuth, section 7.2.1.6].

Reminder: $a(n)$ is the number of ways of arranging $n-1$ circles, not $n$ circles. So we have $a(5)=9$.

Solution 2:

EDIT: A while ago I wrote the part of this answer that's below the line. I realized it was unnecessarily complicated. Using a similar approach, I was able to get this expression:

$$ b(n) = \sum_{( a_1^{r_1} \, \ldots \, a_\ell^{r_\ell} ) \, \vdash \, n} \left( \prod_{i=1}^{\ell} \left(\!\!\binom{b(a_i - 1)}{r_i}\!\!\right) \right) $$

In my original answer I used some creative notation for partitions. The notation above is more standard.

Let $b(n)$ be the number of arrangements of n bubbles, and let $b_k(n)$ be the number of arrangements of n bubbles such that there are exactly k bubbles not enclosed within another bubble. Bubbles not enclosed within another bubble are called top-level bubbles

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

Let $P_k(n)$ be the set of partitions of n into k parts.

Let $b_k \langle p \rangle$, for a partition p, be defined as the number of arrangements of bubbles such that:

1. There are k top-level bubbles
2. There exists a one-to-one mapping between non-empty top-level bubbles and parts of p, where the number of bubbles contained within each of the former is equal to the corresponding part.

Note that $b_j \langle p \rangle = b_k \langle p \rangle$ when j and k are greater than or equal to the number of parts of p. Define $b \langle p \rangle$ as this unique value.

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

A partition of n will be written in the form $a^i, b^j, c^k, \ldots$ where all of a, b, c, etc. are distinct, and $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}$$

The above equations form a recurrence relation for $b(n)$.