2
$\begingroup$

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).

  • 1
    For the curious, [here's what $M$athematica thinks the above graph looks like](http://imgur.com/LcvOV.png). I certainly can't recognize it.2010-11-15

4 Answers 4

4

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.

  • 0
    @Rahul Narain: Hmm... I don't think that generating all permutations is a good way to go, since my graph (see question) is fairly sparse. The three-dimensional version is even sparser.2010-11-15
2

Rubin [1] gives an algorithm for counting Hamiltonian paths.

Mathematica has tools for working with Hamiltonian paths, but the naive

Length[HamiltonianCycles[G, All]] 

gives an out-of-memory exception for this particular graph.

[1] Frank Rubin, A search procedure for Hamilton paths and circuits (1974)

0

EDIT: This answer assumes that $S = A \times A$.

Given a pair $(a,b)$, there are $2|A|-1$ pairs (a',b') such that a=a' or b=b' (or both). Therefore if we don't care about the relation between first and last element, we get $|A|^2(2|A|-1)^{n-1}$ sequences.

  • 0
    OP said differ in exactly one component in the title, though the text was not explicit. If that is what he wants it should be $|A|^2(2|A|-2)^{n-1}$. But your logic is sound.2010-11-15
-1

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|$)

  • 0
    S is not the same as A x A.2010-11-15