## My Favorite Sequences: A263135

This is the fourth in my installment of My Favorite Sequences. This post discusses sequence A263135 which counts penny-to-penny connections among $$n$$ pennies on the vertices of a hexagonal grid. I published this sequence in October 2015 when I was thinking about hexagonal-grid analogs to the “Not Equal” grid. The square-grid analog of this sequence is A123663.

## A263135: Placing Pennies

The sequences A047932 and A263135 are about placing pennies on a hexagonal grid in such a way that maximizes the number of penny-to-penny contacts, which occurs when you place the pennies in a spiral. A047932, counts the contacts when the pennies are placed on the faces of the grid; A263135 counts the contacts with the pennies placed on the vertices.

While spiral shapes maximize the number of penny-to-penny contacts, there are sometimes non-spiral shapes that have the same number of contacts. For example, in the case of the square grid, there are $$A100092(n)$$ such ways to lay down $$n$$ pennies on the square grid with the maximum number of connections. Problem 108 in my Open Problems Collection asks about generalizing this OEIS sequence to other settings such as the hexagonal grid.

#### Comparing contacts

Notice that the “face” pennies in A047932 can have a maximum of six neighbors, while the “vertex” pennies in A263135 can have a maximum of three. In the limit, most pennies are “interior” pennies with the maximum number of contacts, so $$A047932(n) \sim 3n$$ and $$A263135(n) \sim \frac32n$$.

Looking at the comparative growth rates, it is natural to ask how the number of connections of $$n$$ face pennies compares to the number of connections of $$2n$$ vertex pennies. In October 2015 I made a conjecture on the OEIS that this difference grew like sequence A216256.

Conjecture: For $$n > 0$$, $A263135(2n) – A047932(n) = \lceil\sqrt{3n – 3/4} – 1/2\rceil = A216256(n).$

I believe that the sequence A216256 on the right hand side appears to be the same as the sequence “n appears $$\displaystyle\left\lfloor \frac{2n+1}{3} \right\rfloor$$ times,” but I’d have to crack open my Concrete Mathematics book to prove it.

## Polygons on a “centered $$n$$-gon”

I asked a question on Math Stack Exchange, “When is it possible to find a regular $$k$$-gon in a centered $$n$$-gon“—where “centered $$n$$-gon” refers to the diagram that you get when illustrating central polygonal numbers. These diagrams are one of many possible generalizations of the triangular, square, and centered hexagonal grids. (Although it’s worth noting that the centered triangular grid is different from the ordinary triangular grid.)

If you have any ideas about this, let me know on Twitter or post an answer to the Stack Exchange question above.

## A catalog of polytopes and grids

On my OEIS wiki page, I’ve created some tables that show different kinds of polytopes in different kinds of grids. There are quite a number of combinations of polygons/polyhedra and grids that either don’t have an OEIS sequence or that I have been unable to find.

If you’re interested in working on filling in some of the gaps in this table, I’d love it if you let me now! And if you’d like to collaborate or could use help getting started, send me a message on Twitter!

## Stacking LEGO Bricks

Back in May, I participated in The Big Lock-Down Math-Off from The Aperiodical. In the Math-Off, I went head-to-head against Colin Beveridge (who has, hands-down, my favorite Twitter handle: @icecolbeveridge). Colin wrote about using generating functions to do combinatorics about Peter Rowlett’s toy Robot Caterpillar. Coincidentally and delightfully, I wrote about using generating functions to do combinatorics about Peter Kagey’s toy LEGOs.

Counting LEGO configurations is a problem dating back to at least 1974, when Jørgen Kirk Kristiansen counted that there are 102,981,500 ways to stack six 2×4 LEGOs of the same color into a tower of height six. According to Søren Eilers, Jørgen undercounted by 4!

In my Math-Off piece, I wrote about a fact that I learned from Math Stack Exchange user N. Shales—a fact that may be my (and Doron Zeilberger’s) favorite in all of mathematics: there are exactly $$3^{n-1}$$ ways to make a tower out of $$1 \times 2$$ LEGO bricks following some simple and natural rules. Despite this simple formula, the simplest known proof is relatively complicated and uses some graduate-level combinatorial machinery.

## The Rules

1. The bricks must lie in a single plane.
2. No brick can be directly on top of any other.
3. The bottom layer must be a continuous strip.
4. Every brick that’s not on the bottom layer must have at least one brick below it.

Gouyou-Beauchamps and Viennot first proved this result in their 1988 statistical mechanics paper, but the nicest proof that I know of can be found in Miklós Bóna’s Handbook of Enumerative Combinatorics (page 26). Bóna’s proof decomposes the stacks of blocks in a clever way and then uses a bit of generating function magic.

## Other rules

In preparation for the Math-Off piece, I asked a question on Math Stack Exchange about counting the number of towers without Rule 2. The user joriki provided a small and delightful modification of Bóna’s proof that proves that there are $$4^{n-1}$$ towers if only rules 1, 3, and 4 are followed.

It might also be interesting to consider the 14 other subsets of the rules. I encourage you to compute the number of corresponding towers and add any new sequences to the On-Line Encyclopedia of Integer Sequences. If you do so, please let me know! And I’d be happy to work with you if you’d like to contribute to the OEIS but don’t know how to get started.

Another natural question to ask: How many different towers can you build out of $$n$$ bricks if you consider mirror images to be the same? In the example above with the red bricks, there are six different towers, because there are three pairs of mirror images. By Burnside’s Lemma (or a simpler combinatorial argument) this is equivalent to counting the number of symmetric brick stacks. If there are $$s(n)$$ symmetric towers with $$n$$ bricks, then there are $$\displaystyle \frac 12 (3^{n-1}+s(n))$$ towers. For $$n = 4$$, there are three such towers, shown below in blue.

I asked about this function on Math Stack Exchange and wrote a naive Haskell program to compute the number of symmetric towers consisting of $$n \leq 19$$ bricks, which I added to the OEIS as sequence A320314. OEIS contributor Andrew Howroyd impressively extended the sequence by 21 more terms. I also added sequence $$A264746 = \frac 12 (3^{n-1}+A320314(n))$$, which counts towers up to reflection, and A333650, which is a table that gives the number of towers with $$n$$ bricks and height $$k$$.

## Stacking Ordinary Bricks

It is also interesting to count the number of (stable) towers that can be made out of ordinary bricks without any sort of mortar. I asked on Math Stack Exchange for a combinatorial rule for determining when a stack of ordinary bricks is stable. MSE user Jens commented that this problem is hard, and pointed to the OEIS sequence A168368 and the paper “Maximum Overhang” by Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick, which provides a surprising example of a tower that one might expect to be stable, but in fact is not.

I’d still like to find a combinatorial rule, or implement a small physics engine, to determine when a stack of bricks is stable.

These problems and some generalizations can be found in Problem 33 of my Open Problem Collection. If you’d like to collaborate on any of these problems, let me know on Twitter. If you find yourself working on your own, I’d love for you to keep me updated with your progress!

(The graphics of LEGO bricks were rendered using the impressive and free LEGO Studio from BrickLink.)