# 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

$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."
• 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