Skip main navigation

Flexagons and Catalan numbers

Read Yossi Elran's article about the connection between flexagons and Catalan numbers.
14 graphs depicting all the North and East grid paths between 2 points that do not cross the diagonal between them
© Davidson Institute of Science Education, Weizmann Institute of Science

Catalan numbers are one of my favourite types of numbers! They pop up regularly in situations where things need to be counted (a branch of mathematics called combinatorics).

Catalan numbers

Here is a list of the first ten Catalan numbers:

  • 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862…

Take for example the following problem. You live in a city built like a grid, like Manhattan or Toronto. To get to work you need to walk four blocks East and four blocks North. How many different ways are there to do this, if you are not allowed to cross the diagonal line between your house and your work?

Pause. I’m waiting for you to figure this out…

Correct! The answer is 14. You can see all the different 14 paths in the image above. 14 is the fourth Catalan number. Actually, it’s the fifth, but we call the first number the zero’th, so that works out OK. If the distance between your house and work was five blocks South and five blocks West, the answer would be 42 different paths. If the distance was two blocks North and two blocks West, the answer would be 2. Generally speaking, for a grid with dimensions n x n, the answer is the n’th Catalan number. If you lived at work, the grid has the dimensions 0 x 0 and the answer would be the 0’th Catalan number which is one, so that makes sense.

Catalan numbers are also the answer to many other question such as: How many ways are there to divide a convex polygon with n + 2 sides into non-crossing triangles? For a hexagon, n = 4 and the answer is the 4’th Catalan number, 14.

Dividing a hexagon into non-crossing triangles

For the mathematically inclined there is a formula to calculate the Catalan numbers and you can find it here or here along with more examples and explanations.

Catalan numbers and flexagons

So what does all this have to do with flexagons? For one, Catalan numbers pop up in combinatorial formulas for calculating the number of different kinds of flexagons. Here are 10 various number series, all related to some counting of flexagons, and all with some relationship to Catalan numbers. The most immediate connection though, is this.

A hexaflexagon pat can be split with a finger right through it so it comes out the other side. This splits the pat into two sub-pats. If there are only 2 leaves, as is the case with the tri-hexa-flexagon, there is only one way to split them. We’ll we’ll call the two leaves a and b, so we can write the pat structure as: (a,b), where the comma marks the splitting point. If there are 3 leaves in a pat, a, b and c, it can be split in two different ways: one leaf in the top sub-pat and two in the bottom, or two leaves in the top sub-pat and one in the bottom: (a,b-c) or (a-b,c). The dashed line means that the leaves are hinged. They create a pocket but not a full opening. Notice that because of the way flexagons are constructed, there can only be 1 or 2-leaf pats. This means that, when writing all the possible structures of a pat, we use all possible reductions to one or two leaf sub-pats. Hence, a four-leaf pat can be split in 5 different ways: (a, (b-c)-d); (a, b-(c,d)); (a-b,c-d); (a-(b-c),d); ((a-b)-c,d). Note that the difference between (b-c)-d and b-(c-d) is equivalent to the two options of the three leaf pat, except that instead of having a full opening there is an inner pocket. So (b-c)-d indicates a hinge between a two-leaf sub-pat on the top hinged to a single leaf on the bottom, and b-(c-d) indicates a hinge between a leaf on the top hinged to a two-leaf sub-pat on the bottom. A five-leaf pat can be split this way in 14 different ways. 1,2,5,14… Wait a minute! These are Catalan numbers! That’s the connection! In general, an (n+1) leaf pat can be split in the n’th Catalan number different ways…

Discussion

Any questions? Post your questions and comments below!

© Davidson Institute of Science Education, Weizmann Institute of Science
This article is from the free online

Flexagons and the Math Behind Twisted Paper

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education