تابع مولد

این مقاله دربارهٔ توابع مواد در ریاضیات است. برای توابع مولد در فیزیک کلاسیک، توابع مولد در فیزیک را ببینید. برای توابع مولد در برنامه‌نویسی کامپیوتر، توابع مولد در برنامه‌نویسی کامپیوتر را ببینید.

در ریاضیات تابع مولد یک سری توانی است که ضرایب آن اطلاعاتی در مورد دنبالهٔ فرضی a_n (با اندیس‌های طبیعی) را در خود رمز می‌کنند. توابع مولد برای اولین بار توسط ابراهام دو مواور استفاده شدند. در واقع توابع مولد بسیار قدرتمند هستند و می‌توان از آن‌ها برای رمزگذاری اطلاعات در مورد آرایه‌ای از اعداد فهرست شده توسط اعداد طبیعی استفاده کرد.

توابع مولد دارای انواع مختلفی مانند توابع مولد معمولی، توابع مولد نمایی، سری‌های لمبرت، سری‌های بل و سری دیریکله می‌باشند که در ادامه برای هر یک تعریف و مثال‌هایی ارائه داده می‌شود. هر دنباله در اصل یک تابع مولد از هر نوع دارد (به جز سری‌های لمبرت و دیریکله که از اندیس یکم شروع می‌شوند، بقیه انواع از اندیس صفرم شروع می‌شوند) و بسته به نوع تابع می‌توان از تابع مولد مناسب استفاده کرد. توابع مولد اغلب به صورت یک فرم بسته (به جای یک سری) ارائه می‌شوند. گاهی یک تابع مولد با یک مقدار خاص x مقداردهی می‌شود. به هر حال، باید توجه داشت که توابع مولد سری‌هایی توانی هستند و لازم نیست که برای همهٔ مقادیر x رفتار مشابهی داشته باشند.

توابع مولد به‌طور کلی در فرم توابع معمولی که به صورت نگاشتی از دامنه به برد است، نیستند و این نام نیز صرفاً به صورت سنتی بر روی آن‌ها بوده و بهتر است به جای توابع مولد از واژه سری‌های مولد استفاده کنیم.

تعاریف

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

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

${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$

وقتی از واژهٔ تابع مولد استفاده می‌شود عموماً منظور همان تابع مولد معمولی است. اگر a_n تابع احتمالی وزن دار از یک متغیر تصادفی گسسته باشد آنگاه تابع مولد معمولی اش، تابع مولد احتمال نامیده می‌شود.

تابع مولد معمولی می‌تواند به دنباله‌هایی با اندیس‌های چند گانه تعمیم بیابند برای مثال تابع مولد دنباله ی${\displaystyle a_{m,n}}$(که mوn اعداد طبیعی اند) عبارتست از

${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}}$

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

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

${\displaystyle EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}$

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

تابع مولد پوآسن

تابع مولد پوآسن دنبالهٔ a_n به صورت زیر است:

${\displaystyle \operatorname {PG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}e^{-x}{\frac {x^{n}}{n!}}=e^{-x}\,\operatorname {EG} (a_{n};x).}$

سریهای لمبرت

سریهای لمبرت دنبالهٔ a_n عبارتست از

${\displaystyle \operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.}$

توجه کنید اندیس a_nدر سری‌های لمبرت بایک شروع می‌شود (نه باصفر)

سری‌های بل

سری بل یک متغیر x و یک عدد اولP عبارتست از

${\displaystyle \operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.}$

توابع مولد سری‌های دیریکله

سری دیریکله هرچند کاملاً یک سری توانی نیست اما اغلب به عنوان تابع مولد طبقه‌بندی می‌شود. سری دریکله دنبالهٔ a_n عبارتست از

${\displaystyle \operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.}$

تابع مولد سری دیریکله زمانی که an یک تابع حاصل ضربی باشد بسیار مفید است. زمانی که a_n بسط حاصلضرب اولر باشد داریم:

${\displaystyle \operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,.}$

اگر an یک کاراکتر دیریکله باشد آنگاه تابع مولد سری دیریکله آن یک سری L دیریکله می‌شود.

توابع مولد دنباله‌های چندجمله‌ای

ایده توابع مولد قابل بسط دادن به سایر دنباله‌ها می‌باشد. به عنوان مثال دنباله چندجمله‌ای‌های شامل دوجمله (دنباله دوجمله ای) توسط تابع مولد زیر تولید شده است:

