2
$\begingroup$

Question

I am interested in finding a general formula for the number $L(2,n)$ of Langford pairings. After several months of searching for patterns, I have made the following observations:

The number of Langford pairings when $n=3$ is $$L(2,3)= \frac{(2*3)!}{(2!)^3} -\left[\left(\frac{90}{2!-0^2}\right) +2\left(2^2+\frac{90}{3!-1^2}\right)\right]= 90 -45 -44= 1$$

Similarly, the number of Langford pairings when $n=4$ is $$L(2,4)= \frac{(2*4)!}{(2!)^4} -\left[\frac{2520}{2!-0^2} + \frac{2}{1}\left(-2^2+\frac{2520}{3!-1^2}\right) + \frac{3}{2}\left(2^2+\frac{2520}{4!-3^2}\right)\right] = 2$$

The next solution should look like this, for $n=7$, but why?? $$ N= \frac{(2*7)!}{(2!)^7}, L(2,7)= N -\left[\frac{N}{2!-0^2} +\frac{5}{4}\left(-2^2+\frac{N}{0!*(3!-1^2)}\right) +\frac{5}{2}\left(2^2+\frac{N}{1!*(4!-3^2)}\right) +\frac{14}{1}\left(-2^2+\frac{N}{2!*(5!-6^2)}\right)\right] = 51$$

the fractions should have 0!, 1!, and 2! divided into them, and the N= 'odd' entries should have a 1 added to the final answer to be correct.

(In particular, the numerators of the []-terms are equal to the initial term)

Can we extend this pattern to a formula for general $n$, and prove that it counts the number of Langford pairings?

Motivation

I read a summary of Knuth's Art of Computer Programming, written by Vamsi K. I skimmed his anecdote and realized the dilemma for counting Langford Pairings corresponded directly to an "exact" covering of a set. I have heard people describe the interference of digits and the counting method for their place-holders as degenerative, but that's only true in a small number of cases.

At first, I was only sure of one thing:

Proposition: $\displaystyle\frac{(2n)!}{(2!)^n}$ is the exact count for the possible number of arrangements having only $2$ elements of each number in their sequences.

But nothing else came to mind. So I looked through a book called, Numbers by David Wells, and I noticed that Nikolaus Bernoulli had used a 'sub-factorial' to count the number of ways that he could mail $n$ letters to everyone on his list, but to all the wrong persons. I recognized his problem was related to Langford sequences: N. Bernoulli knew that $$5!*(1 -1/1! +1/2! -1/3! +1/4! -1/5!)=44$$ or the number of ways that 5 letters inside 5 wrong envelopes could be sent incorrectly to 5 different addresses.

I tweaked Bernoulli's 'sub-factorial' formula by subtracting the square of a number from each denominator factorial of each term, and some further thinking brought me to the above observations.


[[This post has been edited from the original text by a third party, and the interpretation may be flawed. In order to preserve the interests of the original poster, the full text of the previous edit is displayed below.]]

Original Post

first, the problem is to count the number of times that 231213, 312132 would appear from the 90 possibilities of "112233". $90 = \Large \frac{(2*3)!}{(2!)^3}$ my computer program counted: None matching, 44; One matching, 40; and Only Two Matching, 4. The 40 and 4 combine to form 88 (not 89 by formula.)

second, the problem is to count the number of times that 23421314, 41312432 would appear from the 2520 possibilities of "11223344". $2520 = \Large \frac{(2*4)!}{(2!)^4}$ my program counted: No Matches, 1228; One match, 1000; Two matches, 258; and Three matching, 32. The 1228 & 32 combine to form 1260.

the first calculation is slightly off because using a formula to count during iterations is trying to be "1-1 and onto" or a bijection. it wouldn't map back to "2" counts from two different calculations.

the next step, if someone can produce it by formula, is to count the number of Langford Pairings from the possible $681,080,400 = \Large \frac{(2*7)!}{(2!)^7}.$ the answer is 52... 26 possibilities and their reversals. one example is 1 4 1 5 6 7 4 2 3 5 2 6 3 7. Can you do it "by formula"??? My computer counts don't reveal what the formula is going to be... Bill

I like to count!... and when someone finds a very interesting puzzle, say Langford/Skolem pairings, it bothers me when !!NO ONE!! can count the number of possible pairs for a given 'n', even when we know which 'n's hold true for making each pairing, we know the number of possible combinations for each 'n' using brute force on the computer, and we can produce a singleton for each 'n' in the set of {n mod 4} == -1, 0; etc. the "best part" of ANY puzzle is to arrange the pattern in your mind using al- gebra(to eventually discover the formula with confidence!!!):

