# Forks and holes

There are $n$ holes in line at a distance $1 cm$. We have forks with $2$ tines at the same distance.

a) how many ways to plug $k$ such forks?

b) what changes if the holes are in the circle?

-
This has little to do with probability. I've retagged it. – Rick Decker Nov 5 '12 at 16:55

For the first question you want the number of ways to pick $k$ non-overlapping pairs of adjacent integers from the set $\{1,2,\dots,n\}$; call this number $f(n,k)$. I’ll show you two approaches, because I didn’t see the nicer one until I’d written up most of the more straightforward one.

Suppose that the leftmost pair chosen is $\{i,i+1\}$; then the other $k-1$ pairs must be chosen from the set $\{i+2,\dots,n\}$, something that can be done in $f(n-i-1,k-1)$ ways. Thus,

$$f(n,k)=\sum_{i=1}^{n-1}f(n-i-1,k-1)=\sum_{i=1}^{n-2}f(i,k-1)\;.\tag{1}$$

Clearly $f(n,k)=0$ if $n<2k$, and it’s not hard to see that $f(n,1)=n-1$ for all $n\ge 1$.

$(1)$ then implies that

$$f(n,2)=\sum_{i=1}^{n-2}f(i,1)=\sum_{i=1}^{n-2}(i-1)=\sum_{i=0}^{n-3}i=\frac{(n-3)(n-2)}2=\binom{n-2}2\;,$$ and then that

$$f(n,3)=\sum_{i=1}^{n-2}f(i,2)=\sum_{i=2}^{n-2}\binom{i-2}2=\sum_{i=0}^{n-4}\binom{i}2=\binom{n-3}3$$ by a standard binomial coefficient identity. Since $n-1=\binom{n-1}1$, this suggests the conjecture that

$$f(n,k)=\binom{n-k}k\;.\tag{2}$$

At this point it’s easy enough to prove $(2)$ by induction on $k$, using the same binomial coefficient identity.

Alternatively, we can give a combinatorial proof of $(2)$ that could have solved the problem right away. Imagine that we’ve placed $k$ forks. They define $k+1$ slots where other holes could be: $k-1$ slots between adjacent forks, and one on each end. We’ve used up $2k$ holes, so there are $n-2k$ holes left, and they can be distributed amongst the $k+1$ slots in any fashion. This is a standard stars-and-bars problem, and the number of distributions is $$\binom{(n-2k)+(k+1)-1}{(k+1)-1}=\binom{n-k}k\;.$$

If the holes are in a circle, there are only $k$ slots between the forks, since the ends now wrap around; I’ll leave you to work out how that affects the result.

-
there is more elegant and optimal answer - with no induction – Xxx Nov 13 '12 at 14:22
@Xxx: Did you actually read the entire answer? I gave a simple answer that does not use induction (as well as one that does). – Brian M. Scott Nov 13 '12 at 19:32
yes, I've seen the alternative version, thank You for the help! – Xxx Nov 13 '12 at 21:22
@Xxx: You’re welcome. – Brian M. Scott Nov 13 '12 at 23:40
Sorry, but could You explain this one more time: They define k+1 slots where other holes could be: k−1 slots between adjacent forks, and one on each end – Xxx Nov 14 '12 at 1:12

Hint: pick a hole for the first fork. How many ways can you do that? Then that one is full, how many ways to pick the hole for the second? But you have counted each arrangement twice, because you could have picked the holes in the other order.

For the second, all the holes are equivalent for the first fork. Also there are equivalent holes for the second.

-