# Number of ways to cover $2n$ place ring with $j$ dominos

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?

-

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, this counts each possible arrangement $j$ times, once for each domino that we could have colored red, so we need to divide $(1)$ by $j$ to get

$$\frac1j\binom{2n-j+1}{j-1}=\frac1{2n-j}\binom{2n-j}j\tag{2}\;.$$

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.

$(2)$ counts the number of circular arrangements of dominoes and uncovered places when the $2n$ places in the ring are considered indistinguishable. If, as is apparently the case here, they are considered distinguishable $-$ if, for instance, they are numbered from $1$ through $2n$ $-$ then each of the circular arrangements counted in $(2)$ actually corresponds to $2n$ different arrangements, one for each of the $2n$ possible starting places around the ring. Thus, to get the actual number of arrangements under this interpretation of the problem we must multiply $(2)$ by $2n$:

$$N_{2n,j} = \frac{2n}{2n -j} \binom{2n-j}{j}\;.$$

-
+1 Thank you for the detailed explanation. – Sasha May 30 '12 at 6:17

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.

-
Thanks for the connection. An algebraic derivation is also in my own answer to the question of "probability of bricks arrange randomly". – Sasha Sep 6 '12 at 19:43
@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! – Byron Schmuland Sep 6 '12 at 19:45