Folding de Bruijn graphs

I wrote recently about foldings of de Bruijn graphs, why we are interested in them, and how pleased I was that we had agreed that the de Bruijn graph with word length 4 over a 2-letter alphabet has 1247 foldings (or said otherwise, there are 1247 automata over a 2-letter alphabet whose state is determined by the last four symbols read).

Well, now we have a formula for the number of foldings of de Bruijn graphs with word length 2 over arbitrary alphabets, which (programmed in GAP) can compute the number for alphab et size 20 in 700 milliseconds, and alphabet size 30 in 50 seconds.

I won’t describe the formula here. The computation involves nested loops, the outer loop over partitions of the alphabet, and the inner loop over partitions of the set of parts in the outer loop; the inner loop implements a Möbius inversion over the lattice of set partitions, while the outer loop sums products of the function computed by the inner loop.

I am discussing it here because of a sidelight on how mathematics gets done. I was trying to understand the fact that, for word length 2 over alphabet of size 3, there are 192 foldings. I had observed that 192 = 5³+3×22+1; I knew where the first and last terms came from but was thinking about 22. I went to bed, and as I lay there going to sleep I understood how to get this number (it is B(2)(B(4)−B(2)²), where B(n) is the nth Bell number). So I went to sleep, confident that I could reproduce the argument in the morning.

Well, of course, the next morning, I tried to write it out and got stuck, and by the evening I hadn’t got unstuck. So I went back to bed, and replayed my mental processes, and back it came in full clarity. I didn’t leap up and write it down, but simply rehearsed the argument until it was absolutely clear to me and I was sure I could recover it in the morning.

And, sure enough, I could!