The Big Lock-Down Math-Off, Match 15

Welcome to the fifteenth match in this year’s Big Math-Off. Take a look at the two interesting bits of maths below, and vote for your favourite.

You can still submit pitches, and anyone can enter: instructions are in the announcement post.

Here are today’s two pitches.

Colin Beveridge – The Young Rowlett’s Robot Caterpillar

Colin blogs at flyingcoloursmaths.co.uk and tweets at @icecolbeveridge.

I stopped my run mid-stride, almost falling onto a cyclepath. Peter Rowlett, in an episode of Mathematical Objects, had just invoked the dread incantation: generating functions.

I do not use the phrase ‘dread incantation’ lightly. Generating functions are one step removed from dark magic, and it immediately became my mission to use them to solve the Robot Caterpillar Problem.

Peter’s son has – or, I should say, had – a toy robot, comprising a head and eight attachments. The attachments can be arranged in any order: three that cause the robot to move forward, two that turn it left, two that turn it right, and one (in a twist I’m sure is entirely unconnected to the fact that the robot no longer works) that plays a jaunty tune. Any number of segments between one and eight (inclusive) constitutes a valid robot. The packaging claims the number of arrangements is “endless”; Peter believes the number to be… well, endful. But how many exactly?

A brief explainer on generating functions

Before you get onto the robot’s generating function, I’m going to start with an example that’s a bit less complicated.

Consider the binomial expression \( (q + px)^n \), where \( p + q = 1\). If you expand that, you get \( q^n p^0 x^0 + n q^{n-1}p^1 x^1 + \dots + \begin{pmatrix}n \\ r \end{pmatrix} q^{n-r} p^r x^r + \dots + p^n x^n \).

Consider also the binomial distribution. Given \( n \) trials, each with a probability of \( p \) of success and \(q \) of failure, the probability of \( r \) successes is \( \begin{pmatrix} n \\ r \end{pmatrix} q^{n-r}p^n \) – which is exactly the coefficient of the \( x^r \) term in the expansion above.

