Counting with Wang Tiles

Friday, November 14, 2014 - 9:00am - 9:50am
Keller 3-180
Igor Pak (University of California, Los Angeles)
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.
MSC Code: