2
$\begingroup$

I've been stuck on this problem: How many ways can you place n identical items in k spots(with k>2n-1) so that none of the items are next to another item (not all of the items need to be placed).

I tried using inclusion-exclusion on this but I couldn't figure out how to make it work.

Reading this again my wording was off - I've changed the problem phrasing so that it is clearer.

2 Answers 2

2

Turn the problem around: imagine that the $n$ people are sitting in a row, and we’re to distribute $k-n$ seats in the row in such a way that there is at least one seat in each gap between two adjacent people. There are $n-1$ gaps between the people, and we can also put seats on the ends, so we’re distributing $k-n$ seats in $n+2$ slots with the restriction that the middle $n-1$ slots must each get at least one seat. Of course this means that $k-n$ must be at least $n-1$, so $k\ge 2n-1$.

Start by putting one seat in each of the $n-1$ gaps between people; that leaves us with $k-n-(n-1)=k-2n+1$ seats that can be freely distributed amongst the $n+1$ slots. This is a standard stars-and-bars problem, whose solution is

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

  • 0
    @Marc: I think that you make it sound a bit more involved than it really is: it’s just an easy reduction of the problem to a solved problem.2012-08-28
1

Supposing you are only interested in the set of occupied seats, proceed as follows. Seat the $n$ people on an $n$-subset of the first $k-(n-1)$ seats without restriction, for $\binom{k-n+1}n$ possibilities. Now ask everyone to move ahead in the row as many places are there are people before them (the first person stays seated, the next moves one place, the next two places, etc.). Since the last person moves $n-1$ places, she won't fall off the end of the row, and nobody will end up next to another. The procedure is reversible from a seating arrangement without neigbours, so $\binom{k-n+1}n$ is the answer.

  • 0
    van Leewen:I deleted my answer.thanks2012-08-28