Combinatorics on partial word borders

We develop a powerful graph theoretical approach that can compute the number of partial words, sequences with wildcard or hole characters, having a set of strong and weak periods, the number of partial words having a set of border lengths, the number of partial words having a maximum border length, the population size of a border array, the number of partial words having any set of required compatibilities and incompatibility sets, any of the above restricting to a fixed number of holes, any of the above restricting to a set of hole positions, to name a few. In the process, we establish some elegant relationships between these numbers, the Bell numbers, and the Stirling numbers of the second kind.