I have manually identified possible combinations for a small set I have been working with and I'm not sure if I have overlooked some valid options. I would like to be able to calculate the quantity of sequences of ordered pairs that may be formed by a set of n elements such that, starting with an arbitrary ordered pair of those elements (a,b), the second pair in the sequence has a replaced by a different element (e.g., (c,b)) and the third pair in the sequence has b replaced by a different element (e.g., (c,d)), with this alternation continuing for the remainder of the sequence. I would also stipulate that no ordered pairs repeat, all possible combinations of elements are included as pairs, and the last ordered pair in the sequence may be followed by the first pair of the sequence were ordered pair repetition permitted.

For example, such a sequence for n=2 would be (0,1); (1,1); (1,0); (0,0).

My understanding is that the start and end pairs in the above example are arbitrary; to compare it to a latin square, I'm looking for a count of isotopy classes of ordered pair sequences formed from the same quantity of elements, not just a count of all possible ordered pairs or all possible ordered pair sequences. My hunch is that the circularity and pairing requirements of the sequence imply that it may be formed only when n^2 mod4=0; this is fine by me as I believe it would be different were the permutation rules different (but if I am mistaken I would like to know!).

  • 1
    $\begingroup$ Possibly useful re-formulation: if you represent all pairs as a graph with $n^2$ vertices, with an edge between $(a,b)$ and $(c,d)$ if $a=c$ or $b=d$, then you are asking for the existence of a Hamilton cycle on this graph. $\endgroup$ – angryavian Apr 17 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.