به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+3 امتیاز
83 بازدید
سوال شده در دبیرستان توسط Taha1381

اگر $f_n$ برابر تعداد کلمات متشکل از $a,b,c$ به طول $n$ باشد که از هر سه حرف متوالی حداقل دو تا یکسانند رابطه بازگشتی برای $f_n$ بیابید

1 پاسخ

+3 امتیاز
پاسخ داده شده توسط amirabbas
انتخاب شده توسط Taha1381
 
بهترین پاسخ

به محاسبه $f_n$ می پردازیم. در $f_n$ یک جایگاه به جایگاه های $f_{n-1}$ اضافه می شود که سه انتخاب در آن داریم پس تعداد کل حالت ها برابر با $3f_{n-1}$ است.اما برخی از این حالت ها مورد قبول ما نخواهد بود این حالت ها را محاسبه می کنیم. حالتی که دو حرف پایانی $f_{n-1}$ یکسان باشد مستقل از حرفی که در جایگاه جدید قرار می دهیم مورد قبول ما است. پس حالتی مشکل ساز است که دو حرف پایانی $f_{n-1}$ متفاوت باشند. اگر دو حرف پایانی متفاوت باشند به ازای یک انتخاب در جایگاه جدید به حالتی نامطلوب خواهیم رسید. با در نظر گرفتن این تناظر می توان گفت تعداد حالاتی که باید از $3f_{n-1}$ کم کنیم با تعداد $f_{n-1}$ هایی که دو حرف پایانی آن ها متفاوت است برابر است.که برای محاسبه اینها هم می توان تعداد حالاتی از $f_{n-1}$ که دو حرف پایانی آن ها یکسان است را از کل $f_{n-1}$ کم کرد. اگر به $f_{n-2}$ جایگاهی جدید اضافه کنیم به ازای یک حالت در این جایگاه جدید دو حرف پایانی $f_{n-1}$ یکسان می شود. بنابراین:

$$ f_n = 3f_{n-1}-(f_{n-1} - f_{n-2}) = 2f_{n-1} + f_{n-2} $$

همچنین می دانیم $f_1 = 3$ و $f_2 = 9$

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...