${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}}$

که در آن (p_n(x یک دنباله از چندجمله‌ای‌ها بوده و یک تابع خاص می‌باشد. دنباله نیز به همین ترتیب ساخته شده است. برای اطلاعات بیشتر از چندجمله‌ای‌های تعمیم یافته Appell استفاده کنید.

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

چندجمله‌ای هایک حالت خاص از توابع مولد معمولی می‌باشند که مربوط به دنباله‌های محدود یا دنباله‌های نامحدود می‌باشند. این نکته مهم است که دنباله‌های محدود می‌توانند به عنوان توابع مولد تفسیر شوند مانند Poincaré polynomial و غیره. دنباله ثابت ۱, ۱, ۱, ۱, ۱, ۱, ۱, ۱, ۱, … یکی از کلیدی‌ترین دنباله‌ها در بحث توابع مولد می‌باشد. تابع مولد معمولی این دنباله عبارت است از:

${\displaystyle \sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}.}$

عبارت سمت چپ بسط سری مکلورن عبارت سمت راست می‌باشد. عبارت سمت راست می‌تواند با ضرب سری توانی ۱ − x از سمت چپ و بررسی اینکه نتیجه با سری توانی تابع ثابت ۱ برابر باشد به دست آید. به عبارت دیگر تمامی ضرایب به غیر از ضریب x⁰ برابر صفر می‌شوند. علاوه بر این سری توانی دیگری با این خاصیت وجود ندارد؛ بنابراین سمت چپ می‌تواند توسط ضرب معکوس ۱ − x در حلقه سری توانی تعیین شود. عبارت تابع مولد معمولی برای بقیه دنباله‌ها به راحتی می‌تواند از این مورد به‌دست بیاید. به عنوان مثال جایگزین کردن x → ax تابع مولد تصاعد هندسی 1, a, a², a³, … برای یک ثابت a به‌دست می‌آید:

${\displaystyle \sum _{n=0}^{\infty }(ax)^{n}={\frac {1}{1-ax}}.}$

این تساوی هم چنین به‌طور مستقیم از این واقعیت که سمت چپ بسط سری مکلورن سمت راست است نتیجه می‌شود. داریم:

${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}x^{n}={\frac {1}{1+x}}.}$

همچنین می‌توان x را با توان‌های بالاتری از x تعویض کرد. برای مثال برای دنباله۱, ۰, ۱, ۰, ۱, ۰, ۱, ۰, .... می‌توان تابع مولد زیر را در نظر گرفت:

${\displaystyle \sum _{n=0}^{\infty }x^{2n}={\frac {1}{1-x^{2}}}.}$

با مربع کردن مقادیر در تابع اولیه یا با به‌دست آوردن مشتق نسبت بهx از دو طرف عبارت و تغییر دادن متغیرn → n-1 می‌توان ضرایب دنباله ۱, ۲, ۳, ۴, ۵, … , را ساخت:

${\displaystyle \sum _{n=0}^{\infty }(n+1)x^{n}={\frac {1}{(1-x)^{2}}},}$

و توان سوم آن به فرم اعداد مثلثی ۱, ۳, ۶, ۱۰, ۱۵, ۲۱, … می‌باشد که در آن n ضرایب دو جمله ای${\displaystyle {\tbinom {n+2}{2}}}$ است. پس داریم:

${\displaystyle \sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{n}={\frac {1}{(1-x)^{3}}}.}$

به‌طور کلی می‌توان این قضیه را برای هر k مثبتی تعمیم داد:

${\displaystyle \sum _{n=0}^{\infty }{\binom {n+k}{k}}x^{n}={\frac {1}{(1-x)^{k+1}}}.}$

توجه کنید که:

${\displaystyle 2{\binom {n+2}{2}}-3{\binom {n+1}{1}}+{\binom {n}{0}}=2{\frac {(n+1)(n+2)}{2}}-3(n+1)+1=n^{2},}$

می‌توان تابع مولد دنباله ۰, ۱, ۴, ۹, ۱۶, … از اعداد مربعی را با استفاده از ترکیب خطی از ضرایب دوجمله‌ای زیر به‌دست‌آورد:

