Transcription of Solutions to Exercises Chapter 4: Recurrence …
{{id}} {{{paragraph}}}
Example: barber
Solutions to Exercises Chapter 4: Recurrence …
Solutions to ExercisesChapter 4: Recurrence relations and generatingfunctions1(a) There arenseating positions arranged in a line. Prove that the numberof ways of choosing a subset of these positions, with no two chosen positionsconsecutive, isFn+1.(b) If thenpositions are arranged around a circle, show that the number ofchoices isFn+Fn 2forn 2.(a) Proof by induction. Ifg(n)denotes this number, then we haveg(1) =2=F2,g(2) =3=F3. (Forn=2, we cannot occupy both positions; but all otherchoices are possible.) Forn>2, we separate the seating selections into those inwhich the last position is unoccupied and those in which it is occupied.
Solutions to Exercises Chapter 4: Recurrence relations and generating functions 1 (a) There are n seating positions arranged in a line. Prove that the number
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: