I have a finite alphabet A and a set S of $n$ ordered pairs $(a, b)$ with $a,b\in A.$ I want to find out how many sequences $(a_1, b_1),\ldots,(a_n,b_n)$ there are where adjacent elements have either $a_{k-1}=a_k$ or $b_{k-1}=b_k.$ (Since S is a set, they can't have both.)
Any ideas on how to go about finding this? Formulas, generating functions, algorithms, or whatever you have. In my particular application I have $|A|=10$ and $|S|=21$, but the question seems general.
Also, in my application $(a_1,b_1)$ and $(a_k,b_k)$ are not adjacent. (They can have, but need not have, one member different.)
Edit: For clarification, I'm not allowing all elements from $A\times A$, just those in $S$. No valid answer can ignore S. For example, I might have S = {(1, 1), (3, 3)} in which case there are no valid orderings.
For those interested in using a matrix approach (not sure if this can work; the path needs to go through each pair exactly once), here's the adjacency matrix:
[0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0] [1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0] [1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1] [1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0] [0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0] [0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0] [1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0] [0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0] [0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1] [0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0] [0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0] [1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0] [0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1] [1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0] [0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0] [0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0] [0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0] [0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0] [0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0]
Kudos to anyone who recognizes it (and thus my goal).