I read a summary of Knuth's Art of Computer Programming, written by Vamsi K. I skimmed his anecdote and realized the dilemma for counting Langford Pairings corresponded directly to an "exact" covering of a set. all coverings follow specific "algebraic" rules which Dr. Martin Gardner overlooked. many people have described the interference of digits and the counting method for their place- holders as degenerative. however,that's only true in the first case!

when I first read about this problem in Ian Stewart's book, The Cabinet of Mathematical..., it hibernated in my mind for the next 6 months. it took me a total 2 & 1/2 years to boil out the incon- sistencies to produce the formulas below! in the first few minutes, I was ONLY sure of one thing: $\large \frac{(2*n)!}{((2!)^n)}$ was the EXACT count for the possible number of arrangements having only 2 elements of each number in their sequences... 2-1's, 2-2's, 2-3's, etc.

I !!desperately!! wanted a formula that would count the number of Langford pairings, and two weeks ago, I looked through a book called, Numbers... by David Wells, given to me by a friend, and I noticed that Nikolaus Bernoulli had used a 'sub-factorial' to count the number of ways that he could mail 'n' letters to everyone on his list, but to all the wrong persons. I simply recognized that he didn't have the interference incorporated w/stuffing his envelopes, but his problem (solution) was absolutely related to Langford sequences: i.e. N. Bernoulli knew that... $5!*(1 -1/1! +1/2! -1/3! +1/4! -1/5!)=$ $44$, or the number of ways that 5 letters inside 5 wrong envelopes could be sent incorrectly to 5 different addresses. he was very brillant indeed!!!

finally, I tweaked Bernoulli's 'sub-factorial' formula by subtracting the square of a number from each denominator factorial of each term, and it was a nice find! and well worth the wait!! (I never gave up.) here's the formula for counting the number of Langford pairings:

(the intermediate calculations necessary for counting Langford pairings)

$n= 3;\large \frac{(2*3)!}{(2!)^3}= 90 ; \frac{90}{2!-0^2}= 45, \frac{90}{3!-1^2}= 18$

$L(2,3)= 90 -[45 +2*(18 +2^2)]= 90 -45 -44= 90 -89= 1$; case is slightly degenerative, since $L(2,3) = 2.$

$n= 4; \large \frac{(2*4)!}{(2!)^4} = 2520 ; \frac{2520}{2!-0^2}= 1260, \frac{2520}{3!-1^2}= 504, \frac{2520}{4!-3^2}= 168.$

$L(2,4)= 2520 -[1260 + \frac{2*(504 -2^2)}{1} + \frac{3*(168 +2^2)}{2}] = 2520 -1260 -1000 -258= 2520 -2518= 2.$

you can simply imagine what the general formula is for counting Langford sequences, or L(2,n). (I would stop here), and have confidence that we can surely wrap our minds around how to count the number of Langford pairings for a given 'n' using a formula.

Bill Bouris 8/31/2014

$\endgroup$

closed as unclear what you're asking by Peter Taylor, daw, user147263, DisintegratingByParts, Omnomnomnom Oct 6 '14 at 18:22

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Welcome to Math.SE! I strongly suspect you have an interesting problem here, but you've done the Reader a disservice by the amount of editorializing ("all coverings follow specific 'algebraic' rules which Dr. Martin Gardner overlooked.") A good Question has a concise presentation of the problem for which an Answer is sought: definition and problem statement. This will likely (almost surely, in your case) be followed by a brief account of what makes the problem interesting, difficult, or relevant. $\endgroup$ – hardmath Oct 6 '14 at 0:47
  • 1
    $\begingroup$ In one session, I didn't provide a preamble, and I was criticized for being terse. Now, I'm being accused of over editorializing? If you know the name Martin Gardner as it relates to math, you would have understood that he was mostly interested in recreational math. I really don't understand the who, what, when, where, why and how it seems relevant to comment or vote on something as certain as a math problem without being able to answer my question. Either it's good (and it is...), or it can be disproved, and canceled for the better. Not much maths is being done on the website, just bickering. $\endgroup$ – user124808 Oct 6 '14 at 2:07
  • 2
    $\begingroup$ I added additional info to the front end of this question. My computer counts don't reveal any next step in synthesizing a more general formula. Bill $\endgroup$ – user124808 Oct 6 '14 at 3:19
  • 2
    $\begingroup$ @user124808: Okay, I have made my edit. One specific question that I am still uncertain about: do you have in mind a particular formula for $L(2,n)$? Certainly there are some obvious patterns between the two calculations you provided, but not all of them are clear. In particular, what is the significance of the $2^2$ terms? are they intended to flip signs at every term? and why aren't they in the second term? If you have a concrete idea for the intended summation formula, that would add a lot of value to the post. $\endgroup$ – Eric Stucky Oct 6 '14 at 3:59
  • 2
    $\begingroup$ I don't actually see a question. If this is an attempt to follow David Eppstein's advice that for your ideas to be included in the Wikipedia page on Langford pairing you should first get them published, then you should be aware that he was talking about publication in a peer-reviewed journal, not on a Q&A site. $\endgroup$ – Peter Taylor Oct 6 '14 at 15:53
5
$\begingroup$

I feel that it may help the Reader to have (as Community Wiki, feel free to add/edit) some notes about the history of counting Langford sequences.

J.W. Larsen's thesis has a good introductory section, Counting the number of Skolem sequences using inclusion-exclusion, which describes both Langford and Skolem sequences and progress in their counting. Among other references cited is a web page on Langford's Problem maintained by John E. Miller, recently (April 2014) updated.

A Langford sequence $(a_1,\ldots,a_{2n})$ of length $2n$ (or order $n$) contains two of each entry $1,\ldots,n$, arranged so that if $a_i = a_j$, then $|i-j|=n+1$. An example of this for $n=4$ is $(4,1,3,1,2,4,3,2)$. Note that here $n$ corresponds to the number of entries in the gap between the pair of appearances. [Skolem sequences are instead defined so that the positions of the pair differ by $n$, so that an example of a Skolem sequence of order 4 would be $(2,3,2,4,3,1,1,4)$.]

The notation $L(2,n)$ is used by Miller to mean the count of Langford sequences of order $n$, treating such a sequence and its reversal as but the same solution. The OEIS sequence A014552 also gives the counts "up to reversal". Unfortunately some links there to Miller's pages have page-not-found errors, likely due to site migration issues, but the record computation seems to be $L(2,24)=46845158056515936$ by M. Krajecki and team at Universite de Reims Champagne-Ardenne (April 2005).

Langford's Problem is named for C. Dudley Langford, whose submission to the Mathematical Gazette in 1958 noted watching his son play with colored blocks and forming a stack with green, red, blue, red, green, blue, which amounts to a Langford sequence of order $3$:

$$ (3,1,2,1,3,2) $$

Langford added a pair of yellow blocks, rearranging them to yellow, red, green, red, blue, yellow, green, blue, which may be seen as the order $4$ Langford sequence mentioned before. Langford gave further examples, but noting that they seemed not to exist for certain $n$, asked for a theoretical treatment of which $n$ allow solutions.

In Mathematical Gazette v. 43 (1959), Roy O. Davies gave the existence answer in On Langford's Problem II, that solutions exist if and only if $n \equiv 0,3 \pmod{4}$. The problem of computing $L(2,n)$ is naturally more difficult.

He gives the following solutions. Each consists mostly of strings of consecutive odd or consecutive even numbers, and all but the first and last elements of each string are replaced by ellipses.

For $n=4m$: $$\begin{align*}4m-4,&\ldots,2m,4m-2,2m-3,\ldots,1,4m-1,1,\ldots,2m-3,2m\ldots,4m-4,\\&4m,4m-3,\ldots,2m+1,,4m-2,2m-2,\ldots,2,2m-1,4m-1,\\&2,\ldots,2m-2,2m+1,\ldots,4m-3,2m-1,4m\end{align*}$$

For $n=4m-1$: $$\begin{align*}4m-4,&\ldots,2m,4m-2,2m-3,\ldots,1,4m-1,1,\ldots,2m-3,2m,\ldots,4m-4,\\&2m-1,4m-3,\ldots,2m+1,4m-2,2m-2,\ldots,2,2m-1,4m-1,\\&2,\ldots,2m-2,2m+1,\ldots,4m-3\end{align*}$$

In case one needs an excuse to go to the bookstore, some citations to Martin Gardner's puzzle book Mathematical Magic Show are on the OEIS page, and citations to Donald Knuth's ACP v.4 may be found in Larsen's thesis.

$\endgroup$

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