این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت 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
حسن
در واقع این جدول همه ی جواب های صحیح معادله ی است به قسمی که
به یاد می آوریم که در ضرب چند جمله ای ها توانها با هم جمع می شوند. از این ایده استفاده کرده و به جای شمردن جمعها، حاصلضرب را می شمریم. مثلاً برای مساله فوق سه چند جمله‌ای زیر را درهم دیگر ضرب می کنیم و ضریب را که درواقع تعداد حالاتی است که در این حاصل ضرب بوجود می آید در واقع جواب مساله است:
مثلاً یکی از راههای به دست آمدن در حاصل ضرب فوق همانی است که از چند جمله ای اول،از چند جمله ای دوم و از چند جمله ای سوم در هم ضرب شوند: در واقع این عبارت را می توان چنین بیان کرد که زهرا 4 کتاب، علی 3 کتاب و حسن 5 کتاب دریافت کنند.
پرانتز سمت راست یعنی چنین بیان می کند که علی می تواند 2،3،4یا 5 کتاب بگیرد. دو پرانتز دیگر نیز به همین ترتیب.
اما چنین راه حلی برای این مساله که روش های ترکیبیاتی راحت تر حل می شود شاید به نظرتان عجیب و مانند پیچاندن لقمه به دور سر باشد. البته حق با شماست ولی در مسایل دیگر ولی مشکلتر در واقع این توابع به کار ما می آیند. و کار ما را آسانتر می کنند و این مثال را صرفاً برای تعریف توابع مولد آوردیم.
در واقع تابع دربالا تابع مولد مثال فوق است.
تعریف فرض کنیم دنباله ای از اعداد حقیقی باشند. تابع
را تابع مولد دنباله ی مفروض می نامیم.
اگر و به ترتیب توابع مو لد دنباله های باشند، آنگاه اگر و تنها اگر یعنی برای هر ، .
هم چنین روابط جبری زیر مانند اعداد برای توابع مولد نیز برقرارند ( در واقع این روابط برای هر چند جمله ای تعریف شده اند.):
و
و اگر عددی حقیقی باشد.
در این فصل بهترین روش برای آشنایی با توابع مولد،مشاهده ی مثال های متفاوت و پیدا کردن توابع مختلف می باشد.
بنابراین، و در نتیجه تابع تابع مولد برای دنباله ی می باشد. با تعمیم این مساله ی می بینیم که
برای درک بهتر این مساله 1 را بر تقسیم کنید. در نتیجه تابع مولد دنباله ی عبارت است از. حال از دو طرف تساویمشتق می گیریم ( اگر تا کنون مشتق تابع را نیاموخته اید لزومی ندارد بقیه ی این مثال را بخوانید. ) حاصل مشتق گیری از دو طرف عبارت است از تساوی زیر:
اگر دنباله ی مورد نظر ما تفاوت های جزیی با برخی دنباله هایی که ما توابع مولدشان را می شناسیم داشته باشد. تابع مولد آن نیز با تغییرات جزیی بر روی تابع مولد دنباله ی مشابه اش به دست می آید. به مثال های زیر توجه کنید:
تابع مولد چیست؟ می دانیم تابع مولد است. از آنجا که تنها تفاوت دو دنباله ی مذکور در عنصر سوم آنها از سمت چپ است. با صفر کردن ضریب در تابع ، تابع مولد مجهول را می یابیم. برای این کار کافیست را از کم کنیم. یعنی تابع ، تابع مولد دنباله ی می باشد.
هم چنین به همین صورت می توان دید که تابععبارت است از تابع مولد دنباله ی :.
مثال. تابع تابع مولد دنباله ی می باشد. چرا که تابع مولد دنباله ی و در نتیجه تابع مولد دنباله ی است. ( چرا؟ )
نیز تابع مولد دنباله ی از طرفی در دنباله ی، هر برابر است باپس تابع مولد دنباله ی عبارت است از :
اکنون فنونی را می آموزیم که کاربرد توابع مولد را در حل مسایل شمارش بیشتر نمایانی می کند.
الف. فرض کنیم ضریب در باشد. آنگاه.
ب. پ. اثبات الف. تابع عبارت است از تابع مولد وابسته به مساله ترکیباتی ای که در پی یافتن، جواب های صحیح نامنفی معادله ی است که با حل آن آشنا هستید.
و تعداد جواب ها برابر است با.
ب. در بسط دو جمله ای به جای قرار می دهیم یعنی
و
پ. با محاسبه ی تقسیمخواهیم داشت:
حال با به توان رساندن دو طرف این قسمت از قضیه نیز اثبات می گردد.
مطلوب است تعداد جواب های صحیح و نامنفی معادله ی به طوری که هر متغیر حداقل 3 و حداکثر 8 باشد.
حل تعداد جواب ها عبارت است از ضریب در تابع چند جمله ای و این عدد عبارت است از ضریب در . ( چرا؟ ) بنابر قسمت (پ) ی قضیه ی قبل
و (ب) ی همان قضیه و از (الف) آن قضیه خواهیم داشت پس ضریب در عبارت است از
قضیه ی زیر تعمیم برخی مثالهایی است که در پیش آورده ایم. اثبات آنها را به عنوان تمرین بر عهده خواننده می گذاریم:
اگر تابع مولد دنباله ی تابع مولد باشند، آنگاه:
الف. تابع مولد است. ( و عددند و )
ب. تابع مولد است.
پ. تابع مولد می باشد.
ت. تابع مولد است.
ث. ، که در آن مشتق نسبت به است، تابع مولداست.
در اولین مثال مشاهده کردیم که اگر عددی طبیعی باشد آنگاه تابع مولد دنباله می باشد. اگر کمی آنالیز ریاضی ( مبحث مربوط به حساب دیفرانسیل و انتگرال ) بدانیم می توان اثبات کرد که اگر عددی حقیقی باشد آنگاه
هر گاه عددی طبیعی باشد، ضریب از جایی به بعد صفر می شود ولی اگر طبیعی نباشد ضرایب نامتناهی اند یعنی سری نامتناهی است- حال می توان با کمک این تابع مولد را تعمیم داد. یعنی به جای عدد طبیعی، عدد حقیقیرا قرار می دهیم و تعریف می کنیم:
اگر عددی حقیقی و عددی طبیعی باشند.
از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..
وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران رشد
است به قسمی که
ها، حاصلضرب 
را می شمریم. مثلاً برای مساله فوق سه چند جمله‌ای زیر را درهم دیگر ضرب می کنیم و ضریب 
را که درواقع تعداد حالاتی است که 
از چند جمله ای اول،
از چند جمله ای دوم و 
از چند جمله ای سوم در هم ضرب شوند:
چنین بیان می کند که علی می تواند 2،3،4یا 5 کتاب بگیرد. دو پرانتز دیگر نیز به همین ترتیب.
دربالا تابع مولد مثال فوق است.
دنباله ای از اعداد حقیقی باشند. تابع
و
به ترتیب توابع مو لد دنباله های
باشند، آنگاه
اگر و تنها اگر
یعنی برای هر 
، 
.
عددی حقیقی باشد.
تابع مولد برای دنباله ی
،
و در نتیجه تابع 
تابع مولد برای دنباله ی
می باشد. با تعمیم این مساله ی می بینیم که
تقسیم کنید. در نتیجه تابع مولد دنباله ی 
عبارت است از
. حال از دو طرف تساوی
مشتق می گیریم ( اگر تا کنون مشتق تابع را نیاموخته اید لزومی ندارد بقیه ی این مثال را بخوانید. ) حاصل مشتق گیری از دو طرف عبارت است از تساوی زیر:
عبارت است از تابع
مشتق می گیریم. خواهیم داشت:
، تابع مولد دنباله ی 
می باشد.
چیست؟ می دانیم 
تابع مولد 
است. از آنجا که تنها تفاوت دو دنباله ی مذکور در عنصر سوم آنها از سمت چپ است. با صفر کردن ضریب 
، تابع مولد دنباله ی 
عبارت است از تابع مولد دنباله ی :
.
تابع مولد دنباله ی 
می باشد. چرا که
تابع مولد دنباله ی
و در نتیجه
تابع مولد دنباله ی
است. ( چرا؟ )
از طرفی در دنباله ی
، هر 
برابر است با
پس تابع مولد دنباله ی 
ضریب 
در
باشد. آنگاه
.
است که با حل آن آشنا هستید.
.
به جای 
قرار می دهیم 
یعنی
خواهیم داشت:
به طوری که هر متغیر حداقل 3 و حداکثر 8 باشد.
در تابع چند جمله ای 
و این عدد عبارت است از ضریب
در 
. ( چرا؟ ) بنابر قسمت (پ) ی قضیه ی قبل
عبارت است از
تابع مولد دنباله ی
تابع مولد
باشند، آنگاه:
تابع مولد
است. ( 
و 
عددند و
)
تابع مولد
است.
تابع مولد
می باشد.
تابع مولد
است.
، که در آن
مشتق 
است، تابع مولد
است.
تابع مولد دنباله 
می باشد. اگر کمی آنالیز ریاضی ( مبحث مربوط به حساب دیفرانسیل و انتگرال ) بدانیم می توان اثبات کرد که اگر 
عددی حقیقی باشد آنگاه
از جایی به بعد صفر می شود ولی اگر 
را تعمیم داد. یعنی به جای عدد طبیعی
عددی طبیعی باشند.
