# Hypergraph coloring problem motivated by legal billards racks

Motivation

There are several rules about what makes a rack legal for a game of eight-ball: the top ball has to be a solid, the eight-ball is in the middle, the two bottom vertices have to be one solid and one stripe, etc. But a rule I learned when I first learned to play pool was that there should be no three balls which are pairwise touching each other that are all stripes or all solids. Apparently this is not an actual rule for professional eight-ball. Nevertheless, it is an interesting restriction.

Problem

Suppose we color the points in a triangular grid with base length $n$ with two colors, $A$ or $B$. How many such colorings have the property that no three points in a touching triangle are all the same color?

For instance, with $n=4$, a legal coloring is,

     A
B A
A B B
B B A B


but an illegal coloring is,

     A
B A
A A B
B A B A


because it contains a triangle with three $A$s.

If $\kappa(n)$ denotes the number of legal colorings for a grid with base $n$, what is $\kappa(n)$?

-
You might try setting up a recursion. Forgive the signatory pun. Gerhard "It May Involve Pascal's Triangle" Paseman, 2012.08.30 –  Gerhard Paseman Aug 31 '12 at 4:25
Also, when I in my not so misspent youth was racking up for 8 ball, I was supposed to alternate patterns on the border, with the 1 at an apex and the 8 close to it in the interior. This always left one striped triangle, usually to the lower right of the 8 ball when I lifted the rack. Gerhard "Wore Platforms To See Felt" Paseman, 2012.08.31 –  Gerhard Paseman Aug 31 '12 at 16:16

I calculated the first few terms recursively.

$1, 2, 6, 24, 130, 960, 9702, 134512, 2562516, 67152240, 2422643366, 120395521752, \\\ 8245524190254, 778511553019200, 101361018574446630$

They weren't in the OEIS, but taking off the initial $1$ and dividing the other terms by $2$ produced A007017, which referred to "L. Vuillon, 'Contribution a l'etude des pavages et des surfaces dicretisees,' Dissertation, Universite de la mediterranee, Marseille, France 1996."

Some problems like this have a closed form solution or asymptotics, but typically there is some entropy per area which people can bound but can't compute exactly, such as the hard square entropy constant.

-
Out of morbid curiosity, what made you consider "taking off the initial $1$ and dividing the other terms by $2$"?? –  Vidit Nanda Aug 31 '12 at 5:43
Well, the $1$ is trivial, the number of patterns for the empty triangle. The recursion I used enumerated triangles by the patterns of their bottom rows. Among the possible symmetries which might reduce the recursion, I considered forcing the first entry of the row to be an A. This optimization wasn't worth the trouble to compute the first few terms, but I figured someone else might mod out by the global $A \leftrightarrow B$ symmetry. –  Douglas Zare Aug 31 '12 at 6:02
One thing I noticed was a connection to domino tilings. If you place an AB tile next to another, one of the letters placement will be determined by the trianglee condition, and one should then place the domino to fill that condition. That doesn't mean every coloring is a domino tiling of the triangle, but a lot of it is. Gerhard "Ask Me About System Design" Paseman, 2012.08:30 –  Gerhard Paseman Aug 31 '12 at 6:13
In fact in the comments section of the OEIS they mention this exact problem: "Also, half the number of (n+1)X(n+1)X(n+1) triangular binary arrays with no upright or inverted 2X2X2 subtriangle that is all 0's or all 1's. - R. H. Hardin, Oct 22, 2010." Thanks for this find! –  Sam Hopkins Aug 31 '12 at 15:41