تابع مولد

تابع مولد معمولی دنبالهٔ 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 استفاده کنید.

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

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

${\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) تابع مولد معمولی دنباله (1, 1, ...) می‌باشد.

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

${\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) ≠ 0 . با استفاده از تابع گاما یا ضرایب دو جمله ای داریم :

${\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 = 1, α = 0, β = 3, A(x) = 0, و 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/4, α = 1, β = −1/2, A(x) = 1/2, and B(x) = −1/2, همچنین می‌توان برای اعداد کاتالان نتیجه‌گیری زیر را انجام داد :

${\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}}.}$

${\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}}$

${\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}}}.}$