Number of ways to sit students in a row and so that no 2 students sat directly adjacent

combinatoricsdiscrete mathematics

From Susanna Epp's book:

A row in a classroom has $n$ seats. Let $s_n$ be the number of ways
nonempty sets of students can sit in the row so that no student is
seated directly adjacent to any other student. (For instance, a row of
three seats could contain a single student in any of the seats or a
pair of students in the two outer seats. Thus $s_3 = 4$.) Find a
recurrence relation for $s_1, s_2, s_3, …$

Here're the arrangements for rows from 1 to 5:

$s_1=1$ (1 way to place 1 student)

$s_2=2$ (2 ways to place 1 student)

$s_3=4$ (3 ways to place 1 student, 1 way to place 2 students)

$s_4=7=4+2+1=1+s_3+s_2$ (4 ways to place 1 student, 3 ways to place 2 students)

$s_5=12=7+4+1=1+s_4+s_3$ (5 ways to place 1 student, 6 ways to place 2 students, 1 way to place 3 students)

The pattern is clear: $s_n=1+s_{n-1}+s_{n-2}$ So the set of all arrangements of students in the current row can be partitioned to 3 subsets:

  1. some one one way to do something
  2. the number of ways to sit students in a row 1 sits less
  3. the number of ways to sit students in a row 2 sits less

Why does the partition looks like this? What is 1 and why $s_{n-1}$ and $s_{n-2}$?

Best Answer

If seat #$n$ is occupied, then either the first $n-2$ seats are occupied in some admissible way, or they are all empty (the "$+1$").

If seat #$n$ is empty, then you have an admissible arrangement in seats in the first $n-1$ seats.

Related Question