Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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}\;.$$

share|improve this answer
    
+1 Thank you for the detailed explanation. –  Sasha May 30 '12 at 6:17
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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