4
$\begingroup$

In Blom, Holst, Sandell, "Problems and snapshots from the world of probability" there is a claim that the number of ways of placing $j$ dominos in a ring with $2n$ places in such a way, that each domino occupies two adjacent places, and the dominos do not overlap is $ N_{2n,j} = \frac{2n}{2n -j} \binom{2n-j}{j} $

How does one derive this result?

2 Answers 2

5

Corrected 30 September 2016.

Imagine that the $j$ dominoes have been placed. Paint one of them red, and break the ring immediately to its left. You now have a row of $2n$ places, $2j$ of which are covered by dominoes, including in particular the first two places. Number the dominoes from left to right, starting with the red one: $D_1,D_2,\dots,D_j$. The $n-2j$ uncovered places occur in $j$ blocks, some of which may be empty: after $D_j$, and between $D_k$ and $D_{k+1}$ for $k=1,\dots,j-1$. Counting the number of ways to distribute $2n-2j$ indistinguishable objects $-$ the uncovered places $-$ amongst $j$ distinguishable containers $-$ the spaces between adjacent dominoes and after $D_j$ $-$ is a straightforward stars-and-bars problem, and the answer is

$\binom{(2n-2j)+j-1}{j-1}=\binom{2n-j-1}{j-1}\;.\tag{1}$

However, the red domino could have occupied any of $2n$ different positions around the ring, so each of these arrangements actually corresponds to

$2n\binom{2n-j-1}{j-1}\tag{2}$

arrangements of one red and $j-1$ plain dominoes around the ring. On the other hand, in each arrangement of $j$ plain dominoes around the ring we could have chosen any of the $j$ dominoes to be the red one, so $(2)$ actually counts each arrangement of the plain dominoes $j$ times. The final result is therefore

$N_{2n,j}=2n\cdot\frac1j\binom{2n-j-1}{j-1}=2n\cdot\frac1{2n-j}\binom{2n-j}j=\frac{2n}{2n-j}\binom{2n-j}j\;.$

If you’re not familiar with the identity $\frac1k\binom{n-1}{k-1}=\frac1n\binom{n}k\;,$ expand both sides in terms of factorials. In the form $n\binom{n-1}{k-1}=k\binom{n}k$ it also has a very easy combinatorial proof: both sides calculate the number ways to choose a team of $k$ from a pool of $n$ players and appoint one member of the team to be its captain.

  • 1
    @Nick: The correct interpretation is that I made a mistake; I’m amazed that no one caught it before now. Although the final result was right, the explanation of the intermediate steps was out of order, and the old intermediate expression $(2)$ to which you refer did *not* in fact represent what I said it did; as you observe, it isn’t even always an integer. I’m very glad that you caught drew my attention to it; I’ve now corrected the explanation (and fixed a moderately serious typo that everyone also seems to have missed).2016-09-30
2

Your problem is equivalent to selecting $j$ non-consecutive places on a circle of size $2n$. The formula $N_{2n,j} = \frac{2n}{2n -j} \binom{2n-j}{j} $ is explained here.

  • 0
    @Sasha Thanks for reminding me of that one. I guess if you hang around here long enough you start to see the same problems over and over in different guises!2012-09-06