Sequences of pairs where adjacent elements differ in exactly one component 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).
Let $m = \lvert A\rvert$, and denote by $L_{m,m}$ what is variously called the $m\times m$ rook's graph or lattice graph: it has $m\times m$ vertices arranged in a square, with an edge connecting two vertices if they are in the same row or column. There is a natural mapping between the vertices of $L_{m,m}$ and ordered pairs of elements from $A$, of which $S$ is a subset. Then a sequence of length $n$ in your problem is equivalent to a Hamiltonian path in the subgraph of $L_{m,m}$ induced by $S$.

The number of such paths will certainly depend on the elements of $S$, and not just their cardinality. For example, let $m = 2$ and $n = \lvert S\rvert = 2$; if the two elements of $S$ are adjacent, then there is one Hamiltonian path, otherwise none.

The simplest algorithm I can think of is to simply generate all permutations of the $n$ vertices and check whether each one is a valid path. Finding a single Hamiltonian path is NP-complete, so I'm not sure you can do much better. You could do a search for "count number of hamiltonian paths" and see what you get.
Perhaps I'm misunderstanding your problem. But if you want to count how many sequences of pairs there are which where each two conscutive pairs have at least one element in common, the answer seems easy. Just count how many sequences there are that have not that property, and substract from the total.

I get, then, $a^{2n} - a^2 (a-1)^{2(n-1)} = a^2 [ a^{2(n-1)} - (a-1)^{2(n-1)}]$ (where $a = |A|$)