Table of Contents

• Overview: The Problem
• Polyominoes
  • Castle Rules for Polynominoes
• Don't Generate - Enumerate!

Overview: The Problem

In an earlier post, I mentioned my efforts on Project Euler problems and the wide variety of problems there that can offer some profound mathematical insights.

Given that the first post covered Project Euler problem 1, I thought it would be nice if the next problem cranked up the difficulty factor by an order of magnitude. Project Euler Problem 502 is a very hairy combinatorics problem that required me to learn about a wide variety of combinatorial enumeration techniques.

Let's start with the problem statement.

Building Castles

Problem 502 is about building castles. The problem gives an \(M \times N\) rectangular grid, and asks us to count how many "castles" can be built on the rectangular grid, given its maximum height.

Here is how the game works:

First, start by defining a block as a rectangle of height 1, and an integer-valued length. A castle is a configuation of stacked blocks.

For a game grid of size \(M \times N\), we can construct castles according to the following rules:

• Blocks can be placed on top of other blocks, but no sticking out past edge
• All blocks aligned to grid
• Two neighboring blocks must have 1 unit of space between them
• Maximum achieved height of castle is EXACTLY M
• Castle is made from even number of blocks

Here is an example W = 8, H = 5 castle given in more compact notation:

  #   # 
  #   ##
 ## # ##
##### ##
########

We can also build more complicated castles, like this 10 by 100 castle:

X       X      XX    X     XX   XX X X                          X XX          XX   XX  X     X   XXX
X       X      XX    X     XX X XX X X     X     X             XX XX          XX   XX  X     X   XXX
X      XX      XX    X     XX X XXXX X     X     X             XX XX          XX   XX  X     X   XXX
X      XX      XX    X     XX X XXXX X     X     X XXX         XX XX          XX X XX  X     X   XXX
X      XX     XXX    X     XX X XXXX X  X  X     X XXX X X     XX XX          XX X XX  X  X  X   XXX
X      XX  X  XXX  X X     XXXX XXXX X  XX X    XX XXX X X   X XX XX          XX XXXX  X XX XX  XXXX
X  XX  XX  X  XXX  X X     XXXX XXXX XX XX XX XXXX XXX X XXX X XX XX    X     XX XXXXX X XX XX XXXXX
X  XX  XXX X  XXX  X X   X XXXX XXXX XX XX XX XXXX XXXXX XXX XXXX XX  X X     XX XXXXX X XX XXXXXXXX
X XXXXXXXX X XXXXXXX X XXXXXXXX XXXXXXX XX XX XXXXXXXXXXXXXX XXXX XX XX X  XX XX XXXXXXXXXX XXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Our objective in this problem is to enumerate all possible castles. Let \(F(x,y)\) denote the number of unique castles with a width of x and a height of exactly y. The problem gives use the trivial number \(F(4,2) = 10\). The problem also gives \(F(13,10)\) and \(F(10,13)\), both of which are absolutely enormous numbers.

This should be your first giant red flag that manual enumeration through a traversal of combinatoric space is absolutely, positively out of the question. We'll explain why in more detail below, but suffice to say, there is a combinatoric explosion that occurs for castles larger than 10, so castles with a width of 1 trillion are going to get STUPID big.

Then we're given \(F(100,100)\), which is so enormous it has to be reported mod 1,000,000,007.

Finally, the problem asks us the following whopper of a question:

What is \(F(10^{12},100) + F(10^4, 10^4) + F(100,10^{12}) mod 1,000,000,007\)?

Whew.

The Scale of the Problem

For solving this problem it is important to take a step back and think through the size of the combinatoric space being searched, and what methods we have for carving out that space.

As already mentioned, the size of this problem - the actual number of castles - is surely larger than the Eddington numer, the number of protons in the known universe. The numbers of combinations are STUPID big. There's no way for the mind to fully wrap itself around the concept.

