1
$\begingroup$

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}$?

$\endgroup$
2
  • $\begingroup$ Your argument for s_3 is incorrect. $\endgroup$ May 21, 2020 at 21:10
  • 1
    $\begingroup$ @MohammadZuhairKhan Right, and the relation too, both fixed. $\endgroup$
    – super.t
    May 21, 2020 at 21:18

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Also note that these numbers $1,2,4,7,12, ...$ are one less than the Fibonacci numbers (index translated by one or two, depending on how you index your Fibonacci's), so if you allowed the empty arrangement, you'd just get the Fibonacci numbers -- and the explanation for the recursive equation (without the "$+1$") would would be the same as in this answer. $\endgroup$
    – Ned
    May 22, 2020 at 2:27
  • $\begingroup$ makes perfect sense, thank you $\endgroup$
    – super.t
    May 22, 2020 at 7:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .