Videos

Counting with Wang Tiles

Presenter
November 14, 2014
Keywords:
  • Combinatorial sequence
MSC:
  • 11Bxx
Abstract
Even a casual reader of OEIS knows that some sequences are quite nice and elegant (e.g. A000108) while others are very erratic and rather difficult (e.g. A000002). One way to explain the difference is to say that the former sequences count natural combinatorial objects, while the latter do not. But what exactly IS a natural combinatorial sequence? We attempt to answer this question. We consider a class of sequences which can be computed with a finite set of Wang tiles inside an nxn square. Rather surprisingly, this simple class has never been studied until now. We show that many nice combinatorial sequences belong to this class (Bell numbers, Catalan numbers, partition numbers, etc.) Joint work with Scott Garrabrant.