The huge numbers involved means, we must have a closed-form expression for \(F(x,y)\) that we can evaluate once to get each of the \(F(10^{12},100), F(10^4,10^4), F(100,10^{12})\) required by the answer. Doing so much as counting to 1 trillion takes minutes on modern computers, so if you're doing anything else 1 trillion times, you'll end up waiting a loooong time.

Generating Functions

As it turns out, there is indeed a combinatorial enumeration method that does not require explicitly finding or generating each permutation in order to count all permutations. I have covered generating functions on the charlesreid1.com wiki. The principal idea behind generating functions is the observation that we can rearrange the infinite series:

into the equation

This single identity leads to a whole family of solution techniques for generating functions. The basic idea is to start by writing the rules of your system (see above), then write a generating function that varies with characteristic variables of the problem (width and height in this case, possibly others), and last, combine the generating functions of different rules or objects into a single generating function.

Overview of Polyominoes

Let us begin by considering a two-dimensional grid \(\pi\) of points at positive integer coordinates, \(\pi = \mathbb{N} \times \mathbb{N}\).

Let a polyomino denote a two-dimensional shape formed by connecting contiguous unit square tiles together, all of which align to the 2D grid of integers \(\pi\).

(Granted, this definition sounds a bit pedantic, as we're just describing stackable squares, but we need to keep the definition general because there are many kinds of polyomonioes, and many rules that we can set for how we arrange them.)

If you have played Tetris before, or John Conway's Game of Life, you will recognize polyominoes from those contexts.

Now, we set up our generating function in terms of characteristics of the problem.

It is very important to note that, while most of the rules are fairly straightforward to translate into a polyomonio type of framework, Rule 6 is not. In fact, it is probably Rule 6 that makes Problem 502 so challenging. Were it not for Rule 6, this would be a nearly-trivial problem.

Let's review our castle construction rules and translate them into polyomino equivalents.

Castle Rules for Polyominoes

Generating Function Variables

We want to construct a multivariate ordinary generating function for our castles, since we have several variables we want to change, and get back a total count of castles.

The two most obvious variable choices for our generating function independent variables are width \(x\) and height \(y\). Surely, these must be in the final generating function.

However, this still doesn't give us enough information about the construction process from step to step. Imagine that we place the first block on row 1.

Then we may place as many blocks as we would like along row 2, wherever we would like (level 2 is the least restricted layer of the castle).

Now, when we get to row 3, we are only allowed to keep building where there is already an existing tower from the prior row. This means, we have to pass along information from the prior row - where the bricks are located and how many - so that we know where the next level may build towers.

This will remain an open question until we cover a few other representations of Problem 502 and ways of modeling it. Then we will cover what additional variables our generating function might need.

Rule 1: No Overhangs

Rule 1 stipulates that blocks can be placed on top of other blocks as long as nothing sticks out past the end or hags out.

This ensures that the resulting polyomino is column convex. Column convexity is the property that we can draw a vertical line through any column of the polyomino, and we only intersect the polyomino in two places. (No internal breaks.)

This rule stipulates what kind of polyomino constructions are allowed.

Rule 2: Snap to Grid

This rule is just saying that the unit squares in the castle problem match the unit squares of polyominoes, ensuring the problems are interchangeable.

Rule 3: Neighbor Blocks Need Space

Rule 3 is crucial for being able to count blocks. If two side-by-side contiguous unit squares could be either one or two blocks, this would make the final count of solutions much, much, much, much, much bigger than it should be.

Rule 4: Bottom Row is One Block

This is more of an accounting-based rule, but we define our castle construction process such that it begins with a completed row. This means that the number of blocks that we add on top of that single block must be odd overall.

Rule 5: Maximum Height is Exactly H

As it turns out, the last two rules are the toughest - in a sense, because they are global conditions on the combinatoric solution that is being counted. In other words, we will use generating functions to "construct" our combinatoric objects in a methodical way, and the challenge is on setting global conditions on the generating function's counted solutions.

Rule 6: Even Number of Blocks

Rule 6 is definitely what makes this problem difficult.

Our approach is going to involve coming up with a counting function - but this rule tells us that the counting function will need to have some way of accounting for the total number of blocks, and divide by or subtract a factor that accounts for castles with an odd number of blocks.

Don't Generate - Enumerate!

We mentioned above that the number of possibilities here is huge, so this combinatorics problem falls squarely in the realm of enumerating, not generating.

That being said, and keeping in mind that the problem size blows up rapidly, it can still be useful to write an algorithm to generate castles for small values of width and height, to test formulas for these small values (and uncover corner cases!).

See Project Euler/502 on the charlesreid1.com wiki for continued work on this problem.

Table of Contents

• Overview: The Problem
• Why This Problem?
• Going Deeper: An Example

Overview: The Problem

Project Euler is a website that provides mathematically-oriented programming problems. There are many (over 500) and they are a rich source of profound mathematical insights.

I have been considering a writeup that goes deep into a particular problem, so why not do it with problem 1?

Problem 1 of Project Euler asks:

Find the sum of all the multiples of 3 or 5 below 1000.

It is a pretty simple task - one of the first things covered in a decent programming course is the assortment of mathematical operators, including the modular operator and multiplication operator, useful here.

This problem is also a familiar problem in another guise - any computer science student who has solved a variant of the fizz buzz problem will recognize this task (in the fizz buzz problem, you print fizz every time a number is divisible by 3 and buzz every time it is divisible by 5, etc.)

It is a deceptively simple problem. In fact, it is so easy to solve with a computer that you almost lose a sense of what the manual process would look like. How might we perform this task by hand?

Finally, it is an example of a problem in which we are trying to find the number of outcomes of several classes of events, and some of the events are labeled with both classes. This means it will be important to learn and apply the Inclusion-Exclusion Principle. (Fortunately, this principle is fairly straightforward to apply.)

We will get to the algorithm to counting these factors by hand, and handling more complicated constraints as well, but first I'll address why this problem - this task - was deemed important enough to be the very first step that nearly everyone takes on their epic (or... not so epic) Project Euler journey.

Why This Problem?

The central task in this problem is to find multiples of a number \(k\), and count them. The task is simple enough (unlike later Project Euler questions, which can be downright frightening at times), but still requires knowledge of loops, operators, and basic algorithm design. It's no litmus test for whether you can solve Problem 100, but it gets you started.

The task at the heart of this problem - iterating through a list of multiples of a number - is at the heart of the Sieve of Eratosthenes algorithm, which in turn is at the heart of applied number theory. While it may not be the algorithm applied in practice, it is the first and most important algorithm number theorists learn.

It's also a first lesson in the subtleties of Project Euler problems - the eager but naive algorithm designer will count all multiples of 3, then all multiples of 5, forgetting that some repeat.

Welcome to Project Euler.

Going Deeper: An Example

It's true that this problem seems a bit boring on its face. But let's dive deeper. Suppose I asked you to find the number of multiples of the integers 3 and 4, but not the integer 5, below 2,001 - and to do so without explicitly enumerating them with a computer.

To do this, we can express the problem in set notation. We have three sets, A, B, C, containing multiples of 3, 4, and 5, respectively. In set theory language, we wish to find

We can start by counting the sets A and B, as well as accounting for \(A \bigcap B\) (numbers that are multiples of both a and b).

Next, we can count \(A \bigcap C\) and \(B \bigcap C\), which are the multiples of a and b that we counted that we should not have because they are multiples of c.

Finally, we cannot forget \(A \bigcap B \bigcap C\) - numbers that have a, b, and c as multiples. This case is a bit tricky. Any item that is in \(A \bigcap B \bigcap C\) has already been removed - twice. The first time was when it was removed because it was in \(A \bigcap C\), and the second time was when it was removed because it was in \(B \bigcap C\). Therefore, we must add each of these items back in, to account for the double-removal and ensure these items are only removed once.

So we will add the items in \(A \bigcap B \bigcap C\) back into the final set.

Visually representing A, B, and C with a Venn diagram,

To get back to the problem at hand, we can compute the size of these sets using the floor function. For example, the cardinality of A is:

Next, we subtract the duplicates (numbers with both A and B as factors):

Now subtract integers that have both a and c as multiples, or b and c as multiples:

And last but not least, those numbers with a, b, and c as factors were just removed twice, so we add them back in once:

This gives a total number of multiples M below N with a or b as a factor, but not c:

in our specific case,

The Lattice Paths Problem

I first came across the lattice paths problem in Project Euler problem 15. The question described a 2x2 square lattice, and illustrated the 6 ways of navigating from the top left corner to the bottom right corner by taking the minimum number of steps - 2 right steps and 2 down steps.

The question then asks for the number of minimum paths on a 20 x 20 grid. Needless to say, even without seeing the number, it should be obvious that enumerating all of these paths would get extremely expensive with grid dimensions growing beyond 10. That means this should be approached as an analytical combinatorics problem, not a computational combinatorics problem. As it turns out, there is a closed-form solution, and this is one of the few Project Euler questions that can be answered with the straightforward use of Wolfram Alpha (I solved it while boarding a bus).

But this is an interesting problem that goes beyond the Project Euler question - it has to do with a combinatorics problem that is maddeningly simple, yet surprisingly difficult to formulate - the problem of multisets.

Problem Formulation: Permutations

Thinking through the 2x2 grid, we already stated that the shortest path must consist of 2 right moves and 2 down moves - the number of paths is simply a question of the order in which these moves are made. Let us represent the path that moves right twice, then down twice, using the string

RRDD

Now we have a way of representing paths through the lattice - and we've turned our very specific lattice problem into a much more general combinatorics problem. How many unique permutations of the above path/string can we find?

Permutations of Unique Items (Factorial)

Let's suppose we have a string consisting of unique characters:

ABCDEFG

Now how many permutations of this string are there? The first letter can be any of the 7 characters, so we have 7 possibilities. The second letter can be any of the remaining 6 characters, so we have 7 * 6 possibilities. And so on down the line, until we get a total number of possible permutations of the string equal to

There are 5040 unique permutations of the string.

Our situation is complicated by the fact that some of our permutations are repeated. For example, if we label the two down moves as D1 and D2, we can choose the first move as D1 and the second move as D2, or the first move as D2 and the second move as D1 - the two are equivalent. This will eliminate some of the permutations.

Permutations of Items with Duplicates (Multichoose)

Our case is slightly different: we have items with duplicates. This fits into a general combinatorics framework called stars-and-bars (link to Wikipedia article). In this framework, we are trying to determine the number of ways that we can partition a set of n objects into a set of \(k\) bins. The \(n\) objects are often denoted as star characters, and the k bins are formed by k-1 bar characters.

For example, if we are adding 5 components to a circuit board, and they can be any one of 9 possible components, we can represent this as the partitioning of 5 stars among 9 bins, or 8 bars. Here are some possibilities:

||||||||        <-- No choices made yet (9 bins, 8 partitions)
*|*||*||*|*||   <-- Mix of different components
||*|*||*|*||*   <-- Mix of different components
****|||*|||||   <-- Heavy on component 1
*|**|||**||||   <-- Two pairs

In the case of our lattice path problem, we have only two unique characters, D and R. We can think of the problem of generating permutations as inserting the down moves into a sequence of right moves. We have a certain number of locations where we can insert the down moves, and down moves can be inserted in order.

This is what's often called a stars-and-bars problem in combinatorics: trying to determine the number of permutations of items from multisets can be described as partitioning star characters with bar characters.

To formulate our problem in these terms, we can think of "distributing" our down moves as we move right through the lattice. On the 20x20 grid, we are going to make 20 right moves, and we can distribute our 20 down moves at any of 21 possible locations (columns of points on the lattice).

Thus, our n items, the 20 down moves, are being placed between the 20 right moves, which are the 20 bars that create 21 bins (21 locations to place the down moves).

Example

Considering the smaller 2x2 example, and replacing bars with R, we have, for a 2x2 lattice, six possibilities:

RR    <-- No choices made yet
**RR  <-- all on left
*R*R  <-- distributed... etc...
*RR*
R**R
R*R*
RR**

To enumerate the number of possibilities, we use the multichoose function, denoted "n multichoose k". This counts the number of ways to place n objects (D) into \(k\) bins (created by \(k-1\) other objects, R). The multichoose function is defined as (see https://en.wikipedia.org/wiki/Multiset#Counting_multisets Wikipedia page for proper Latex notation - it looks like the binomial coefficient but with 2 parentheses):

where, again, n is number of objects, being split into \(k\) partitions by \(k-1\) other objects.

Now, let's plug in the numbers for the 2 by 2 lattice. We get:

We are partitioning 2 down moves among 3 possible columns in the lattice. This gives:

which is indeed the number of paths through the lattice.

Solving 2D Rectangular Lattice

To generalize, on a lattice of width \(W\) and height \(H\), we have \(W\) right moves that form \(W+1\) partitions, in which we are placing H items. The number of possible paths through the lattice is therefore equivalent to permutations of the string:

RRRR...(W times)...RRRDDDD...(H times)...DDDD

Now n and k are given by:

so the total number of possible paths through the W x H square lattice is:

More Examples

The number of minimal paths through a 4 x 2 lattice (identical to the number of paths through a 2 x 4 lattice) is:

The number of minimal paths through an 8x8 lattice is given by:

and finally, the number of minimal paths through a 20 x 20 lattice is given by:

(This is the Project Euler problem 15 answer so last few digits are omitted.)

Solving 2D Square Lattice (Special Case)

If we use the above formulas for the special case where the dimensions of the grid are equal, such as the 20 x 20 case, we get the simpler and more symmetric formula:

where \(D\) is the dimension of the square grid.

Solving 3D Cuboid Lattice

(Note: cuboids are the 3D analogue of 2D rectangles.)

If we take this idea a step further, and use a slightly different combinatoric formula, we can generalize the problem to paths through higher dimensional lattices. This is an approach I came up with through trial and error, and some experimentation with Mathematica.

Suppose we have a 3D lattice, composed of 8 cubes, 2 on each side. Now we wish to know: how many shortest Manhattan distance paths are there through the lattice, from one corner to the other?

This can be re-cast, as we did above, as the problem of counting unique permutations of a string of the form:

UURRBB

where U denotes an up move, R denotes a right move, and B denotes a back move.

While we could use the multiset approach from above to describe this problem, it turns out that this approach is not powerful enough to describe the problem of arbitrary 3D lattices.

Let's pose the problem slightly more generally: we have C bags of moves or characters, each of a different size. We must use each character i precisely as many times as we have instances in its bag C_i. How many unique permutations are there?

Consider the following example string of length \(N = 14\), consisting of:

These form a path through a 3D lattice of size \(4 \times 4 \times 6\):

UUUURRRRBBBBBB

The number of unique permutations can be computed by breaking this into sub-problems. Start by asking how many permutations there are of the string:

UUUUXXXXXXXXXX

(Treating the Rs and Bs as identical). Then we get:

Next, we deal with the other sub-problem, the Xs, by asking how many ways we can permute the following string:

RRRRBBBBBB

which is solved via another binomial coefficient. This number of permutations is given by:

Now combining these, we get the overall number of permutations:

Solving 3D Cubic Lattice (Special Case)

If we have the special case of a perfect cubic lattice, the formula above reduces to the nice and symmetric:

Solving N-Dimensional Square Lattice (N-Dimensional Multisets)

Let's look at the example of a traversal of a 4D lattice, which we can think of as the evolution of a 3D traversal in time (a step in the fourth dimension would represent a "pause" in the 3D traversal).

Consider the traversal of a cube with dimensions \(3 \times 4 \times 5 \times 3\). Then

A path on this 4D lattice has the form:

UUURRRRBBBBBWWW

(where \(W\) denotes wait, or a step in the time dimension).

The number of permutations is given by:

For our specific example,

Confirmed by Mathematica: