3

For example,

$n = 3$, $(2,3,1,2,1,3)$ or $(3,1,2,1,3,2)$

$n = 4$, $(4,1,3,1,2,4,3,2)$ or $(2,3,4,2,1,3,1,4)$

This problem does have a name, but I did not find it. Thanks for @Martin R, It is called Langford pairing problem.

Assume that $L_{n}$ is the number of solutions of Langford pairing problem.

Actually, I want to know some conclusions or references about the following:

  1. The proof of $L_{n} = 0~~\text{iff}~~n~\text{mod}~4 = 1~\text{or}~2$.

  2. The general formula or recurrence formula of $L_{n}$ (A176127$(n)$ in OEIS).

  3. Given $n$, how to find one of the solutions.

  4. Given $n$, how to find all the solutions and the representation of them.

As for (1), it is proved in "Some new possibilities of optimum synthetic linear arrays for radioastronomy" in 1975. You are welcome if you have a simple proof.

As for (2)(4), the answer seems open.

As for (3), I have no idea about the algorithm.

Assume that $A_{m,n} = (1,2,\ldots,n,1,2,\ldots,n, \ldots, 1,2, \ldots, n)$ (repeat $m$ times). There is a concept named high-order sequence denoted $L(m,n)$. It is denoted the number of permutations of $A_{m,n}$ with the property that there are $k$ numbers between each two $k$'s in the set for $k=1,\ldots,n$.

I will close this question unless it is useful.

Blanco
  • 656
  • Thought that https://oeis.org/A026272 might be relevant, but no luck. – Ivan Neretin Feb 19 '20 at 15:36
  • It looks like youer second example is missing a $2$ in the end. What do you mean by "how to"? Do you want a prescription how to find such a reordering for general $n$? – joriki Feb 19 '20 at 16:05
  • You missed as well $(2,3,4,2,1,3,1,4)$ for the case of $n=2$,. indeed any valid arrangement when read forwards will also be a valid arrangement when read backwards. A dirty javascript method reveals that there are no valid arrangements for $n=5$. Running the same script for $n=6$ is taking a while, but I'm doubtful that any additional sequences will exist for higher $n$. I might try rewriting it in python more efficiently if I get time. – JMoravitz Feb 19 '20 at 16:12
  • There are no solutions for $n=5, 6$. There are $52$ solutions for $n=7$ and $300$ solutions for $n=8$. No solutions for $n=9, 10$, and $35584$ solutions for $n=11$. (Unless I made a programming error.) – Martin R Feb 19 '20 at 20:30
  • 2
    This is http://oeis.org/A176127: The number of permutations of {1,2,...,n,1,2,...,n} with the property that there are k numbers between the two k's in the set for k=1,...,n. – Martin R Feb 19 '20 at 20:39
  • 1
    https://en.wikipedia.org/wiki/Langford_pairing – Martin R Feb 19 '20 at 20:45
  • In the "high-order" problem, you can't have $k$ numbers between each two $k$s; you may mean $k$ numbers between each $k$ and the next $k$. – Gerry Myerson Oct 27 '22 at 05:21
  • Did you check the links and references at http://oeis.org/A014552 ? – Gerry Myerson Oct 27 '22 at 05:23

0 Answers0