${\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {2}{(1-x)^{3}}}-{\frac {3}{(1-x)^{2}}}+{\frac {1}{1-x}}={\frac {x(x+1)}{(1-x)^{3}}}.}$

توابع گویا

مقالهٔ اصلی: دنباله بازگشتی خطی

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

ضرب منجر به کانولوشن

مقالهٔ اصلی: ضرب کوشی

ضرب چند تابع مولد باعث ایجاد یک پیچیدگی گسسته در (ضرب کوشی) دنباله‌ها می‌گردد. به عنوان مثال دنباله مجموع تجمعی:

${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\cdots )}$

از یک دنباله با تابع مولد معمولی (G(a_n; xدارای تابع مولد زیر می‌باشد:

${\displaystyle G(a_{n};x)={\frac {1}{1-x}}}$

زیرا 1/(1-x) تابع مولد معمولی دنباله (۱, ۱, ...) می‌باشد.

ارتباط با با گسستگی زمانی تبدیل فوریه

مقالهٔ اصلی: Discrete-time Fourier transform

سری مطلقاً همگرا ی زیر را در نظر بگیرید:

${\displaystyle G\left(a_{n};e^{-i\omega }\right)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n}}$

این سری گسستگی زمانی تبدیل فوریه a₀, a₁, .... را به ما می‌دهد.

رشد مجانبی از دنباله

در حساب دیفرانسیل و انتگرال، اغلب از نرخ رشد ضریب یک سری توانی برای محاسبه شعاع همگرایی استفاده می‌شود. عکس این مطلب نیز صادق است؛ اغلب شعاع همگرایی برای یک تابع مولد را می‌توان برای استنباط آنالیز مجانبی یک دنباله اساسی مورد استفاده قرار داد. به عنوان مثال، تابع مولد معمولی G(a_n; x) که دارای شعاع محدودی از همگرایی (r) می‌باشد به صورت زیر نوشته می‌شود:

${\displaystyle G(a_{n};x)={\frac {A(x)+B(x)\left(1-{\frac {x}{r}}\right)^{-\beta }}{x^{\alpha }}}}$

که در آن(A(xو (B(x توابع تحلیلی با شعاع همگرایی بزرگ‌تر (یا مساوی) r بوده و B (r) ≠ ۰. با استفاده از تابع گاما یا ضرایب دو جمله ای داریم:

${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}(1/r)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}(1/r)^{n},}$

رشد مجانبی از دنباله مربعات

با توجه به مطالب بیان شده فوق، تابع مولد معمولی دنباله مربعات به صورت زیر است:

${\displaystyle {\frac {x(x+1)}{(1-x)^{3}}}.}$

که در آن r = ۱, α = ۰, β = 3, A(x) = ۰, و B(x) = x(x+1), همچنین ما می‌توانیم بررسی کنیم که آیا دنباله مربعات همان‌طور که انتظار داشتیم رشد می‌کند، بدین منظور داریم:

${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {1(1+1)}{1^{0}\,\Gamma (3)}}\,n^{3-1}(1/1)^{n}=n^{2}.}$

رشد مجانبی اعداد کاتالان

مقالهٔ اصلی: اعداد کاتالان

تابع مولد معمولی برای اعدا کاتالان به صورت زیر است:

${\displaystyle {\frac {1-{\sqrt {1-4x}}}{2x}}.}$

که در آن r = ۱/۴, α = ۱, β = −1/2, A(x) = 1/2, and B(x) = −۱/۲, همچنین می‌توان برای اعداد کاتالان نتیجه‌گیری زیر را انجام داد:

${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {-{\frac {1}{2}}}{({\frac {1}{4}})^{1}\Gamma (-{\frac {1}{2}})}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\frac {1}{4}}}\right)^{n}={\frac {n^{-{\frac {3}{2}}}\,4^{n}}{\sqrt {\pi }}}.}$

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

در واقع می‌توان تابع مولد با چند متغیر را مانند آرایه‌ای شامل تعدادی اندیس تعریف کرد، که به آن توابع مولد چند متغیره یا توابع مولد فوق‌العاده و برای دو متغیر توابع مولد دومتغیرهگویند.

