Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  leonbloy Nov 15 '10 at 3:14
    
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. –  leonbloy Nov 15 '10 at 3:20
    
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$ –  Ross Millikan Nov 15 '10 at 15:20
    
@Ross Millikan: Correct, I don't care. –  Charles Nov 15 '10 at 16:53
1  
For the curious, here's what Mathematica thinks the above graph looks like. I certainly can't recognize it. –  Rahul Nov 15 '10 at 18:06

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
    
I would appreciate any references you find. –  Charles Nov 15 '10 at 17:03
1  
@Charles: I updated the answer with a reference. The problem seems to be computationally quite hard. –  Rahul Nov 15 '10 at 17:46
    
@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. –  Charles Nov 15 '10 at 18:08
    
@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? –  Charles Nov 15 '10 at 18:12
    
@Charles: I should mention that I got the reference for #P-completeness from Roberts and Kroese, J. Graph Alg. Appl., 2007, which turned up in a Google search. This paper may also be useful to you for larger graphs. –  Rahul Nov 15 '10 at 18:14

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)

share|improve this answer

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.

share|improve this answer
    
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. –  Ross Millikan Nov 15 '10 at 5:39

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

share|improve this answer
    
What are you trying to count? –  Yuval Filmus Nov 15 '10 at 3:30
    
I'm trying to count how many sequences there are, following the statement. Why the downvote? –  leonbloy Nov 15 '10 at 3:32
    
You might have got your quantifiers wrong, then. Are you calculating the same number as I do? We're getting different answers. –  Yuval Filmus Nov 15 '10 at 3:36
    
S is not the same as A x A. –  Charles Nov 15 '10 at 16:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.