(۰۵ اسفند ۱۳۹۵ ۰۵:۱۰ ب.ظ)ss311 نوشته شده توسط: یک دنباله به طول ۸،ساخته شده از نمادهای {۰و۱و...و۹} خوب نامیده میشود هرگاه شامل تعداد زوجی صفر باشد.تعداد دنباله های خوب به طول ۸ کدام است؟
۱)۸^۱۰
۲)۹^۱۰
۳)(۲/(۸^۸ -۸^۱۰))
۴) (۲/(۸^۸ +۸^۱۰))
برای حالت کلی دنباله های خوب به طول n
به کمک روابط بازگستی اگر تعداد دنباله های خوب به طول n را
an بنامیم رقم اول یا صفراست یا صفر نیست(۹ حالت دیگر)
اگر صفر نباشد مسئله کاهش یافته به طول n-1 داریم یعنی
an−1
اگر صفر باشد پس باید در n-1 مکان دیگر تعداد فرد صفر داشته باشیم که معادل تعداد کل حالت منهای تعداد دنباله های خوب به طول n-1
پس رابطه بازگشتی برابر با
an=9an−1+10n−1−an−1⟹an=8an−1+10n−1
با
a0=1,a1=9 که بعد از حل داریم
an=12(8n+10n)
حال کافیه به جای n مقدار ۸ قرار دهیم که گزینه ۴ حاصل می شود