به عنوان مثال ${\displaystyle (1+x)^{n}}$ تابع مولد معمولی برای ضرایب دو جمله ای با یک n ثابت است. حال فرض کنید بخواهیم تابع مولد دومتغیره‌ای که ضرایب دو جمله‌ای ${\displaystyle {\binom {n}{k}}}$ را برای تمامk و n‌ها تولید می‌کند را به‌دست آوریم، برای این منظور ${\displaystyle (1+x)^{n}}$ را به عنوان یک سری در n در نظر گرفته و تمامی توابع مولد در y را پیدا می‌کنیم که این عبارت را به عنوان ضریب دارند. تابع مولد ${\displaystyle a^{n}}$ به صورت زیر است:

${\displaystyle {\frac {1}{1-ay}},}$

تابع مولد ضرایب دوجمله‌ای عبارت است از:

${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.}$

مثال

تابع مولد برای دنباله اعداد مربع کامل a_n = n²:

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

${\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}.}$

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

${\displaystyle EG(n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}}$

سری Bell

${\displaystyle f_{p}(x)=\sum _{n=0}^{\infty }p^{2n}x^{n}={\frac {1}{1-p^{2}x}}}$

سری دیریکله

${\displaystyle \operatorname {DG} (n^{2};s)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2),}$

با استفاده از تابع زتای ریمان.

دنبالهٔ a_n که توسط تابع مولد سری دیریکله تولید شده متناظر است با:

${\displaystyle \operatorname {DG} (a_{n};s)=\zeta (s)^{m}}$

که در آن ${\displaystyle \zeta (s)}$ تابع زتای ریمان بوده که دارای تابع مولد معمولی می‌باشد:

${\displaystyle \sum _{n=1}^{\infty }a_{n}x^{n}=x+{m \choose 1}\sum _{a=2}^{\infty }x^{a}+{m \choose 2}\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }x^{ab}+{m \choose 3}\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }x^{abc}+{m \choose 4}\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }x^{abcd}+\cdots }$

تابع چند متغیره

توابع مولد چند متغیره در عمل در هنگام محاسبه جدول احتمال متشکل از اعداد طبیعی نامنفی با شماره سطر و ستون مشخص به کار برده می‌شوند. فرض کنید جدول مورد نظر دارای r سطر و c ستون باشد؛ مجموع سطرها برابر ${\displaystyle t_{1},\ldots t_{r}}$ و مجموع ستون‌ها برابر ${\displaystyle s_{1},\ldots s_{c}}$ می‌باشد. بر اساس I. J. Good عدد این جدول برابر است باضرایب:${\displaystyle x_{1}^{t_{1}}\ldots x_{r}^{t_{r}}y_{1}^{s_{1}}\ldots y_{c}^{s_{c}}}$ در:

${\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.}$

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

توابع مولد در موارد زیر استفاده می‌شوند:

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

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

نمونه‌هایی از دنباله‌های چندجمله ای که توسط توابع مولد تولید شده‌اند:

• چندجمله‌ای‌های Appell
• چندجمله‌ای چبیشف
• چندجمله‌ای‌های Difference
• چندجمله‌ای‌های عمومیAppell
• چندجمله‌ای‌های Q-difference

منابع

• Doubilet, Peter; Rota, Gian-Carlo; Stanley, Richard (1972). "On the foundations of combinatorial theory. VI. The idea of generating function". Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability. 2: 267–318. Zbl 0267.05002. Reprinted in Rota, Gian-Carlo (1975). "3. The idea of generating function". Finite Operator Calculus. With the collaboration of P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko and R. Stanley. Academic Press. pp. 83–134. ISBN 0-12-596650-4. Zbl 0328.05007.
• Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001
• Ronald L. Graham; Donald E. Knuth; Oren Patashnik (1994). "Chapter 7: Generating Functions". Concrete Mathematics. A foundation for computer science (second ed.). Addison-Wesley. pp. 320–380. ISBN 0-201-55802-5. Zbl 0836.00001. {{cite book}}: Unknown parameter |author-separator= ignored (help)
• Wilf, Herbert S. (1994). Generatingfunctionology (2nd ed.). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001.
• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press. ISBN 978-0-521-89806-5. Zbl 1165.05001.

پیوند به بیرون

• "Generating function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Generating Functions, Power Indices and Coin Change at cut-the-knot
• Generatingfunctionology PDF download page
• (فرانسوی) 1031 Generating Functions
• Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
• Frederick Lecue; Riedel, Marko, et al., Permutation, Les-Mathematiques.net, in French, title somewhat misleading.
• "Generating Functions" by Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.