While doing estimates on the complexity of an algorithm I have run into a word-combinatorial problem with both a local and a global constraint.
This seems to be a rather general situation and I'm sure there must be useful literature on the subject, though I haven't found anything that quite applies.
The local constraint in my case is simply a set of bad words to be avoided, and the global constraint is that no letter must repeated.
Consider an alphabet of $N$ letters divided in $p$ families. The $i$-th family contains $n_i$ letters ($i=1,...,p$), and $\sum_{i=1}^p n_i = N$.
We want to compute the number of words of $q$ letters ($q \leq N$) such that: (1) they all start with the same letter; (2) no letter appears more than once; (3) there are exactly $s$ pairs of adjacent letters from different families.
So the set of "bad" words consists of all two-letter words made with letters from two different families.
We are counting the self-avoiding words of length $q$ that begin with a given letter and contain exactly $s$ bad words as factors.
I can solve the local and global constraint separately. I solve the local one with the Goulden-Jackson method, the global one by just counting.
The problem is that Goulden-Jackson doesn't really apply to global constraints. If you apply it, the equation for the clusters is unyieldy. There must be a better way to handle these situations.
