مسئله ی پیکارجوی ترکیبیات

[Goharshady]

تو کتابی که من ازش نقل می کنم نوشته بود پیکارجو ولی به نظر من پیکارجو نیست وگرنه تو ترکیبیات ممتاز مطرحش می کردم.
این هم سوال:

چند دنباله به طول n از اعداد 0و1و2و3 وجود دارد با این شرط که هرکدام شامل تعداد زوجی 0 و تعداد فردی 1 باشد؟ (روی تعداد 2ها و 3ها شرطی نداریم).


منبع: مسائل برگزیده ریاضی از سراسر دنیا ، راس هانسبرگر ترجمه ی امیر آجرلو

 

[Goharshady]

راهنمایی: 3 مقدار بازگشتی متفاوت در نظر بگیرید و آنها را به هم مرتبط نمایید.

 

[Goharshady]

تو کتابی که من ازش نقل می کنم نوشته بود پیکارجو ولی به نظر من پیکارجو نیست وگرنه تو ترکیبیات ممتاز مطرحش می کردم.
این هم سوال:

چند دنباله به طول n از اعداد 0و1و2و3 وجود دارد با این شرط که هرکدام شامل تعداد زوجی 0 و تعداد فردی 1 باشد؟ (روی تعداد 2ها و 3ها شرطی نداریم).


منبع: مسائل برگزیده ریاضی از سراسر دنیا ، راس هانسبرگر ترجمه ی امیر آجرلو

فکر کنم واقعا پیکارجو بوده!!!

پاسخ: تعداد این دنباله ها به صورت بدیهی برابر است با تعداد دنباله هایی که تعداد زوجی 1 و تعداد فردی 0 دارند.(چرا؟) این تعداد را با a[SUB]n[/SUB] نشان می دهیم. همچنین دنباله هایی که تعداد زوجی 1 و تعداد زوجی 0 داشته باشند را با b[SUB]n[/SUB] نشان می دهیم و c[SUB]n[/SUB] تعداد دنباله هایی است که تعداد فردی 1 و تعداد فردی 0 داشته باشند. 3 رابطه ی زیر بدیهی است:

[center:6518610ffe]

[/center:6518610ffe]

حال همه ی دنباله های n رقمی را در نظر بگیرید. می دانیم که تعداد آنها 4[SUP]n[/SUP] است.​

از طرفی:​

• یا تعداد زوجی صفر و تعداد فردی یک دارند : an
• یا تعداد فردی یک و تعداد زوجی صفر دارند: an
• یا تعداد زوجی صفر و تعداد زوجی یک دارند : bn
• یا تعداد فردی صفر و تعداد فردی یک دارند: cn

پس :

با استفاده از 3 رابطه ی بازگشتی بالا داریم:
[center:6518610ffe]

[/center:6518610ffe]

از تفریق دو رابطه به دست می آید:​

[center:6518610ffe]

[/center:6518610ffe]​