The binomial expression \( g(x) = (q + px)^n \) is the generating function of the binomial distribution: it turns a probability distribution into a polynomial in \( x \), which can be manipulated to give all sorts of nice results (for example, the expected value of the distribution is \( g'(1) \), or at least the limit from below. Can you see why?)

It’s not just for probability distributions, though: it’s also for counting problems. Like, to pull an example out of thin air, the number of ways to arrange the segments of a robot.

Generating a robot

The approach Peter and Katie suggest in the podcast is to figure out the possible combinations of pieces using a generating function in four variables:

• Represent the possible number of forward pieces as \( 1 + f + f^2 + f^3 \) – since you can use 0, 1, 2 or 3 forward pieces;
• Represent the possible number of left pieces as \( 1 + l + l^2 \) – since you can use 0, 1 or 2 left pieces;
• Represent the possible number of right pieces as \( 1 + r + r^2 \);
• Represent the possible number of music pieces as \( 1 + m \).

… and multiply all of those together. Each term of the resulting polynomial has either zero, one, two or three \( f \)s in it, zero, one or two \( l \)s, and so on. Because of how multiplication works, every possible combination of pieces turns up in the expansion exactly once.

However, they turn up without respect to order – so, for example the term \( f^2 r l^2 m \) represents all of the possible robots containing two forward pieces, a right piece, two left pieces and a music piece – which can be combined in \( \frac{6!}{2!2!} = 180 \) different ways. All you need to do is work out the number of arrangements for each of the 72 terms and add them up.

I don’t know about you, but I didn’t spend seven years at dark magic school to do grunt work like that. We have a Wolfram|Alpha for doing grunt work. The only question is, how to set up the problem so that Wolfram|Alpha gives us the answer?

First insight: dividing out repeated segments

If a combination of segments has \( n \) different segments in it, there are \( n! \) different ways to arrange them. However, if any segment appears more than once, the number of possible arrangements is reduced – for every segment that appears \( k \) times, you have to divide by \( k! \).

Rather than do that manually every time, why not build it in to the generating function? Instead of representing the number of forward pieces by \( 1 + f + f^2 + f^3 \), represent it as \( 1 + f + \frac{1}{2}f^2 + \frac{1}{6}f^3 \); the left pieces become \( 1 + l + \frac{1}{2}l^2 \), and the right pieces \( 1 + r + \frac{1}{2}r^2 \). The music pieces don’t need to change (mathematically, at least).

That would turn the term that used to be \( f^2 r l^2 m \) into \( \frac{1}{4} f^2 r l^2 m \) – so it’s now a term of degree… six; you can get the total number of 6-segment robots by adding up all of the degree-six terms and multiplying by \( 6! \) – and similarly for the other degrees.

Second insight: who needs all of those letters?!

Now you’ve accounted for all of the repeats, it doesn’t really matter (for counting purposes) what the pieces are – only the degree of the term involved. That means, if you replace all of the variables with \( x \), you can “simply” do the expansion and combine the terms to end up with only nine things to work out.

The generating function is now \( g(x) = \left(1 + x + \frac{1}{2}{x^2} + \frac{1}{6}{x^3}\right)\left( 1 + x + \frac{1}{2}x^2\right)^2 \left(1+x\right) \), which Wolfram|Alpha is quite happy to work out.

All you have to do is replace each degree-\( n \) term with \( n! \) and add up the result.

That’s still boring, though. There must be a way to do that automatically, mustn’t there?

Of course there is.

Third insight: operational calculus

There’s a trick, in generating functions: if you want to multiply each of the degree-\( n \) coefficients by \( n \), you can just differentiate. So, if you want to multiply the \( x^8 \) coefficient by \( 8! \), all you need to do is differentiate eight times! The number remaining as the unit term is the number of eight-segment permutations.

However, there’s a problem: if you do that, all of the lower-order terms vanish, and that’s not what you want at all. Also, if you differentiate, say, six times, your unit term is the correct number of six-segment permutations, but you still have an \( x \) and an \( x^2 \) term that you don’t really want – you can handle that, though, by evaluating this derivative at \( x = 0 \).

To find the total number of possible robots, you need to sum the first eight derivatives of \( g(x) \) – which, what with this being a polynomial, means the sum of all of the derivatives, and evaluate the result at \( x=0 \).

That is to say, you want \( g(0) + g'(0) + g”(0) + … \), and this is the correct point to abandon any pretense of rigour.

Let’s use \( D \) to represent \( \frac{d}{dx} \), and abuse notation to say you’re after the function \( R(x) = \left(1 + D + D^2 + D^3 + \dots\right)g(x) \), which you’ll evaluate at \( x =0 \).

Everybody knows that \( 1 + D + D^2 + D^3 + \dots = \frac{1}{1-D} \), so you can rewrite: \( (1-D)R(x) = g(x) \), or (dropping the \((x))\), \( R – R’ = g \).

That can be solved using an integrating factor:

• \( \frac{\mathrm{d}}{\mathrm{d}x}\left(Re^{-x}\right) = -ge^{-x} \)
• \( Re^{-x} = -\int ge^{-x} \mathrm{d}x \)
• So \( R = -e^x \int ge^{-x} \mathrm{d}x \)

Finishing off

That’s not something that’s especially nice to work out by hand (in effect, you have to do all of the differentiation you were trying to avoid) – but Wolfram|Alpha doesn’t mind!

If you scroll down to the expanded form, it gives \( \frac{1}{24}x^8 + \frac{2}{3} x^7 + \frac{145}{24} x^6 + \frac{479}{12} x^5 + \frac{619}{3} x^4 + 834 x^3 + \frac{5019}{2} x^2 + 5023 x + 5024 \); when this is evaluated at \( x= 0\), you get 5024.

Removing the one case where there are no segments gives 5023, which is the answer Peter gave on the podcast. Alakazam!

---

Peter Kagey – Counting Stacks

Peter writes about maths at peterkagey.com and tweets at @PeterKagey.

One of the most surprising combinatorial formulas I know is also one of the simplest. It arises when counting stacks of $1 \times 2$ LEGO bricks like this:

Here’s the miracle: If you have $n$ bricks, stacked according to the four rules below, then there are exactly $3^{n-1}$ different ways to stack them! Why is this surprising? Because despite how simple the formula is, there is no simple explanation for why the formula is so nice!

Usually when some set of objects is counted with such a simple formula, there’s an easy explanation. In this case, for example, you might expect that there are always exactly three ways to add a new block onto an existing stack. Curiously, there’s not such an easy explanation.

The Four Rules

There are four rules that these stacks of bricks must follow. (Below the list, you can find examples of stacks that break each of these rules.)

• The bricks must lie in a vertical plane.
• Each brick must be offset by 1 stud, like you might see in a brick wall.
• The bottom layer must be contiguous.
• Every brick must have at least one brick below it.

This means that the following four stacks are not allowed:

An example for three bricks.

When building with three bricks, there are $3^{3-1} = 9$ such structures.

A proof

This result was first proven in a 1988 statistical mechanics paper, but the nicest proof that I know of can be found in Miklós Bóna’s book (page 26). Bóna’s proof uses decomposes the stacks of blocks in a clever way and then uses a bit of generating function magic. (Generating functions are a tool in combinatorics which is usually first encountered at the beginning of graduate school.)

Uncharted territory

By removing or modifying any of the four rules, you get new kinds of stacks with different formulas. For example, if you remove the second rule, there are $4^{n-1}$ stacks of $n$ bricks—another miraculous fact that is equally tricky to prove. Most changes, however, don’t result in such nice formulas.

Here’s where you come in! If you’d like to do a bit of original mathematics, choose some set of rules and count up the number of resulting stacks for small numbers of blocks. Even better, find a formula for the number of stacks!

These counts would make a great addition to the On-Line Encyclopedia of Integer Sequences. If you’d like to do this, but feel intimidated or don’t know where begin, I’d love to do it together with you––just let me know on Twitter (@PeterKagey)!

---

So, which bit of maths made you say “Aha!” the loudest? Vote:

Note: There is a poll embedded within this post, please visit the site to participate in this post's poll.

The poll closes at 9am BST on Monday the 11th, when the next match starts.

If you’ve been inspired to share your own bit of maths, look at the announcement post for how to send it in. The Big Lockdown Math-Off will keep running until we run out of pitches or we’re allowed outside again, whichever comes first.