A LEGO Counting problem

It is commonly believed that the number of ways to combine six two-by-four studded lego bricks of the same color is

102,981,500

This number was computed at LEGO in 1974 and has been systematically repeated by LEGO Company since, for instance in LEGO Company Profile 2004. It also appears in books like The ultimate LEGO book (Dorling Kindersley, 1999). Consequently, the number can be found in several "fun fact" books and on more than 250 home pages in a multitude of languages. However, the number is wrong - very wrong. By an extensive, but rather straightforward computer calculation we have found that the correct number is

915,103,765

Questions and answers

Material LEGO is a registered trademark of the LEGO Company.
Why is 102,981,500 wrong?

This number is - roughly - the number of ways one can build a tower of height six with two-by-four studded LEGO bricks. But when one builds with LEGO one does not have to put each brick on top of the previous one. Indeed, it is a main feature of LEGO that one can combine the bricks much more freely. LEGO has counted all configurations like

but neglected all the lower configurations, like

How does one arrive at the number 102,981,500?

Consider first how many ways two two-by-four LEGO bricks can be combined. If one fixes the position of the lower LEGO brick, the second can be put on top in 46 ways, namely

However, only the blue combinations here are unique. All of the other combinations have doubles which can be achieved by rotating the lower brick 180 degrees so we see that the number of different combinations of two LEGO bricks of the considered size is

2+44/2=24

To build a tower with six bricks, one can choose among the 46 positions five times. Again, most of the configurations thus obtained have doubles. There are 25 symmetric configurations, but the remaining 465-25 configurations are counted twice. We get

25+(465-25)/2=102,981,504

Note that the number reported by LEGO is off by four. This is probably just because the calculator used at the time did not have the capacity for 9-digit numbers.


How does one arrive at the number 915,103,765?

We have written computer programs to systematically generate and count all the different configurations with six two-by-four studded LEGO bricks. This is a computation which takes about half a week on a standard home computer.

To avoid error, we have independently developed two different computer programs and executed them on different platforms. The program first developed by Søren Eilers is written in Java, executed on a G4 Apple Powerbook, and uses a recursive counting process. The program subsequently developed by Mikkel Abrahamsen is written in Pascal, executed on an Intel Machine with Windows XP and uses an iterative counting process.

The number of configurations of various heigts are

HeightNumber
2 7,946,227
3162,216,127
4359,949,655
5282,010,252
6102,981,504
Total 915,103,765

Why didn't LEGO compute the correct number?

It may seem surprising that LEGO has not found the larger number, since the purpose of the calculation must have been to convince the public that this toy was a flexible one. But to compute the correct number would seem to be impossible without access to a relatively powerful computer. At the time when the computation was done such computers were probably not available to LEGO.

Jørgen Kirk Kristiansen, who has carried out the computation leading to 102,981,500 in the LEGO corporate newsletter Klodshans in May 1974 clearly states that he only intends to count the towers of maximal height. Obviously this has been forgotten over the years.


Why is it so hard?

It is worthwile to point out that it is not the size of the number which is the problem. In fraction of a second, we can compute that there are

4,028,635,400,867,168,454,517,798,790,018,457,665,536

ways to combine 25 two-by-four LEGO bricks into a tower of height 25. That this is a 40 digit number causes no problem, because we have the efficient formula

224+(4624-224)/2
for the number of combinations.

But the mathematics of the total number of combinations is so irregular that it is very difficult to come up with a formula for it. Thus one has to essentially go through all the possibilities. Based on our data, we estimate the total number of ways to combine 25 two-by-four LEGO bricks to be a 47 digit number.

With the current efficiency of our computer programs we further estimate that it would take us something like

130,881,177,000,000,000,000,000,000,000,000,000,000,000

years to compute the correct number. After some 5,000,000,000 years we will have to move our computer out of the Solar system, as the Sun is expected to become a red giant at about that time.


Why is this interesting?

Clearly nobody really needs to know exactly how many ways there are to combine 6 or more LEGOs, as clearly demonstrated by the fact that LEGO has done very nicely with the smaller number over several decades!

Thus this is mainly interesting as a challenge for mathematicians: To compute or at least estimate the number of ways to combine a given number of two-by-four LEGO bricks. Such challenges are always important to drive mathematical research, and it oftens happens that methods developed to study a problem with no practical applications (like this one) are useful to study problems which do have an impact on everyday life.

Mathematicians often get the question of whether there is anything left to study in mathematics. The common misconception that the study of mathematics is somehow complete is probably induced by the fact that the mathematics most people encounter during their education is several centuries old. The fact of the matter is that mathematics is a vivacious research area with lots of open problem, and here is a good one to point out.


What are our results?

We predict that it is impossible to find efficient formulae to compute the number of ways to combine N bricks. We have proved that the number of ways to combine N bricks into a tower of height N-1 (with two bricks at exactly one of the levels) is

(37065N-89115)46N-4+(2N-1)2N-1

and one can do something similar for other relatively "high" configurations. But finding explicit formulae for the total number seems impossible.

The number of ways to combine seven 2x4-blocks is

85,747,377,755

We have in a paper On the entropy of LEGO given decent upper and lower bounds for the number of configurations with N bricks. For instance, it is less than

and thus grows no faster than 204N. In the other direction, on may use that there are 74130 ways to build a tower with 4 blocks of height 3 with 2 blocks in the middle layer to prove that the growth is at least as fast as 64N.

More subtle estimates can be given to show that the growth lies between 78N and 191N. We predict that the true value is around 100.


Who are we?

Søren Eilers is an associate professor (Danish title: lektor) at the Department of Mathematics at the University of Copenhagen, Denmarks largest university, founded 1479. He got suspicious about the number 102,981,500 after seing it at a visit to the LEGO museum at the LEGOLAND park in Billund, Denmark. In the summer of 2004, he developed and executed a program which gave the number 915,103,765. Subsequently, he has toyed with the problem of finding a better description of the number of combinations. Being no expert no combinatorics, he has tried to persuade colleagues to work on the problem.

Mikkel Abrahamsen is a high school student at Odsherreds Gymnasium who approached the Department of Mathematics at the University of Copenhagen to ask for suggestions for a project. Søren Eilers suggested this problem to him, without giving his number or any details about how he had found it. Mikkel Abrahamsen then proceeded to develop his own method and independently computed the number 915,103,765. The method used by Mikkel Abrahamsen has computational benefits compared to the one developed by Søren Eilers, and he has subsequently worked on improving the speed of the programs to get better estimates on the number of configurations with more than 6 bricks. Mikkel Abrahamsen was awarded the Danish "Forskerspire" prize for these contributions.

Bergfinnur Durhuus is an associate professor at the Department of Mathematics at the University of Copenhagen. Being an expert on mathematical physics he saw connections from the LEGO problem to methods from this area, and found estimates on the number of configurations with a given number of bricks which we have subsequently been able to refine.


How to contact us?

Email Søren Eilers at eilers@math.ku.dk or call 0045 35320723 (workdays, 9am-3pm CET). Languages: Danish (native), English, Swedish (fluent).


Søren Eilers
Last modified: Thu Apr 7 09:43:19 CEST 2005