In how many ways are we able to arrange $k$ identical non-overlapping dominoes on a circle of $2n$ labelled vertices?
The problem can be reduced to the number of ways to choose $k$ non-consecutive vertices from the $2n$ labelled vertices,and now there are two cases,assuming we are arranging these $k$ identical dominoes counterclockwise:
-
If vertex $1$ in included,then the adjacent vertex (from the left) cannot be chosen,since the dominoes are non-overlopping,so we are left with the other $2n-2$ vertices and we want to choose $k-1$ nonconsecutive vertices ,this can be done in $\binom{2n-2-(k-1)+1}{k-1}=\binom{2n-k}{k-1}$ ways.
-
If vertex $1$ in not included,so we are left with the other $2n-1$ vertices and we want to choose $k$ nonconsecutive vertices ,this can be done in $\binom{2n-1-k+1}{k}=\binom{2n-k}{k}$ ways.
Now summing these two cases gives the answer.
I'm not sure about the proof,besides dos it make difference if we do the process clockwise?
Best Answer
You appear to be off a bit: in your first case $3$ vertices are unavailable, not $2$.
I’ve numbered the vertices from $1$ through $2n$. For my first case I put a domino on vertices $1$ and $2$. Now I need to choose $k-1$ of the $2n-3$ vertices $3,4,\ldots,2n-1$, ensuring that no two chosen vertices are adjacent. This can be done in
$$\binom{(2n-3)-(k-2)}{k-1}=\binom{2n-1-k}{k-1}$$
ways.
For my second case I put a domino on vertices $2n$ and $1$; the analysis is the same, so we get another $\binom{2n-1-k}{k-1}$ arrangements.
Any other arrangement must avoid vertex $1$ entirely. In that case we need to choose $k$ of the $2n-2$ vertices $2,3,\ldots,2n-1$, ensuring that no two chosen vertices are adjacent. This can be done in
$$\binom{(2n-2)-(k-1)}k=\binom{2n-1-k}k$$
ways. I get a total of
$$2\binom{2n-1-k}{k-1}+\binom{2n-1-k}k=\binom{2n-1-k}{k-1}+\binom{2n-k}k$$
arrangements. I’ve checked this by hand with $n=4$ and $k=3$.