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

  • 0
    I suggest to adopt some terminology to clarify, for instance, let's say two pairs are "similar" if they have the first element equal, or the second (or both, of course). So, are you trying to count the sequences that have all adjacent pairs "similar" ? Or the sequences that have at least two adjacent pairs simliar?2010-11-15
  • 0
    Also, I don't understand your last sentence. I understood that "adjacent" elements are the consecutive pairs in the sequence. Then, obviously, (a1,b1) (a2,b2) are adjacent.2010-11-15
  • 0
    Charles: In the last sentence, do you require that $(a_1,b_1)$ and $(a_k,b_k)$ not have $a_1=a_k$ or $b_1=b_k$ or is that allowable? It sounds like you don't care. If you require that there be no match the problem is harder. Also in your first paragraph it would be good to repeat (if you mean it like the title says) that you cannot have both $a_{k-1}=a_k$ and $b_{k-1}=b_k$2010-11-15
  • 0
    @Ross Millikan: Correct, I don't care.2010-11-15
  • 0
    @leonbloy: I want to count the sequences where all adjacent pairs are similar. I've clarified the question to make S a set, so there is no pair of distinct pairs where the first and second elements are equal.2010-11-15
  • 1
    For the curious, [here's what Mathematica 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
    I would appreciate any references you find.2010-11-15
  • 1
    @Charles: I updated the answer with a reference. The problem seems to be computationally quite hard.2010-11-15
  • 0
    @Rahul Narain: Thank you very much! Since my immediate interest is in a very small graph (21 elements), exponential time is acceptable. This also tells me that I won't be able to do the three-dimensional case, which has 143 elements.2010-11-15
  • 0
    @Rahul Narain: I don't see how the all simple paths problem solves mine. I need paths that use all points which can start and end from any points; that gives paths that need not use all points starting and ending with given points. Am I missing a simple reduction?2010-11-15
  • 0
    @Charles: I should mention that I got the reference for #P-completeness from [Roberts and Kroese, J. Graph Alg. Appl., 2007](http://www.cs.brown.edu/sites/jgaa/accepted/2007/RobertsKroese2007.11.1.pdf), which turned up in a Google search. This paper may also be useful to you for larger graphs.2010-11-15
  • 0
    @Charles: Oh, I didn't notice that you wanted a path of length exactly $n-1$. In that case, you're trying to count the number of *Hamiltonian* paths in the graph. Then yes, what I posted is not relevant. Sorry!2010-11-15
  • 0
    @Charles: I've updated my answer to be even less helpful. :)2010-11-15
  • 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
    What are you trying to count?2010-11-15
  • 0
    I'm trying to count how many sequences there are, following the statement. Why the downvote?2010-11-15
  • 0
    You might have got your quantifiers wrong, then. Are you calculating the same number as I do? We're getting different answers.2010-11-15
  • 0
    S is not the same as A x A.2010-11-15