توابع مولد معمولی




این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


توابع مولد معمولی
گاهی برای شمارش و حل مسایل ترکیباتی به ابزاری مراجعه می کنیم که تا به حال آنها را در آنالیز ریاضی و ریاضیات پیوسته دیده ایم:
چند جمله ای ها حاصل جمع و حاصل ضرب آنها.
به مثال زیر توجه کنید:
مادری برای فرزندان خود، زهرا، علی و حسن، 12 کتاب می خرد. مادر به چند طریق می تواند کتابها را بین فرزندانش تقسیم کند به طوری که زهرا حداقل چهار کتاب، و علی و حسن هریک حداقل دو کتاب بگیرند،‌ولی حسن بیشتر از پنج کتاب نگیرد؟ در جدول زیر همه حالت های ممکن برای توزیع این کتابها را نوشته ایم.

3 4 5 2 3 4 5 2 2 3 2 2 3 4 زهرا
4 3 2 6 5 4 3 2 3 2 5 4 3 2 علی
5 5 5 4 4 4 4 8 7 7 5 6 6 6 حسن

در واقع این جدول همه ی جواب های صحیح معادله ی است به قسمی که

به یاد می آوریم که در ضرب چند جمله ای ها توانها با هم جمع می شوند. از این ایده استفاده کرده و به جای شمردن جمعها، حاصلضرب را می شمریم. مثلاً برای مساله فوق سه چند جمله‌ای زیر را درهم دیگر ضرب می کنیم و ضریب را که درواقع تعداد حالاتی است که در این حاصل ضرب بوجود می آید در واقع جواب مساله است:
img/daneshnameh_up/1/1e/mco0142a.gif

مثلاً یکی از راههای به دست آمدن در حاصل ضرب فوق همانی است که از چند جمله ای اول،از چند جمله ای دوم و از چند جمله ای سوم در هم ضرب شوند:
در واقع این عبارت را می توان چنین بیان کرد که زهرا 4 کتاب، علی 3 کتاب و حسن 5 کتاب دریافت کنند.
پرانتز سمت راست یعنی چنین بیان می کند که علی می تواند 2،3،4یا 5 کتاب بگیرد. دو پرانتز دیگر نیز به همین ترتیب.
اما چنین راه حلی برای این مساله که روش های ترکیبیاتی راحت تر حل می شود شاید به نظرتان عجیب و مانند پیچاندن لقمه به دور سر باشد. البته حق با شماست ولی در مسایل دیگر ولی مشکلتر در واقع این توابع به کار ما می آیند. و کار ما را آسانتر می کنند و این مثال را صرفاً برای تعریف توابع مولد آوردیم.
در واقع تابع دربالا تابع مولد مثال فوق است.
تعریف فرض کنیم دنباله ای از اعداد حقیقی باشند. تابع

را تابع مولد دنباله ی مفروض می نامیم.
اگر و به ترتیب توابع مو لد دنباله های باشند، آنگاه اگر و تنها اگر یعنی برای هر ،‌ .
هم چنین روابط جبری زیر مانند اعداد برای توابع مولد نیز برقرارند ( در واقع این روابط برای هر چند جمله ای تعریف شده اند.):

و

و اگر عددی حقیقی باشد.



در این فصل بهترین روش برای آشنایی با توابع مولد،‌مشاهده ی مثال های متفاوت و پیدا کردن توابع مختلف می باشد.

مثال

به ازای ،

یعنی تابع مولد برای دنباله ی

می باشد.

مثال

به ازای،

بنابراین، و در نتیجه تابع تابع مولد برای دنباله یimg/daneshnameh_up/f/f8/mco0142b.gif می باشد. با تعمیم این مساله ی می بینیم که

برای درک بهتر این مساله 1 را بر تقسیم کنید. در نتیجه تابع مولد دنباله ی عبارت است از. حال از دو طرف تساویمشتق می گیریم (‌ اگر تا کنون مشتق تابع را نیاموخته اید لزومی ندارد بقیه ی این مثال را بخوانید. ) حاصل مشتق گیری از دو طرف عبارت است از تساوی زیر:

پس تابع مولد دنباله یعبارت است از تابع

حال دوباره از عبارت مشتق می گیریم. خواهیم داشت:

پس تابع ، تابع مولد دنباله ی می باشد.

مثال

اگر دنباله ی مورد نظر ما تفاوت های جزیی با برخی دنباله هایی که ما توابع مولدشان را می شناسیم داشته باشد. تابع مولد آن نیز با تغییرات جزیی بر روی تابع مولد دنباله ی مشابه اش به دست می آید. به مثال های زیر توجه کنید:

مثال



تابع مولد چیست؟ می دانیم تابع مولد است. از آنجا که تنها تفاوت دو دنباله ی مذکور در عنصر سوم آنها از سمت چپ است. با صفر کردن ضریب در تابع ، تابع مولد مجهول را می یابیم. برای این کار کافیست را از کم کنیم. یعنی تابع ، تابع مولد دنباله ی می باشد.
هم چنین به همین صورت می توان دید که تابععبارت است از تابع مولد دنباله ی :.
مثال. تابع تابع مولد دنباله ی می باشد. چرا که تابع مولد دنباله ی و در نتیجه تابع مولد دنباله ی است. ( چرا؟ )‌
نیز تابع مولد دنباله ی از طرفی در دنباله ی، هر برابر است باپس تابع مولد دنباله ی عبارت است از :

اکنون فنونی را می آموزیم که کاربرد توابع مولد را در حل مسایل شمارش بیشتر نمایانی می کند.

قضیه

الف. فرض کنیم ضریب در باشد. آنگاه.
ب.
پ.
اثبات
الف. تابع عبارت است از تابع مولد وابسته به مساله ترکیباتی ای که در پی یافتن، جواب های صحیح نامنفی معادله ی است که با حل آن آشنا هستید.
و تعداد جواب ها برابر است با.
ب‌. در بسط دو جمله ای به جای قرار می دهیم یعنی


و

پ. با محاسبه ی تقسیمخواهیم داشت:

حال با به توان رساندن دو طرف این قسمت از قضیه نیز اثبات می گردد.

مثال

مطلوب است تعداد جواب های صحیح و نامنفی معادله ی به طوری که هر متغیر حداقل 3 و حداکثر 8 باشد.
حل
تعداد جواب ها عبارت است از ضریب در تابع چند جمله ای و این عدد عبارت است از ضریب در . ( چرا؟ ) بنابر قسمت (پ) ی قضیه ی قبل

و (ب) ی همان قضیه
و از (الف) آن قضیه خواهیم داشت
پس ضریب در عبارت است از



قضیه ی زیر تعمیم برخی مثالهایی است که در پیش آورده ایم. اثبات آنها را به عنوان تمرین بر عهده خواننده می گذاریم:

قضیه

اگر تابع مولد دنباله ی تابع مولد باشند، آنگاه:
الف. تابع مولد است. ( و عددند و )
ب. تابع مولد است.
پ. تابع مولد می باشد.
ت. تابع مولد است.
ث. ، که در آن مشتق نسبت به است، تابع مولداست.
در اولین مثال مشاهده کردیم که اگر عددی طبیعی باشد آنگاه تابع مولد دنباله می باشد. اگر کمی آنالیز ریاضی ( مبحث مربوط به حساب دیفرانسیل و انتگرال ) بدانیم می توان اثبات کرد که اگر عددی حقیقی باشد آنگاه

هر گاه عددی طبیعی باشد، ضریب از جایی به بعد صفر می شود ولی اگر طبیعی نباشد ضرایب نامتناهی اند یعنی سری نامتناهی است- حال می توان با کمک این تابع مولد را تعمیم داد. یعنی به جای عدد طبیعی، عدد حقیقیرا قرار می دهیم و تعریف می کنیم:
اگر عددی حقیقی و عددی طبیعی باشند.


یعنی خواهیم داشت:


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0051.pdf




تعداد بازدید ها: 33176