19
$\begingroup$

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

But then things started getting strange:

enter image description here

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

enter image description here

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:
enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

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?

$\endgroup$
4
  • 7
    $\begingroup$ See the OEIS. $\endgroup$
    – Arthur
    Commented Jan 12, 2017 at 6:23
  • 4
    $\begingroup$ @DavidQuinn: Not quite because the parentheses would distinguish the order, so ()(()()) is different from (()())() but the circles find it the same. The parentheses give the Catalan numbers $\endgroup$ Commented Jan 12, 2017 at 6:40
  • 2
    $\begingroup$ FWIW, this is now a PCG challenge. $\endgroup$
    – PM 2Ring
    Commented Jan 13, 2017 at 10:07
  • 1
    $\begingroup$ To add to @Arthur's comment, an arrangement of $n$ bubbles corresponds to an unlabeled rooted tree on $n+1$ nodes; the root is the region outside all the bubbles, the other regions correspond to bubbles, and arcs in the tree represent containment. $\endgroup$
    – Tad
    Commented Jan 14, 2017 at 3:26

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Verified in Java that this matches A000081 up to 24 bubbles before my integers overflowed. Unfortunately my recurrence relies on the calculation of partitions, which is a lot more complicated than the recurrence based on divisors given in the other answer. But at least I can see the connection between bubbles and partitions; I have no idea where divisors come into play. $\endgroup$
    – Axe
    Commented Jan 15, 2017 at 0:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .