How to approximate the Langford numbers with probability? A Langford pairing, also called a Langford sequence is a permutation of the multi set {$1,1,2,2, \dots, n,n$} in such a way that there are exactly $k$ elements in between every $k$.
Interestingly, such an arrangement is only possible when $n \equiv -1,0 \pmod 4$. The number of different pairings for a given value of $n$ is given by $L_n$. 
Note the use of the word different. A permutation is said to be different from another permutation, if one cannot be gotten from the other by reversing the order. So, $L_3 = L_4 = 1$. The permutation for $n = 3$ is $312132$. It's reverse permutation $231213$ is not considered different so the value of $L_n = 1$. 
Now, for the question. 
If a permutation of ${1,1,2,2, \dots n,n}$ is chosen at random, what is the probability that two $k$'s are exactly $k$ positions apart, given $k$ ? Use this to guess the size of Langford numbers $L_{n}$.
I have been able to make neither head nor tail of the solution given in the book. 
$2n - k - 1$ of the $\binom{2n}{2}$ equally likely pairs of positions satisfy the stated condition. If these probabilities were independent, (they aren't) the value of $2L_n$ would be 
$$
\begin{align}
\binom{2n}{2,2,2, \dots 2}\prod_{k=1}^n\frac{2n - k - 1}{\binom{2n}{2}} &= \frac{(2n)!^2n(n-1)}{n!(2n)^{n+1}(2n -1)^{n+1}} \\
&=\exp(n\ln\frac{4n}{e^3} +\ln\sqrt \frac{\pi e n}{2} + O(n^{-1}))\\
\end{align}
$$
I understand why there are $\binom{2n}{2}$ pairs in total but why are $2n - k - 1$ pairs chosen out ? How is that number picked out ? 
Placing two elements $k$ positions apart is equivalent to choosing a contiguous string $k + 2$ length. So, there should be $2n - k - 2$.But, it is not. What is the reason for this ?
Independent probability of what ? How does that imply the value of $2L_{n}$ ? And why is that expression a product of a multi nominal coefficient and a product ?
I could understand the first equality but have no clue about the final equality. I'm not sure how the factor of $O(n^{-1})$ comes up. Here's the formula that I think will help.
$$\ln n! = n\ln n - n + O(\ln n)$$
Please help me.
Thanks.
 A: On the $2n-k-1$ pairs, you're miscounting by $1$. You're right that a string of length $k+2$ is being placed, but there are $m-j+1$ positions for a string of length $j$ in $m$ elements, not $m-j$. (This is perhaps easiest to see for $m=j$.)
Independent probability of what? Of each pair being placed at the right distance. The first multinomial factor counts the permutations of the elements, and the product multiplies the probabilities for each pair to be at the right distance. If these probabilities were independent (which they aren't), multiplying them would yield the probability that all pairs are at the right distance simultaneously, and multiplying that by the total number of equiprobable permutations would then yield the number of admissible permutations.
The number of permutations is given by that multinomial coefficient because there are $2n$ elements to permute, but each pair can be permuted among themselves without changing the permutation, so $n$ factors of $2!$ need to be divided out of $(2n)!$.
The factor $2$ in $2L_n$ is to account for the fact that $L_n$ only counts the permutations up to reflection.
For the final equality, use
$$
n!=\sqrt{2\pi n}\left(\frac n{\mathrm e}\right)^n\left(1+O\left(\frac1n\right)\right)
$$
(see Wikipedia). Then
\begin{align}
\frac{(2n)!^2n(n-1)}{n!(2n)^{n+1}(2n -1)^{n+1}}
&=\frac{2\pi2n\left(\frac{2n}{\mathrm e}\right)^{4n}\left(1+O\left(\frac1n\right)\right)n(n-1)}{\sqrt{2\pi n}\left(\frac n{\mathrm e}\right)^n\left(1+O\left(\frac1n\right)\right)(2n)^{n+1}(2n-1)^{n+1}}
\\
&=\frac{\sqrt{\pi n/2}n^n2^{2n}\left(1-\frac1n\right)}{\mathrm e^{3n}\left(1-\frac1{2n}\right)^{n+1}}\left(1+O\left(\frac1n\right)\right)
\\
&=
\frac{\sqrt{\pi\mathrm e n/2}n^n2^{2n}}{\mathrm e^{3n}}\left(1+O\left(\frac1n\right)\right)\;,
\end{align}
and taking the logarithm yields the quoted result. (Here $\left(1+\frac xn\right)^n=\mathrm e^x\left(1+O\left(\frac1n\right)\right)$ was used.)
