Sigurður Helgason and I explore in our bachelor’s thesis, Identifying Combinatorial Structures for Binary Strings and Set Partitions, how to build combinatorial specifications for avoidance classes of binary strings and set partitions. Building upon the work of Bean et al. and the CombSpecSearcher system, we show that we can find a combinatorial specification for any avoidance class of binary strings, and combinatorial specifications for many avoidance classes of set partitions.
I think even in tech and computer science it’s unlikely most people know what a combinatorial specification or avoidance class is, so here’s a quick motivating example with binary strings.
Let’s say you wanted to know how many binary strings of length 10 do not contain the substring ‘101’. This would be easy enough to brute force, but what if you then wanted to know the same thing for binary strings of length 9999? This would be considerably more difficult to brute force. In my thesis I show how to count the number of binary strings of any length that avoid (i.e., do not contain) some given substring. I also explore the same idea applied to set partitions (with plenty of cool tikz graphics!), but you’ll have to read the thesis to see how.