no two or more seats are adjacent

Question

There are $15$ seats around a table marked as $1,2, 3,\cdots,15.$ The number of ways in which $6$ seats can be selected, such that no two or more are adjacent, is

what i try

no two or more are adjacents $=$ Total -(no adjacents)-(exactly one adjacents)

Total arrangements $=\displaystyle \binom{15}{6}\cdot 6!$

Did not know how do i solve it. Help me please

Answer 1

We will solve the problem for a row first, then subtract those arrangements in which two people will be placed in adjacent seats if we join the ends of the row together to form a circle.

We will arrange nine blue and six green balls. Line up the nine blue balls. This creates ten spaces in which we could place a green ball, eight between successive blue balls and two at the ends of the row.

To separate the green balls, we choose six of these ten spaces in which to insert a green ball, which can be done in $\binom{10}{6}$ ways. For instance, if we choose the first, third, fifth, sixth, eighth, and ninth spaces, we obtain the arrangement shown below.

We now number the balls from left to right. The numbers on the green balls represent the selected seats. Thus, if the seats were arranged in a row, there would be $$\binom{10}{6}$$ ways to select the seats so that no two of them were adjacent.

However, if we had an arrangement such as

when we joined the ends of the row, two of the green balls would be adjacent. We must remove these arrangements. Notice that in selecting arrangements with green balls at both ends of the line, we must select both spaces at the ends of the line and four of the eight spaces between successive blue balls in which to place a green ball. Hence, there are $$\binom{8}{4}$$ such arrangements.

Subtracting these from the total yields $$\binom{10}{6} - \binom{8}{4}$$ selections in which no two of the green balls (seat positions) are adjacent when the balls (seats) are arranged in a circle.

Answer 2

First, let us count the ways to select $6$ seats, and then to paint one of the selected seats red. This will over-count the number of ways to choose the seats by a factor of $6$, so we will need to divide by $6$ in the end.

There are $15$ ways to choose the red seat. Let $x_1$ be the number of empty chairs between the red seat and the next seat in clockwise order, let $x_2$ be the number of chairs between that seat and the next, and so on. These numbers $x_i$ determine the seating selection. They must satisfy $x_i\ge 1$ and $x_1+x_2+\dots+x_6=9$. By stars and bars, the number of ways to solve this is $\binom{9-1}{6-1}$; in a row of $9$ stars, look at the $9-1$ spaces between these stars, and place a bar in $6-1$ of them. The bars divide the stars into $6$ rows. The number of stars in the $i^{th}$ row represents the value of $x_i$.

Therefore, the number of ways to choose $6$ seats and paint one red is $$ 15\times \binom{8}5 $$ We must finally divide $6$ to attain the number of ways to only select the seats: $$ \frac{15}6\binom85. $$