تعداد دنباله های ....

[Olympiad]

فرض کنید a[SUB]n[/SUB] تعداد دنباله های در مبنای دو به طول n باشد که شامل هیچ زیر رشته ی 010 نباشد و b[SUB]n[/SUB] تعداد دنباله های در مبنای دو به طول n باشد که شامل هیچ زیر رشته ی 1100 یا 0011 نباشد . ثابت کنید برای هر عدد طبیعی b[SUB]n+1[/SUB]=2a[SUB]n [/SUB]،n

 

[seifi_seifi]

دنباله ی A را با دنباله ی B متناظر میکنیم به طوری که زیر هر دو عدد کنار هم 0 یا 1 قرار میدهیم اگر دو عدد با هم برابر بودند 0 و اگر متفاوت بودند 1 قرار میدهیم.

به عنوان مثال دنباله ی 110010 با دنباله ی 01011 متناظر است. با این تناظر زیر رشته ی 010 فقط از دو زیر رشته ی 1100 و 0011 تشکیل میشود پس

به ازای هر دنباله به طول n دارای 010 دو دنباله ی متناظر با طول n+1 موجود است.

تعداد دنباله های n+1 تایی شامل 0011 و 1100 دو برابر تعداد دنباله های n تایی شامل 010 است... .

 

[Goharshady]

دوست عزیز خیلی معذرت می خواهم
ولی این رو بهتر نبود تو قسمت ترکیبیات مقدماتی مطرح می کردی؟

 

[mimilad]

پاسخ : تعداد دنباله های ....

این سوال رو با نوشتن دنباله بازگشتی برای هر دو تا نیز میتوان حل کرد . (البته استقرا هم میخواد )