How many ways are there to select 4 people in a round circular table from 15 people sitting on it such that no two people selected are adjacent

combinatorics

I want to know what is wrong with my approach.

I approached the problem like this:
enter image description here

The red circles, are the positions of different people, and the green lines suggest a random selection which agrees with the condition. (ie green lines are selected people).

enter image description here

$x_i$ denotes the gap between two consecutive selections. For the selections to be non consecutive $x_i \geq 1$. There is one – one correspondence between increasing/decreasing the size of the gap and the selections of the people on the table.
counting the number of gaps: it should be $15-5+1=11$.
so now $ x_1 + x_2 + x_3 + x_4 = 11$ and $x_i \geq 1 $, so we just have to find the number of integral solutions for this, and it would correspond to the number of selection.
The above condition is equivalent to the number of integral solutions of:
$ y_1 + y_2 + y_3 + y_4 = 7$, where $y_i \geq 0$

so our answer should be $ 10 \choose 3$ $=120$, but the answer should be $450$, what am i doing wrong?

Best Answer

It's a bit hard to follow your diagrams.

Sticking with what I think is your approach: There are $4$ gaps formed by your four choices, and the lengths of those gaps must sum to $11$. There are $\binom {10}3=120$ ways to populate those gaps with positive natural numbers. There are $15$ choices for the "first" selection. But of course any choice out of the $4$ could have been the "first" one so you are counting each selection $4$ times. Thus the desired result is $$\frac {\binom {10}3\times 15}{4}=450$$

Here's an example to illustrate the idea behind the calculation. Suppose the gap sequence was $\{3,3,3,2\}$. Those sum to $11$ so it's a valid choice. That alone does not give us a choice of four people though, you need to start somewhere. Say $1$ was the first selection. Then use that gap sequence to get the selection $(1,5,9,13)$. However you could have also obtained that selection by starting with $5$ and using the gap sequence $\{3,3,2,3\}$ or by starting with $9$ and using $\{3,2,3,3\}$ or by starting with $13$ and using $\{2,3,3,3\}$. Thus this procedure generates each selection exactly four times, so you must divide by $4$ to correct.

Related Question