Welcome to NRICH.

 
Bubbles - an old investigation
By Miles Berry (T474) on Monday, December 13, 1999 - 09:46 pm:

My year 7 class are working on an old investigation I came across:
We're interested in the number of topologically distinct arrangements B(n) of a given number of 'bubbles' n, given bubbles may be either inside other bubbles or alongside them and no bubbles may touch: eg, for 3 bubbles, 4 essentially distinct arrangements exist:
()()(), (())(), (()()), ((()))
We have established that B(n)>=2B(n-1).
I wonder if anyone can take this further?
A proper algebraic result seems a long way away, indeed I wonder if one exists at all?
Thanks in anticipation,
Miles Berry,
Head of Maths,
Christ Church Cathedral School,
Oxford.

By Alex Barnard (Agb21) on Tuesday, December 14, 1999 - 11:11 am:

Okay... I've not see the problem with the 'topologically distinct' restriction but I do know what happens when this is dropped:

It is a very famous (once you've done maths for years!) sequence of numbers and it comes up in many different guises. The one I know of is the way that you draw the bubbles with (). If you look at the examples you have then you see they are of the correct syntax for parentheses - ie. they match up in pairs in the way you want parentheses to match. The other common one is to do with voting. Imagine how many ways it is possible to cast 2n votes for 2 candidates such that the first one is never behind in the count and the result is a tie. In your diagrams take '(' to be a vote for candidate 1 and ')' a vote for candidate 2.

So the first few cases are:

[n=1] ()
[n=2] ()() & (())
[n=3] ()()() & ()(()) & (())() & (()()) & ((()))

The sequence starts 1,1,2,5,14,42,132,429,1430,4862,...

It is formed by a convolution:

5 = 1×2 + 1×1 + 2×1
14 = 5×1 + 2×1 + 1×2 + 1×5
42 = 14×1 + 5×1 + 2×2 + 1×5 + 1×14
132 = 42×1 + 14×1 + 5×2 + 2×5 + 1×14 + 1×42

and so on... It also has an explicit formula:

nth term is 2nCn / (n+1).

So this is certainly an upper bound for what you want. Have you worked out some more values of B(n)? If so could you send them on and if I have any ideas about this then I'll let you know. Things where you start putting conditions like 'distinct' are generally difficult to count although this isn't always true...

AlexB.

By Miles Berry (T474) on Tuesday, December 14, 1999 - 11:33 am:

Thanks.
That certainly helps - what name is given to the sequence you have?
So far our (possibly incorrect) values are:
B(1)=1
B(2)=2
B(3)=4
B(4)=9
B(5)=20
B(6)=44
B(7)=103
B(8)=243
We've checked B(1) to B(5) by hand, the others are conjectured but seem quite plausible.
-Miles.

By Alex Barnard (Agb21) on Tuesday, December 14, 1999 - 12:31 pm:

Sorry... I can't believe I forgot to tell you that my sequence is called the Catalan numbers.

I've done a little searching and have discovered that it is possible to write a recurrence relation down for the things you want - although it isn't too nice! I won't tell you how I got to this in this message but if you want to know then I'll write it up in another.

Call the numbers you are looking for B(n). And define B(0)=1 and B(-ve)=0.

Define a secondary sequence A(n) as follows:

A(n) = Sum over d dividing n of d×B(d-1)

Eg. A(1) = 1×B(0) = 1
A(2) = 2×B(1) + 1×B(0) = 3
A(3) = 3×B(2) + 1×B(0) = 7
A(4) = 4×B(3) + 2×B(1) + 1×B(0) = 19
etc...

You should see that I can write down the value of A(n) if I know the values of B(m) for m<n.

Then:

n×B(n) = Sum over m>=1 of B(n-m)×A(m)

If you use this you get 1,1,2,4,9,20,48,115,286... So you seem to have everything in the right sort of size but B(6) onwards seem to be too small.

And looking this up in an encyclopedia of sequences seems to suggest that this is the best formula you are going to get. It doesn't list any closed form ways of writing the terms out just the recurrence above.

If you are interested the encyclopedia is at EoIS and your sequence is the one with 'A number' 81.

AlexB.

By Alex Barnard (Agb21) on Wednesday, December 15, 1999 - 03:42 pm:

Okay... here is the way in which I proved the above formula. It is going to use a method called 'generating function' which, once you are used to them, are a fantastic way to do problems of this form. Perhaps if I get time some day I'll write an article on them. If I think of a more direct method I'll certainly submit it here - or if anyone else can I'd be very grateful. But for now, here is a solution:

If we have a sequence B(n) where n=0,1,2,... then we can write these numbers as terms in a power series [don't worry about convergence it almost never matters!]. The resulting function is called the generating function. So, the generating function of the B(n) is defined to be:

b(x) = B(0) + xB(1) + x2B(2) + ...

The fantastic thing about this method is that now we only have a single object to deal with and lots of calculations become a whole lot more simple! So what we now want to do is find out something about the shape of the generating function you want... but before this a little detour:

Elementary bubble arrangements

By this I mean elementary as in building blocks (cf. periodic tables). I will call an arrangement of bubbles elementary if all the bubbles are inside one large one. So for example:

() & (()()) & (()) & ((()())()) are elementary
()() & (()())(()()) & ()(()) are not elementary

Notice that all the non-elementary ones above are made from 2 elementary ones - of course this isn't always true but it should indicate how we are going to build up from elementary ones.

Now suppose that we have lots and lots of pieces of paper each of which has a picture of an elementary arrangement (lots of copies of each type). We can imagine making a non-elementary one by picking a few pieces of paper and putting them down in front of us. What you mean by 'topologically distinct' is exactly that it doesn't matter which order I place the pieces of paper in.

So now we have two smaller problems... How many elementary arrangements are there and how do we fit them together to get what we want?

Counting the elementary arrangements is easy. Imagine what happens if you pop the large outer bubble. You are left with a (possibly non-elementary) arrangement of one-less bubbles. So if I write C(n) for the number of elementary arrangements of n bubbles then we have just seen that C(n)=B(n-1). [NOTE: this n-1 is why there were lots of d-1's in what I told you]

How to build up arrangements

Firstly we rearrange our bits of paper into a nicer system. Put them in piles according to the number of bubbles on the picture. So the first pile contains C(1)=B(0)=1 picture which is () [there are still lots of copies of each picture in the piles]. The second pile contains C(2)=B(1)=1 picture which is (()). And so on...

Now, how many ways are there to pick out k pieces of paper from the n'th pile? Remembering that we don't care about the order and there are C(n) different sorts of picture. Well... just pretend that C(n)=1. Then there is always 1 way to pick out k pieces of paper. What is the generating function for this? Well we want to keep track of the number of bubbles so we'll make the power of x do this for us. So we look at:

1 + xn + x2n + x3n + ...

Which is just (1-xn)-1.

What about if C(n) is more than 1? Well imagine taking the C(n)'th power of the above generating function. What is the coefficient of a given power of x? Well, you get contributions by picking p from the first bracket, q from the second,... and r from the C(n)'th and this corresponds exactly to picking p of the first type of card, q of the second,... and r of the C(n)'th type. So the generating function we want is

(1-xn)-C(n)

Well now it should be clear (!) that when we put together cards of different weights we should again multiply together. So we eventually see that the generating function for putting together elementary arrangements is:

(1-x)-C(1)(1-x2)-C(2)(1-x3) -C(3)...

And so if this was multiplied out then the coefficients would be the B(n) that we want!

I hope this is okay so far... Please write back if there is anything unclear. I'll let you know how to get the formula from where we have got soon...

AlexB.