دالة توليد

في الرياضيات ، الدالة المولدة هي تمثيل لسلسلة لانهائية من الأعداد كمعاملات لمتسلسلة قوى رسمية . غالبًا ما تُعبَّر الدوال المولدة بصيغة مغلقة (بدلاً من متسلسلة)، وذلك باستخدام تعبير يتضمن عمليات على المتسلسلة الرسمية.

توجد أنواع مختلفة من الدوال المولدة، منها الدوال المولدة العادية ، والدوال المولدة الأسية ، ومتسلسلات لامبرت ، ومتسلسلات بيل ، ومتسلسلات ديريشليه . من حيث المبدأ، لكل متتالية دالة مولدة من كل نوع (باستثناء متسلسلات لامبرت وديريشليه التي تتطلب أن تبدأ المؤشرات من 1 بدلاً من 0)، ولكن سهولة التعامل معها قد تختلف اختلافًا كبيرًا. وتعتمد الدالة المولدة الأنسب، إن وجدت، في سياق معين على طبيعة المتتالية وتفاصيل المسألة المطروحة.

تُسمى الدوال المولدة أحيانًا بالمتسلسلات المولدة ، ^{[ 1 ]} حيث يمكن القول أن سلسلة من الحدود هي مولد لتسلسل معاملات الحدود الخاصة بها.

تاريخ

تم تقديم الدوال المولدة لأول مرة من قبل أبراهام دي موافر في عام 1730، من أجل حل مشكلة التكرار الخطي العامة. ^{[ 2 ]}

يكتب جورج بوليا في كتابه "الرياضيات والاستدلال المعقول" :

يُعزى اسم "الدالة المولدة" إلى لابلاس . مع ذلك، استخدم أويلر أسلوب الدوال المولدة قبل لابلاس بزمن طويل، دون أن يُطلق عليه هذا الاسم . وقد طبّق هذه الأداة الرياضية على العديد من المسائل في التحليل التوافقي ونظرية الأعداد .

تعريف

الدالة المولدة هي أداة تشبه إلى حد ما الحقيبة. فبدلاً من حمل العديد من الأشياء الصغيرة بشكل منفصل، وهو أمر قد يكون محرجاً، نضعها جميعاً في حقيبة، وبالتالي لا يتبقى لدينا سوى شيء واحد لحمله، وهو الحقيبة.

— جورج بوليا ، الرياضيات والاستدلال المعقول (1954)

الدالة المولدة هي بمثابة حبل غسيل نعلق عليه سلسلة من الأرقام لعرضها.

— هربرت ويلف ، علم وظائف التوليد (1994)

التقارب

على عكس المتسلسلات العادية، لا يُشترط في متسلسلة القوى الرسمية أن تتقارب ؛ في الواقع، لا تُعتبر الدالة المولدة دالة بالمعنى الحرفي ، ويبقى "المتغير" غير محدد . يمكن تعميم ذلك على متسلسلة قوى رسمية بأكثر من متغير غير محدد، لترميز معلومات حول مصفوفات عددية متعددة الأبعاد لا نهائية. وبالتالي، فإن الدوال المولدة ليست دوالًا بالمعنى الرسمي للتحويل من مجال إلى مجال مقابل .

قد تتضمن هذه التعبيرات بدلالة المتغير غير المحدد $x$ عمليات حسابية، وتفاضلًا بالنسبة إلى $x$ ، وتركيبًا مع (أي تعويضًا في) دوال مولدة أخرى؛ ولأن هذه العمليات مُعرَّفة أيضًا للدوال، فإن النتيجة تبدو كدالة لـ $x$ . في الواقع، غالبًا ما يُمكن تفسير التعبير ذي الصيغة المغلقة على أنه دالة يُمكن تقييمها عند قيم محددة (صغيرة بما فيه الكفاية) لـ $x$ ، والتي لها متسلسلة صورية كمتسلسلة توسيع لها ؛ وهذا يُفسر تسمية "الدوال المولدة". مع ذلك، ليس من الضروري أن يكون هذا التفسير ممكنًا، لأن المتسلسلات الصورية ليست مُلزمة بإعطاء متسلسلة متقاربة عند استبدال قيمة عددية غير صفرية لـ $x$ .

القيود

ليست كل التعبيرات ذات المعنى كدوال لـ $x$ ذات معنى كتعبيرات تشير إلى متسلسلات رسمية؛ على سبيل المثال، القوى السالبة والكسرية لـ $x$ هي أمثلة على الدوال التي ليس لها متسلسلة قوى رسمية مقابلة.

الأنواع

دالة التوليد العادية (OGF)

عند استخدام مصطلح "الدالة المولدة" دون تحديد، يُقصد به عادةً الدالة المولدة العادية. الدالة المولدة العادية للمتتالية $a n$ هي: $G(a_{n};x)=\sum _{n=0}^{\infty}a_{n}x^{n}.$ إذا كانت $a n$ هي دالة الكتلة الاحتمالية لمتغير عشوائي منفصل ، فإن دالتها المولدة العادية تسمى دالة توليد الاحتمالات .

دالة التوليد الأسي (EGF)

الدالة المولدة الأسية للمتتالية $a n$ هي $\operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.$

تعتبر الدوال المولدة الأسية عمومًا أكثر ملاءمة من الدوال المولدة العادية لمسائل التعداد التوافقي التي تتضمن كائنات مصنفة. ^{[ 3 ]}

$من فوائد$ الدوال المولدة الأسية أنها مفيدة في نقل العلاقات التكرارية الخطية إلى مجال المعادلات التفاضلية $.$ $على$ سبيل المثال، لنأخذ متتالية فيبوناتشي ${fₙ}$ التي تحقق العلاقة التكرارية الخطية $fₙ₊₂$ $= fₙ₊₁ + fₙ . تأخذ$ الدالة المولدة الأسية المقابلة الشكل التالي $:$ $\operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}$

ويمكن إثبات أن مشتقاتها تحقق المعادلة التفاضلية $EF ″ (x) = EF' (x) + EF(x)$ كمعادلة مماثلة مباشرة للعلاقة التكرارية المذكورة أعلاه. وبناءً على هذا، فإن الحد العاملي n $! هو$ مجرد حد معاكس لتطبيع مؤثر المشتقة المؤثر على $xⁿ .$

دالة توليد بواسون

دالة توليد بواسون للمتتالية $a n$ هي $\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$ هي $\operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.$ لاحظ أنه في متسلسلة لامبرت، يبدأ الدليل $n$ من 1، وليس من 0، وإلا فإن الحد الأول سيكون غير معرف.

معاملات متسلسلة لامبرت في متسلسلات القوى $b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)$ ترتبط الأعداد الصحيحة $n \geq 1$ بمجموع القواسم $b_{n}=\sum _{d|n}a_{d}.$ تُقدّم المقالة الرئيسية العديد من الأمثلة الكلاسيكية، أو على الأقل المعروفة، المتعلقة بالدوال الحسابية الخاصة في نظرية الأعداد . كمثال على متطابقة متسلسلة لامبرت غير المذكورة في المقالة الرئيسية، يمكننا أن نُبيّن أنه بالنسبة لـ $| x | و | xq | < 1،$ لدينا ^{[ 4 ]} $\sum _{n=1}^{\infty }{\frac {q^{n}x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {q^{n}x^{n^{2}}}{1-qx^{n}}}+\sum _{n=1}^{\infty }{\frac {q^{n}x^{n(n+1)}}{1-x^{n}}},$

حيث لدينا متطابقة الحالة الخاصة للدالة المولدة لدالة القاسم ، $d (n) \equiv σ0 (n) ،$ المعطاة بواسطة $\sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {x^{n^{2}}\left(1+x^{n}\right)}{1-x^{n}}}.$

سلسلة بيل

سلسلة بيل لمتتالية $a n$ هي تعبير بدلالة كل من $x غير المحدد و$ $p$ الأولي ويتم إعطاؤها بواسطة: ^{[ 5 ]} $\operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.$

دوال توليد متسلسلة ديريشليه (DGFs)

تُصنف متسلسلات ديريشليه الرسمية غالبًا على أنها دوال مولدة، على الرغم من أنها ليست متسلسلات قوى رسمية بالمعنى الدقيق. دالة توليد متسلسلة ديريشليه للمتتالية $a n$ هي: ^{[ 6 ]} $\operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.$

تُعد دالة توليد متسلسلة ديريشلي مفيدة بشكل خاص عندما $تكون الدالة n$ دالة $ضربية$ ، وفي هذه الحالة يكون لها تعبير ضرب أويلر ^{[ 7 ]} بدلالة متسلسلة بيل للدالة: $\operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,.$

إذا كان المتغير n دالة $ديريشليه ،$ فإن دالة توليد متسلسلة ديريشليه الخاصة به تُسمى متسلسلة ديريشليه $L.$ لدينا أيضًا علاقة بين زوج المعاملات في متسلسلات لامبرت المذكورة أعلاه ودوال توليدها. أي، يمكننا إثبات ما يلي: $[x^{n}]\operatorname {LG} (a_{n};x)=b_{n}$ إذا وفقط إذا $\operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s),$ حيث $ζ (s)$ هي دالة زيتا لريمان . ^{[ 8 ]}

المتتالية $a k$ الناتجة عن دالة توليد متسلسلة ديريشليه (DGF) المقابلة لما يلي: $\operatorname {DG} (a_{k};s)=\zeta (s)^{m}$ لها دالة توليد عادية: $\sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots$

دوال توليد المتتابعات متعددة الحدود

يمكن توسيع مفهوم الدوال المولدة ليشمل متواليات من كائنات أخرى. فعلى سبيل المثال، يتم توليد متواليات كثيرات الحدود من النوع ذي الحدين عن طريق: $e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}$ حيث $p n (x)$ متتالية من كثيرات الحدود، و $f (t)$ دالة ذات شكل معين. تُولَّد متتاليات شيفر بطريقة مماثلة. راجع المقالة الرئيسية " كثيرات حدود أبيل المعممة" لمزيد من المعلومات.

تتضمن أمثلة المتتابعات متعددة الحدود التي يتم توليدها بواسطة دوال توليد أكثر تعقيدًا ما يلي:

وظائف توليد أخرى

تتضمن التسلسلات الأخرى التي يتم توليدها بواسطة دوال توليد أكثر تعقيدًا ما يلي:

الدوال المولدة للأس المزدوج
جداءات هادامارد للدوال المولدة والدوال المولدة القطرية، وتحويلاتها التكاملية المقابلة

كثيرات الحدود الالتفافية

تُعرّف مقالة كنوت "متعددات الحدود الالتفافية" [ ^{9 ] فئة} معممة من متتابعات متعددات الحدود الالتفافية من خلال دوالها المولدة الخاصة من الشكل $F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},$ لبعض الدوال التحليلية $F$ مع توسيع متسلسلة القوى بحيث $F (0) = 1$ .

نقول إن عائلة من كثيرات الحدود، $f 0 ، f 1 ، f 2 ، ...$ ، تشكل عائلة التفاف إذا $كانت درجة f n \leq n$ وإذا تحقق شرط الالتفاف التالي لجميع $x$ ، $y$ ولجميع $n \geq 0$ : $f_{n}(x+y)=f_{n}(x)f_{0}(y)+f_{n-1}(x)f_{1}(y)+\cdots +f_{1}(x)f_{n-1}(y)+f_{0}(x)f_{n}(y).$

نرى أنه بالنسبة لعائلات الالتفاف الصفرية غير المتطابقة، فإن هذا التعريف يعادل اشتراط أن يكون للمتتالية دالة توليد عادية من الشكل الأول المذكور أعلاه.

تتمتع سلسلة من كثيرات الحدود الالتفافية المعرفة بالترميز أعلاه بالخصائص التالية:

المتتالية $n! \cdot f n (x)$ من النوع ذي الحدين
تتضمن القيم الخاصة للمتتالية $f n (1) = [z n] F (z)$ و $f n (0) = δ n,0$ ، و
لقيمة ثابتة (اختيارية) $x,y,t\in \mathbb {C}$ تحقق هذه كثيرات الحدود صيغ الالتفاف من الشكل التالي:

${\begin{aligned}f_{n}(x+y)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(y)\\f_{n}(2x)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(x)\\xnf_{n}(x+y)&=(x+y)\sum _{k=0}^{n}kf_{k}(x)f_{n-k}(y)\\{\frac {(x+y)f_{n}(x+y+tn)}{x+y+tn}}&=\sum _{k=0}^{n}{\frac {xf_{k}(x+tk)}{x+tk}}{\frac {yf_{n-k}(y+t(n-k))}{y+t(n-k)}}.\end{aligned}}$

لمعامل ثابت غير صفري $t\in \mathbb {C}$ لقد قمنا بتعديل الدوال المولدة لمتتاليات كثيرات الحدود الالتفافية هذه المعطاة بواسطة ${\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},$ حيث تُعرَّف $𝓕 t (z) ضمنيًا$ بمعادلة دالية على الصورة $𝓕 t (z) = F (x 𝓕 t (z) t)$ . علاوة على ذلك، يمكننا استخدام طرق المصفوفات (كما في المرجع) لإثبات أنه إذا أُعطيت متتابعتان من كثيرات الحدود الالتفافية، $⟨ f n (x) ⟩$ و $⟨ g n (x) ⟩$ ، مع دوال التوليد المناظرة لهما، $F (z) x$ و $G (z) x$ ، فإنه لأي قيمة لـ $t،$ لدينا المتطابقة $\left[z^{n}\right]\left(G(z)F\left(zG(z)^{t}\right)\right)^{x}=\sum _{k=0}^{n}F_{k}(x)G_{n-k}(x+tk).$

تشمل أمثلة متتابعات كثيرات الحدود الالتفافية متسلسلة القوى ذات الحدين ، $𝓑 t (z) = 1 + z 𝓑 t (z) t$ ، وما يسمى بكثيرات حدود الشجرة ، وأعداد بيل ، $B (n)$ ، وكثيرات حدود لاغير ، وكثيرات حدود ستيرلينغ الالتفافية .

الدوال المولدة العادية

أمثلة على المتتابعات البسيطة

تُعدّ كثيرات الحدود حالة خاصة من الدوال المولدة العادية، وهي تُقابل المتتابعات المنتهية، أو ما يُكافئها من متتابعات تتلاشى بعد نقطة معينة. وتكمن أهميتها في إمكانية تفسير العديد من المتتابعات المنتهية على أنها دوال مولدة، مثل كثيرة حدود بوانكاريه وغيرها.

الدالة المولدة الأساسية هي دالة المتتالية الثابتة 1، 1، 1، 1، 1، 1، 1، 1، ... ، والتي دالتها المولدة العادية هي المتسلسلة الهندسية. $\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}.$

الطرف الأيسر هو متسلسلة ماكلورين للطرف الأيمن. ويمكن إثبات المساواة بضرب متسلسلة القوى على اليسار في $1 - x$ ، والتحقق من أن الناتج هو متسلسلة القوى الثابتة 1 (أي أن جميع المعاملات، باستثناء x₀، $تساوي صفرًا$ ). علاوة على ذلك، لا يمكن أن توجد متسلسلة قوى أخرى بهذه الخاصية. لذا، يُشير الطرف الأيسر إلى المعكوس الضربي لـ $1 - x$ في حلقة متسلسلات القوى.

$يمكن اشتقاق تعابير الدالة المولدة$ العادية للمتتابعات الأخرى بسهولة من هذه الدالة. على سبيل المثال، يعطي الاستبدال $x \to ax$ الدالة المولدة للمتتابعة الهندسية $1، a ، a² ، a³ ، ...$ لأي ثابت $a$ : $\sum _{n=0}^{\infty }(ax)^{n}={\frac {1}{1-ax}}.$

(وتنتج المساواة أيضًا بشكل مباشر من حقيقة أن الطرف الأيسر هو متسلسلة ماكلورين للطرف الأيمن.) على وجه الخصوص، $\sum _{n=0}^{\infty }(-1)^{n}x^{n}={\frac {1}{1+x}}.$

يمكن أيضًا إدخال فجوات منتظمة في المتتالية عن طريق استبدال $x$ بقوة معينة من قوى $x$ ، فعلى سبيل المثال، بالنسبة للمتتالية 1، 0، 1، 0، 1، 0، 1، 0، ... (التي تتخطى $x ، x³ ، x⁵ ، ...$ )، نحصل على الدالة المولدة $.$ $\sum _{n=0}^{\infty }x^{2n}={\frac {1}{1-x^{2}}}.$

بتربيع الدالة المولدة الأولية، أو بإيجاد مشتقة كلا الطرفين بالنسبة إلى $x$ وتغيير المتغير المتحرك $n \to n + 1$ ، يتبين أن المعاملات تشكل المتتالية 1، 2، 3، 4، 5، ... ، وبالتالي يكون لدينا $\sum _{n=0}^{\infty }(n+1)x^{n}={\frac {1}{(1-x)^{2}}},$

والقوة الثالثة لها معاملات هي الأعداد المثلثية 1، 3، 6، 10، 15، 21، ... حيث يمثل الحد n $معامل$ ذات الحدين $(n + 2²) ،$ بحيث $\sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{n}={\frac {1}{(1-x)^{3}}}.$

وبشكل أعم، بالنسبة لأي عدد صحيح غير سالب $k$ وقيمة حقيقية غير صفرية $a$ ، فإن ذلك صحيح. $\sum _{n=0}^{\infty }a^{n}{\binom {n+k}{k}}x^{n}={\frac {1}{(1-ax)^{k+1}}}\,.$

منذ $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},$

يمكن إيجاد الدالة المولدة العادية للمتتالية 0، 1، 4، 9، 16، ... من الأعداد المربعة عن طريق التركيب الخطي لمتتاليات توليد معاملات ذات الحدين: $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}}}.$

يمكننا أيضًا التوسع بالتناوب لتوليد نفس سلسلة المربعات كمجموع مشتقات المتسلسلة الهندسية بالشكل التالي: ${\begin{aligned}G(n^{2};x)&=\sum _{n=0}^{\infty }n^{2}x^{n}\\[4px]&=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\[4px]&=x^{2}D^{2}\left[{\frac {1}{1-x}}\right]+xD\left[{\frac {1}{1-x}}\right]\\[4px]&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}.\end{aligned}}$

بالاستقراء، يمكننا بالمثل أن نبين للأعداد الصحيحة الموجبة $m \geq 1$ أن ^{[ 10 ]}^{[ 11 ]} $n^{m}=\sum _{j=0}^{m}{\begin{Bmatrix}m\\j\end{Bmatrix}}{\frac {n!}{(n-j)!}},$

حيث تشير ${n k}$ إلى أعداد ستيرلينغ من النوع الثاني، وحيث الدالة المولدة $\sum _{n=0}^{\infty }{\frac {n!}{(n-j)!}}\,z^{n}={\frac {j!\cdot z^{j}}{(1-z)^{j+1}}},$

وبذلك نستطيع تكوين الدوال المولدة المماثلة على القوى الصحيحة من الرتبة $m$ ، مما يعمم النتيجة في حالة المربع أعلاه. على وجه الخصوص، بما أننا نستطيع كتابة ${\frac {z^{k}}{(1-z)^{k+1}}}=\sum _{i=0}^{k}{\binom {k}{i}}{\frac {(-1)^{k-i}}{(1-z)^{i+1}}},$

يمكننا تطبيق متطابقة مجموع محدود معروفة تتضمن أعداد ستيرلينغ للحصول على ذلك ^{[ 12 ]} $\sum _{n=0}^{\infty }n^{m}z^{n}=\sum _{j=0}^{m}{\begin{Bmatrix}m+1\\j+1\end{Bmatrix}}{\frac {(-1)^{m-j}j!}{(1-z)^{j+1}}}.$

الدوال الكسرية

يمكن التعبير عن الدالة المولدة العادية لمتتالية ما كدالة كسرية (نسبة كثيرتي حدود من الدرجة المحدودة) إذا وفقط إذا كانت المتتالية متتالية خطية تكرارية ذات معاملات ثابتة؛ وهذا يُعمم الأمثلة السابقة. وعلى العكس، فإن كل متتالية مولدة بكسر من كثيرات الحدود تُحقق علاقة تكرارية خطية ذات معاملات ثابتة؛ وهذه المعاملات هي نفسها معاملات كثير الحدود في مقام الكسر (لذا يمكن استنتاجها مباشرة). تُظهر هذه الملاحظة سهولة إيجاد الدوال المولدة للمتتاليات المعرفة بمعادلة فرقية خطية محدودة ذات معاملات ثابتة، ومن ثم، إيجاد صيغ مغلقة صريحة لمعاملات هذه الدوال المولدة. والمثال النموذجي هنا هو اشتقاق صيغة بينيه لأعداد فيبوناتشي باستخدام تقنيات الدوال المولدة.

نلاحظ أيضًا أن فئة الدوال المولدة النسبية تتوافق تمامًا مع الدوال المولدة التي تعد تسلسلات شبه متعددة الحدود من الشكل ^{[ 13 ].} $f_{n}=p_{1}(n)\rho _{1}^{n}+\cdots +p_{\ell }(n)\rho _{\ell }^{n},$

حيث الجذور المتبادلة، $\rho _{i}\in \mathbb {C}$ ، هي قيم قياسية ثابتة حيث $p i (n)$ هي متعددة الحدود في $n$ لجميع $1 \leq i \leq ℓ$ .

بشكل عام، ينتج عن جداءات هادامارد للدوال الكسرية دوال توليد كسرية. وبالمثل، إذا $F(s,t):=\sum _{m,n\geq 0}f(m,n)w^{m}z^{n}$

إذا كانت دالة توليد كسرية ثنائية المتغيرات، فإن دالة التوليد القطرية المقابلة لها ، $\operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n},$

هي جبرية . على سبيل المثال، إذا وضعنا ^{[ 14 ]} $F(s,t):=\sum _{i,j\geq 0}{\binom {i+j}{i}}s^{i}t^{j}={\frac {1}{1-s-t}},$

ثم تُعطى دالة توليد المعاملات القطرية لهذه الدالة المولدة بواسطة صيغة OGF المعروفة $\operatorname {diag} (F)=\sum _{n=0}^{\infty }{\binom {2n}{n}}z^{n}={\frac {1}{\sqrt {1-4z}}}.$

يتم حساب هذه النتيجة بعدة طرق، بما في ذلك صيغة كوشي التكاملية أو التكامل الكفافي ، أو أخذ البقايا المعقدة ، أو عن طريق التلاعب المباشر بسلاسل القوى الرسمية في متغيرين.

العمليات على الدوال المولدة

ينتج عن الضرب عملية الالتفاف

ينتج عن ضرب الدوال المولدة العادية التفاف منفصل ( جداء كوشي ) للمتتاليات. على سبيل المثال، متتالية المجاميع التراكمية (قارن بصيغة أويلر-ماكلورين الأكثر عمومية قليلاً ). $(a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )$ للمتتالية ذات الدالة المولدة العادية $G$ $(an; x) الدالة$ المولدة $G(a_{n};x)\cdot {\frac {1}{1-x}}$ لأنّ $1 / (1 - x)$ هي الدالة المولدة العادية للمتتالية (1، 1، ...) . انظر أيضًا قسم الالتفافات في قسم التطبيقات من هذه المقالة أدناه لمزيد من الأمثلة على حل المسائل باستخدام التفافات الدوال المولدة وتفسيراتها.

مؤشرات تسلسل الإزاحة

بالنسبة للأعداد الصحيحة $m \geq 1$ ، لدينا المتطابقتان المتماثلتان التاليتان للدوال المولدة المعدلة التي تعدّد متغيرات التسلسل المزاحة لـ $⟨ g n - m ⟩$ و $⟨ g n + m ⟩$ على التوالي: ${\begin{aligned}&z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\\[4px]&{\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}=\sum _{n=0}^{\infty }g_{n+m}z^{n}.\end{aligned}}$

التفاضل والتكامل للدوال المولدة

لدينا متسلسلات القوى التالية للمشتقة الأولى لدالة مولدة وتكاملها: ${\begin{aligned}G'(z)&=\sum _{n=0}^{\infty }(n+1)g_{n+1}z^{n}\\[4px]z\cdot G'(z)&=\sum _{n=0}^{\infty }ng_{n}z^{n}\\[4px]\int _{0}^{z}G(t)\,dt&=\sum _{n=1}^{\infty }{\frac {g_{n-1}}{n}}z^{n}.\end{aligned}}$

يمكن تكرار عملية التفاضل والضرب للعنصر المحايد الثاني $k$ مرة لضرب المتتالية في $n k$ ، ولكن هذا يتطلب التناوب بين التفاضل والضرب. أما إذا أجرينا $k$ عملية تفاضل بالتتابع، فسيكون التأثير هو الضرب في المضروب التنازلي رقم $k$ . $z^{k}G^{(k)}(z)=\sum _{n=0}^{\infty }n^{\underline {k}}g_{n}z^{n}=\sum _{n=0}^{\infty }n(n-1)\dotsb (n-k+1)g_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .$

باستخدام أعداد ستيرلينغ من النوع الثاني ، يمكن تحويل ذلك إلى صيغة أخرى للضرب في $n^{k}$ كما يلي (انظر المقال الرئيسي حول تحويلات الدوال المولدة ): $\sum _{j=0}^{k}{\begin{Bmatrix}k\\j\end{Bmatrix}}z^{j}F^{(j)}(z)=\sum _{n=0}^{\infty }n^{k}f_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .$

يُعرَّف عكس رتبة سالبة لصيغة قوى هذه المتتالية، الموافق لعملية التكامل المتكرر ، بتحويل متسلسلة زيتا وتعميماته، المُعرَّفة كتحويل قائم على المشتقات للدوال المولدة ، أو بديلًا، حدًا حدًا، بإجراء تحويل تكاملي على الدالة المولدة للمتتالية. وتُناقش هنا العمليات ذات الصلة بإجراء التكامل الكسري على الدالة المولدة للمتتالية .

تعداد المتتابعات الحسابية

في هذا القسم، نقدم صيغًا للدوال المولدة التي تحصي المتتالية ${f an + b}$ بمعلومية دالة مولدة عادية $F (z)$ ، حيث $a \geq 2$ ، و $0 \leq b < a$ ، و $a$ و $b$ عددان صحيحان (انظر المقال الرئيسي حول التحويلات ). بالنسبة لـ $a = 2$ ، فإن هذا ببساطة هو التفكيك المألوف للدالة إلى أجزاء زوجية وفردية (أي قوى زوجية وفردية). ${\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\[4px]\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned}}$

بشكل أعم، لنفترض أن $a \geq 3$ وأن $ω a = exp ⁠ 2 πi / a ⁠$ يمثل الجذر الأولي للوحدة من الرتبة $a$ . عندئذٍ، كتطبيق لتحويل فورييه المنفصل ، لدينا الصيغة ^[¹⁵^] $\sum _{n=0}^{\infty }f_{an+b}z^{an+b}={\frac {1}{a}}\sum _{m=0}^{a-1}\omega _{a}^{-mb}F\left(\omega _{a}^{m}z\right).$

بالنسبة للأعداد الصحيحة $m \geq 1$ ، يتم توليد صيغة مفيدة أخرى توفر متواليات حسابية معكوسة إلى حد ما - تكرار كل معامل $m$ مرة بشكل فعال - بواسطة الهوية ^{[ 16 ].} $\sum _{n=0}^{\infty }f_{\left\lfloor {\frac {n}{m}}\right\rfloor }z^{n}={\frac {1-z^{m}}{1-z}}F(z^{m})=\left(1+z+\cdots +z^{m-2}+z^{m-1}\right)F(z^{m}).$

$المتتابعات المتكررة من النوع P$ ووظائف التوليد الهولونومية

التعريفات

يقال إن متسلسلة القوى الرسمية (أو الدالة) $F (z)$ هيلونومية إذا كانت تحقق معادلة تفاضلية خطية من الشكل ^{[ 17 ].} $c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0,$

حيث تكون المعاملات $c i (z)$ في مجال الدوال الكسرية، $\mathbb {C} (z)$ أو بعبارة أخرى، $F(z)$ تكون هولونومية إذا كان الفضاء المتجهي فوق $\mathbb {C} (z)$ الفضاء الذي تشكله مجموعة جميع مشتقاته ذو أبعاد محدودة.

بما أنه يمكننا التخلص من المقامات إذا لزم الأمر في المعادلة السابقة، فيمكننا افتراض أن الدوال $cᵢ (z)$ هي كثيرات حدود في $z$ . وبالتالي، يمكننا إيجاد شرط مكافئ بأن الدالة المولدة هي دالة هولونومية إذا كانت معاملاتها تحقق $علاقة$ تكرارية من $النوع P$ على الصورة التالية: ${\widehat {c}}_{s}(n)f_{n+s}+{\widehat {c}}_{s-1}(n)f_{n+s-1}+\cdots +{\widehat {c}}_{0}(n)f_{n}=0,$

لكل عدد صحيح كبير بما فيه الكفاية $n \geq n \geq 0$ ، حيث $ĉ i (n)$ هي كثيرات حدود ثابتة من الدرجة المحدودة في $n$ . بعبارة أخرى، فإن خاصيتي كون متتالية ما $P-$ تكرارية وامتلاكها دالة توليد هولونومية متكافئتان. الدوال الهولونومية مغلقة تحت عملية ضرب هادامارد $⊙$ على الدوال المولدة.

أمثلة

الدوال $e z$ ، $log z$ ، $cos z$ ، $arcsin z$ ، ${\sqrt {1+z}}$ ، ودالة اللوغاريتم الثنائي $Li 2 (z)$ ، والدوال الهندسية الفائقة المعممة $p F q (...; ...; z)$ والدوال المعرفة بواسطة متسلسلة القوى $\sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}$

وغير المتقارب $\sum _{n=0}^{\infty }n!\cdot z^{n}$ جميعها شاملة.

من أمثلة المتتابعات المتكررة من $النوع P$ ذات الدوال المولدة الشاملة $f n ≔ ⁠ 1 / n + 1 ⁠ (2 n n)$ و $f n ≔ ⁠ 2 n / n 2 + 1 ⁠$ ، حيث تكون المتتابعات مثل ${\sqrt {n}}$ و $log n$ ليست دوالًا تكرارية $من النوع P$ نظرًا لطبيعة النقاط الشاذة في دوالها المولدة. وبالمثل، فإن الدوال التي تحتوي على عدد لا نهائي من النقاط الشاذة، مثل tan $z$ $و$ sec $z$ $و$ Γ $($ $z$ $)،$ ليست دوالًا هولونومية.

برنامج للعمل مع المتتاليات المتكررة من النوع $P$ ووظائف التوليد الهولونومية

تتضمن أدوات معالجة المتتاليات التكرارية من الرتبة $P$ في برنامج Mathematica حزم البرامج المتاحة للاستخدام غير التجاري على موقع برمجيات التوافقية الخوارزمية التابع لمجموعة RISC Combinatorics . وعلى الرغم من أن معظمها مغلق المصدر، إلا أن هذه الحزمة توفر أدوات قوية للغاية، منها حزمة Guessلتخمين المتتاليات التكرارية من الرتبة $P$ لأي متتاليات إدخال (مفيدة في الرياضيات التجريبية والاستكشافية)، وحزمة أخرى Sigmaقادرة على إيجاد المتتاليات التكرارية من الرتبة P للعديد من المجاميع، وإيجاد حلول مغلقة للمتتاليات التكرارية من الرتبة $P التي تتضمن$ الأعداد التوافقية المعممة . ^{[ 18 ]} كما توجد حزم أخرى مدرجة على موقع RISC هذا، وهي مخصصة للعمل مع الدوال المولدة الهولونومية تحديدًا.

العلاقة بتحويل فورييه المنفصل زمنيًا

عندما تتقارب المتسلسلة تقارباً مطلقاً ، $G\left(a_{n};e^{-i\omega }\right)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n}$ هو تحويل فورييه المنفصل زمنيًا للمتتالية $a 0 ، a 1 ، ...$ .

النمو التقاربي للمتتالية

في حساب التفاضل والتكامل، غالبًا ما يُستخدم معدل نمو معاملات متسلسلة القوى لاستنتاج نصف قطر تقاربها . وينطبق العكس أيضًا؛ إذ غالبًا ما يُستخدم نصف قطر تقارب الدالة المولدة لاستنتاج النمو التقاربي للمتتالية الأساسية.

على سبيل المثال، إذا كانت دالة توليد عادية $G (an; x)$ ذات نصف قطر تقارب محدود $r،$ $فيمكن$ كتابتها على النحو التالي: $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) \neq 0،$ فإن $a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n}={\frac {B(r)}{r^{\alpha }}}\left(\!\!{\binom {\beta }{n}}\!\!\right)\left({\frac {1}{r}}\right)^{n}\,,$ باستخدام دالة غاما ، أو معامل ذي الحدين ، أو معامل مجموعة متعددة . لاحظ أن نهاية نسبة an إلى أي من هذه التعبيرات عندما يؤول n إلى $اللانهاية$ $مضمونة$ $لتكون$ 1؛ وليس مجرد أن $a$ $n$ متناسب معها.

غالباً ما يمكن تكرار هذا النهج لتوليد عدة حدود في متسلسلة تقاربية لـ $n .$ على وجه الخصوص، $G\left(a_{n}-{\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n};x\right)=G(a_{n};x)-{\frac {B(r)}{r^{\alpha }}}\left(1-{\frac {x}{r}}\right)^{-\beta }\,.$

ويمكن بعد ذلك البحث عن النمو التقاربي لمعاملات هذه الدالة المولدة من خلال إيجاد $A$ و $B$ و $α$ و $β$ و $r$ لوصف الدالة المولدة، كما هو مذكور أعلاه.

يمكن إجراء تحليل تقاربي مماثل للدوال المولدة الأسية؛ فمع دالة مولدة أسية، يكون الناتج هو $a n$ $/$ $n$ $!$ $⁠$ $الذي$ $ينمو$ وفقًا لهذه الصيغ التقاربية. عمومًا، إذا كان نصف قطر تقارب الدالة المولدة لمتتالية ما مطروحًا منها الدالة المولدة لمتتالية أخرى أكبر من نصف قطر تقارب كل دالة مولدة على حدة، فإن المتتاليتين لهما نفس النمو التقاربي.

النمو التقاربي لمتتالية المربعات

كما هو موضح أعلاه، فإن الدالة المولدة العادية لتسلسل المربعات هي: $G(n^{2};x)={\frac {x(x+1)}{(1-x)^{3}}}.$

مع $r = 1$ ، $α = -1$ ، $β = 3$ ، $A (x) = 0$ ، و $B (x) = x + 1$ ، يمكننا التحقق من أن المربعات تنمو كما هو متوقع، مثل المربعات: $a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {1+1}{1^{-1}\,\Gamma (3)}}\,n^{3-1}\left({\frac {1}{1}}\right)^{n}=n^{2}.$

النمو التقاربي لأعداد كاتالان

الدالة المولدة العادية لأعداد كاتالان هي $G(C_{n};x)={\frac {1-{\sqrt {1-4x}}}{2x}}.$

مع $r = 1/4 ،$ $α$ $=$ $1$ ، $β = -1/2$ ، $A$ $($ $x$ $)$ $=$ $1/2$ $،$ و $B$ $($ $x$ $)$ $=$ $-1/2$ $،$ يمكننا $أن نستنتج أنه بالنسبة لأعداد كاتالان :$ $$ $$ $$ $C_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {-{\frac {1}{2}}}{\left({\frac {1}{4}}\right)^{1}\Gamma \left(-{\frac {1}{2}}\right)}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\,{\frac {1}{4}}\,}}\right)^{n}={\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}.$

الدوال المولدة ثنائية المتغيرات ومتعددة المتغيرات

يمكن تعميم الدالة المولدة في عدة متغيرات لتشمل المصفوفات ذات المؤشرات المتعددة. تُسمى هذه الأمثلة غير متعددة الحدود ذات المجموع المزدوج بالدوال المولدة متعددة المتغيرات ، أو الدوال المولدة الفائقة . أما في حالة متغيرين، فتُسمى غالبًا بالدوال المولدة ثنائية المتغيرات .

حالة ثنائية المتغيرات

الدالة المولدة العادية لمصفوفة ثنائية الأبعاد $a m, n$ (حيث $n$ و $m$ أعداد طبيعية) هي: $G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.$ على سبيل المثال، بما أن $(1 + x) n$ هي الدالة المولدة العادية لمعاملات ذات الحدين لقيمة $n$ ثابتة ، يمكن البحث عن دالة مولدة ثنائية المتغيرات تولد معاملات ذات الحدين $(nk)$ لجميع قيم $k$ و $n$ . وللقيام بذلك، نعتبر $(1 + x$ $)$ $n$ $نفسها$ متتالية في $n$ ، ونجد الدالة المولدة في $y$ التي تأخذ قيم هذه المتتالية كمعاملات. بما أن الدالة المولدة لـ $n$ $هي$ : ${\frac {1}{1-ay}},$ الدالة المولدة لمعاملات ذات الحدين هي: $\sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.$ وتشمل الأمثلة الأخرى على ذلك دوال التوليد ذات المتغيرين التالية لمعاملات ذات الحدين ، وأعداد ستيرلينغ ، وأعداد أويلر ، حيث يشير $ω$ و $z$ إلى المتغيرين: ^{[ 19 ]} ${\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\[4px]e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}{\begin{Bmatrix}n\\m\end{Bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}{\begin{bmatrix}n\\m\end{bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1-w}{e^{(w-1)z}-w}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}n\\m\end{matrix}}\right\rangle w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}m+n+1\\m\end{matrix}}\right\rangle {\frac {w^{m}z^{n}}{(m+n+1)!}}.\end{aligned}}$

حالة متعددة المتغيرات

تظهر الدوال المولدة متعددة المتغيرات عمليًا عند حساب عدد جداول التوافق للأعداد الصحيحة غير السالبة ذات مجاميع الصفوف والأعمدة المحددة. لنفترض أن الجدول يحتوي على $r$ صفًا و $c$ عمودًا؛ وأن مجاميع الصفوف هي $t₁, t₂, ...,$ ^tᵣ $،$ $ومجاميع$ الأعمدة هي $s₁, s₂, ...$ $,$ $sᵣ$ $.$ عندئذٍ، وفقًا لـ IJ Good [ ²⁰^]، $فإن$ عدد هذه الجداول هو معامل: $x_{1}^{t_{1}}\cdots x_{r}^{t_{r}}y_{1}^{s_{1}}\cdots y_{c}^{s_{c}}$ في: $\prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.$

التمثيل بواسطة الكسور المستمرة (كسور جاكوبي من النوع $J$ )

التعريفات

تُعدّ متسلسلات الكسور المستمرة من نوع جاكوبي وستيلتجس ( الكسور $J$ والكسور $S$ على التوالي)، التي تمثل متقارباتها النسبية من الرتبة $h متسلسلات قوى$ دقيقة من الرتبة $2h$ $،$ طريقةً أخرى للتعبير عن الدوال المولدة العادية المتباعدة عادةً للعديد من المتتابعات الخاصة ذات المتغير الواحد والمتغيرين. يتم توسيع الشكل الخاص للكسور المستمرة من نوع جاكوبي ( الكسور $J$ ) كما في المعادلة التالية، ولها متسلسلات القوى المقابلة التالية بالنسبة إلى $z$ لبعض متتابعات المكونات المحددة، ${ab$ $i$ $}$ و ${$ $c$ $i$ $}$ ، حيث $z$ $\neq 0$ يُمثل المتغير الرسمي في متسلسل القوى الثاني الموضح أدناه: ^[²¹^] ${\begin{aligned}J^{[\infty ]}(z)&={\cfrac {1}{1-c_{1}z-{\cfrac {{\text{ab}}_{2}z^{2}}{1-c_{2}z-{\cfrac {{\text{ab}}_{3}z^{2}}{\ddots }}}}}}\\[4px]&=1+c_{1}z+\left({\text{ab}}_{2}+c_{1}^{2}\right)z^{2}+\left(2{\text{ab}}_{2}c_{1}+c_{1}^{3}+{\text{ab}}_{2}c_{2}\right)z^{3}+\cdots \end{aligned}}$

معاملات $z^{n}$ ، والتي يُشار إليها اختصارًا بـ $j n ≔ [z n] J [\infty] (z)$ ، في المعادلات السابقة تتوافق مع حلول المصفوفة للمعادلات: ${\begin{bmatrix}k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\k_{0,3}&k_{1,3}&k_{2,3}&k_{3,3}&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}={\begin{bmatrix}k_{0,0}&0&0&0&\cdots \\k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}\cdot {\begin{bmatrix}c_{1}&1&0&0&\cdots \\{\text{ab}}_{2}&c_{2}&1&0&\cdots \\0&{\text{ab}}_{3}&c_{3}&1&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}},$

حيث $j 0 \equiv k 0,0 = 1$ ، $j n = k 0, n$ لـ $n \geq 1$ ، $k r, s = 0$ إذا كان $r > s$ ، وحيث لجميع الأعداد الصحيحة $p ، q \geq 0$ ، لدينا علاقة صيغة جمع معطاة بواسطة: $j_{p+q}=k_{0,p}\cdot k_{0,q}+\sum _{i=1}^{\min(p,q)}{\text{ab}}_{2}\cdots {\text{ab}}_{i+1}\times k_{i,p}\cdot k_{i,q}.$

خصائص الدوال المتقاربة من الرتبة $h$

بالنسبة لـ $h \geq 0$ (على الرغم من أنه عمليًا عندما $h \geq 2$ )، يمكننا تعريف التقارب النسبي من الرتبة $h$ إلى الكسر $J$ اللانهائي ، $J [\infty] (z)$ ، الموسع بواسطة: $\operatorname {Conv} _{h}(z):={\frac {P_{h}(z)}{Q_{h}(z)}}=j_{0}+j_{1}z+\cdots +j_{2h-1}z^{2h-1}+\sum _{n=2h}^{\infty }{\widetilde {j}}_{h,n}z^{n}$

على مستوى المكونات من خلال المتتاليات، $P h (z)$ و $Q h (z)$ ، المعرفة بشكل متكرر بواسطة: ${\begin{aligned}P_{h}(z)&=(1-c_{h}z)P_{h-1}(z)-{\text{ab}}_{h}z^{2}P_{h-2}(z)+\delta _{h,1}\\Q_{h}(z)&=(1-c_{h}z)Q_{h-1}(z)-{\text{ab}}_{h}z^{2}Q_{h-2}(z)+(1-c_{1}z)\delta _{h,1}+\delta _{0,1}.\end{aligned}}$

علاوة على ذلك، فإن عقلانية دالة التقارب $Conv h (z)$ لجميع $قيم h \geq 2$ تستلزم معادلات فرقية محدودة إضافية وخصائص تطابق تحققها متتالية $j n$ ، وبالنسبة لـ $M h ≔ ab 2 \dots ab h + 1$ إذا كان $h ‖ M h،$ فإننا نحصل على التطابق. $j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}},$

بالنسبة للاختيارات غير الرمزية والمحددة لتسلسلات المعلمات ${ab i}$ و ${c i}$ عندما $h \geq 2$ ، أي عندما لا تعتمد هذه التسلسلات ضمنيًا على معلمة مساعدة مثل $q$ أو $x$ أو $R$ كما في الأمثلة الواردة في الجدول أدناه.

أمثلة

يُقدّم الجدول التالي أمثلةً على الصيغ المغلقة لمتتاليات المكونات التي تم إيجادها حسابيًا (والتي ثبتت صحتها لاحقًا في المراجع المذكورة ^{[ 22 ]} ) في عدة حالات خاصة من المتتاليات المحددة، $j n$ ، الناتجة عن التوسعات العامة للكسور $J$ المُعرّفة في القسم الفرعي الأول. هنا، نُعرّف $0 < | a | ، | b | ، | q | < 1$ والمعاملات $R,\alpha \in \mathbb {Z} ^{+}$ و $x$ لتكون غير محددة بالنسبة لهذه التوسعات، حيث يتم تعريف التسلسلات المحددة التي يتم تعدادها بواسطة توسعات هذه الكسور $J$ من حيث رمز $q$ -Pochhammer ، ورمز Pochhammer ، ومعاملات ذات الحدين .

$j_{n}$	$c_{1}$	$c_{i}(i\geq 2)$	$\mathrm {ab} _{i}(i\geq 2)$
$q^{n^{2}}$	$q$	$q^{2h-3}\left(q^{2h}+q^{2h-2}-1\right)$	$q^{6h-10}\left(q^{2h-2}-1\right)$
$(a;q)_{n}$	$1-a$	$q^{h-1}-aq^{h-2}\left(q^{h}+q^{h-1}-1\right)$	$aq^{2h-4}\left(aq^{h-2}-1\right)\left(q^{h-1}-1\right)$
$\left(zq^{-n};q\right)_{n}$	${\frac {q-z}{q}}$	${\frac {q^{h}-z-qz+q^{h}z}{q^{2h-1}}}$	${\frac {\left(q^{h-1}-1\right)\left(q^{h-1}-z\right)\cdot z}{q^{4h-5}}}$
${\frac {(a;q)_{n}}{(b;q)_{n}}}$	${\frac {1-a}{1-b}}$	${\frac {q^{i-2}\left(q+abq^{2i-3}+a(1-q^{i-1}-q^{i})+b(q^{i}-q-1)\right)}{\left(1-bq^{2i-4}\right)\left(1-bq^{2i-2}\right)}}$	${\frac {q^{2i-4}\left(1-bq^{i-3}\right)\left(1-aq^{i-2}\right)\left(a-bq^{i-2}\right)\left(1-q^{i-1}\right)}{\left(1-bq^{2i-5}\right)\left(1-bq^{2i-4}\right)^{2}\left(1-bq^{2i-3}\right)}}$
$\alpha ^{n}\cdot \left({\frac {R}{\alpha }}\right)_{n}$	$R$	$R+2\alpha (i-1)$	$(i-1)\alpha {\bigl (}R+(i-2)\alpha {\bigr )}$
$(-1)^{n}{\binom {x}{n}}$	$-x$	$-{\frac {(x+2(i-1)^{2})}{(2i-1)(2i-3)}}$	${\begin{cases}-{\dfrac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&{\text{for }}i\geq 3;\\[4px]-{\frac {1}{2}}x(x+1)&{\text{for }}i=2.\end{cases}}$
$(-1)^{n}{\binom {x+n}{n}}$	$-(x+1)$	${\frac {{\bigl (}x-2i(i-2)-1{\bigr )}}{(2i-1)(2i-3)}}$	${\begin{cases}-{\dfrac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&{\text{for }}i\geq 3;\\[4px]-{\frac {1}{2}}x(x+1)&{\text{for }}i=2.\end{cases}}$

إن أنصاف أقطار تقارب هذه المتسلسلات التي تتوافق مع تعريف كسور $J$ من نوع جاكوبي المذكورة أعلاه تختلف بشكل عام عن تلك الخاصة بتوسعات متسلسلات القوى المقابلة التي تحدد الدوال المولدة العادية لهذه المتتاليات.

أمثلة

الأرقام المربعة

الدوال المولدة لتسلسل الأعداد المربعة $a n = n 2$ هي:

نوع الدالة المولدة	معادلة
دالة توليد عادية	$G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}$
دالة توليد أسية	$\operatorname {EG} (n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}$
سلسلة بيل	$\operatorname {BG} _{p}\left(n^{2};x\right)=\sum _{n=0}^{\infty }\left(p^{n}\right)^{2}x^{n}={\frac {1}{1-p^{2}x}}$
سلسلة ديريشلي	$\operatorname {DG} \left(n^{2};s\right)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2)$

حيث $ζ (s)$ هي دالة زيتا لريمان .

التطبيقات

تُستخدم الدوال المولدة من أجل:

أوجد صيغة مغلقة لمتتالية معطاة في علاقة تكرارية، على سبيل المثال، أعداد فيبوناتشي .
إيجاد علاقات تكرارية للمتتاليات - قد يوحي شكل الدالة المولدة بصيغة تكرارية.
إيجاد العلاقات بين المتتاليات - إذا كانت الدوال المولدة لمتتاليتين لها شكل مشابه، فقد تكون المتتاليات نفسها مرتبطة.
استكشف السلوك التقاربي للمتتاليات.
إثبات المتطابقات التي تتضمن متواليات.
حل مسائل التعداد في التوافقية وتشفير حلولها. تعد كثيرات حدود الرخ مثالاً على تطبيق في التوافقية.
قم بتقييم المجاميع اللانهائية.

تقنيات متنوعة: تقييم المجاميع ومعالجة المشكلات الأخرى باستخدام الدوال المولدة

مثال 1: صيغة مجموع الأعداد التوافقية

توفر لنا الدوال المولدة عدة طرق لمعالجة المجاميع ولتحديد الهويات بين المجاميع.

تحدث أبسط حالة عندما يكون $s n = Σ n k = 0 a k$ . عندئذٍ نعلم أن $S (z) = ⁠ A (z) / 1 - z ⁠$ للدوال المولدة العادية المناظرة.

على سبيل المثال، يمكننا التلاعب $s_{n}=\sum _{k=1}^{n}H_{k}\,,$ حيث $H k = 1 + 1 / 2 + \dots + 1 / k هي$ الأعداد التوافقية . $H(z)=\sum _{n=1}^{\infty }{H_{n}z^{n}}$ لتكن دالة التوليد العادية للأعداد التوافقية. إذن $H(z)={\frac {1}{1-z}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,,$ وبالتالي $S(z)=\sum _{n=1}^{\infty }{s_{n}z^{n}}={\frac {1}{(1-z)^{2}}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,.$

استخدام ${\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}\,,$ ينتج عن عملية الالتفاف مع البسط $s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,,$ والتي يمكن كتابتها أيضاً على النحو التالي $\sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,.$

مثال 2: مجموع معاملات ذات الحدين المعدلة وتحويل ذات الحدين

كمثال آخر على استخدام الدوال المولدة لربط المتتاليات ومعالجة المجاميع، بالنسبة لمتتالية عشوائية $⟨ f n ⟩،$ نُعرّف متتاليتي المجاميع التاليتين: ${\begin{aligned}s_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}f_{m}3^{n-m}\\[4px]{\tilde {s}}_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}(m+1)(m+2)(m+3)f_{m}3^{n-m}\,,\end{aligned}}$ لكل $n \geq 0$ ، نسعى إلى التعبير عن المجاميع الثانية بدلالة المجاميع الأولى. نقترح منهجًا يعتمد على الدوال المولدة.

أولاً، نستخدم تحويل ذات الحدين لكتابة الدالة المولدة للمجموع الأول على النحو التالي: $S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}}\right).$

بما أن الدالة المولدة للمتتالية $⟨ (n + 1)(n + 2)(n + 3) f n ⟩$ معطاة بـ $6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)$ يمكننا كتابة الدالة المولدة للمجموع الثاني المعرف أعلاه بالشكل التالي ${\tilde {S}}(z)={\frac {6}{(1-3z)}}F\left({\frac {z}{1-3z}}\right)+{\frac {18z}{(1-3z)^{2}}}F'\left({\frac {z}{1-3z}}\right)+{\frac {9z^{2}}{(1-3z)^{3}}}F''\left({\frac {z}{1-3z}}\right)+{\frac {z^{3}}{(1-3z)^{4}}}F'''\left({\frac {z}{1-3z}}\right).$

على وجه الخصوص، يمكننا كتابة دالة توليد المجموع المعدلة هذه على النحو التالي: $a(z)\cdot S(z)+b(z)\cdot zS'(z)+c(z)\cdot z^{2}S''(z)+d(z)\cdot z^{3}S'''(z),$ for $a (z) = 6(1 - 3 z) 3$ , $b (z) = 18(1 - 3 z) 3$ , $c (z) = 9(1 - 3 z) 3$ , and $d (z) = (1 - 3 z) 3$ , where $(1 - 3 z) 3 = 1 - 9 z + 27 z 2 - 27 z 3$ .

وأخيراً، يترتب على ذلك أنه يمكننا التعبير عن المجموع الثاني من خلال المجموع الأول بالشكل التالي: ${\begin{aligned}{\tilde {s}}_{n}&=[z^{n}]\left(6(1-3z)^{3}\sum _{n=0}^{\infty }s_{n}z^{n}+18(1-3z)^{3}\sum _{n=0}^{\infty }ns_{n}z^{n}+9(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)s_{n}z^{n}+(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)(n-2)s_{n}z^{n}\right)\\[4px]&=(n+1)(n+2)(n+3)s_{n}-9n(n+1)(n+2)s_{n-1}+27(n-1)n(n+1)s_{n-2}-(n-2)(n-1)ns_{n-3}.\end{aligned}}$

مثال 3: الدوال المولدة للمتتاليات المتكررة المتبادلة

في هذا المثال، نعيد صياغة مثال الدالة المولدة الوارد في القسم 7.3 من كتاب الرياضيات الملموسة (انظر أيضًا القسم 7.1 من المرجع نفسه للاطلاع على رسوم توضيحية لمتسلسلات الدوال المولدة). على وجه الخصوص، لنفترض أننا نبحث عن العدد الإجمالي للطرق (المُشار إليه بـ $U n$ ) لتبليط مستطيل أبعاده 3× $n$ بقطع دومينو غير مُعلَّمة أبعادها 2×1. لنُعرِّف المتتالية المساعدة، $V n$ ، بأنها عدد الطرق لتغطية مستطيل أبعاده 3× $n$ باستثناء جزء الزاوية من المستطيل الكامل. نسعى إلى استخدام هذه التعريفات لإعطاء صيغة مغلقة لـ $U n$ دون تفصيل هذا التعريف أكثر للتعامل مع حالات قطع الدومينو الرأسية مقابل الأفقية. لاحظ أن الدوال المولدة العادية لمتتاليتينا تُطابق المتسلسلة التالية: ${\begin{aligned}U(z)=1+3z^{2}+11z^{4}+41z^{6}+\cdots ,\\V(z)=z+4z^{3}+15z^{5}+56z^{7}+\cdots .\end{aligned}}$

إذا نظرنا في التكوينات الممكنة التي يمكن إعطاؤها بدءًا من الحافة اليسرى للمستطيل 3× $n$ ، فسنتمكن من التعبير عن علاقات التكرار المتبادلة أو المتكررة المتبادلة التالية لمتتاليتينا عندما $n \geq 2$ المعرفة كما هو موضح أعلاه حيث $U 0 = 1$ ، $U 1 = 0$ ، $V 0 = 0$ ، و $V 1 = 1$ : ${\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned}}$

بما أن لدينا أنه بالنسبة لجميع الأعداد الصحيحة $m \geq 0$ ، فإن الدوال المولدة ذات الفهرس المزاح تحقق ^{[ ملاحظة 1 ]} $z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\,,$ يمكننا استخدام الشروط الابتدائية المحددة أعلاه وعلاقتي التكرار السابقتين لنرى أن لدينا المعادلتين التاليتين اللتين تربطان الدوال المولدة لهذه المتتاليات المعطاة بواسطة ${\begin{aligned}U(z)&=2zV(z)+z^{2}U(z)+1\\V(z)&=zU(z)+z^{2}V(z)={\frac {z}{1-z^{2}}}U(z),\end{aligned}}$ وهذا يعني، من خلال حل نظام المعادلات (وهذه هي الحيلة الخاصة بطريقتنا هنا)، أن $U(z)={\frac {1-z^{2}}{1-4z^{2}+z^{4}}}={\frac {1}{3-{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2+{\sqrt {3}}\right)z^{2}}}+{\frac {1}{3+{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2-{\sqrt {3}}\right)z^{2}}}.$

وبالتالي، من خلال إجراء تبسيطات جبرية على المتتالية الناتجة عن توسعات الكسور الجزئية الثانية للدالة المولدة في المعادلة السابقة، نجد أن $U 2 n + 1 \equiv 0$ وأن $U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}}\right)^{n}}{3-{\sqrt {3}}}}\right\rceil \,,$ لجميع الأعداد الصحيحة $n \geq 0. ونلاحظ أيضًا أن تقنية دالة التوليد المزاحة نفسها المطبقة على$ التكرار من الدرجة الثانية لأعداد فيبوناتشي هي المثال النموذجي لاستخدام دوال التوليد لحل علاقات التكرار في متغير واحد والتي تمت تغطيتها بالفعل، أو على الأقل التلميح إليها، في القسم الفرعي المتعلق بالدوال الكسرية المذكور أعلاه.

الالتفاف (منتجات كوشي)

يؤدي الالتفاف المنفصل للحدود في سلسلتين قوى رسميتين إلى تحويل ناتج الدوال المولدة إلى دالة مولدة تحصي مجموعًا ملتفًا لحدود التسلسل الأصلي (انظر ناتج كوشي ).

لنفترض أن $A (z)$ و $B (z)$ دالتان مولدتان عاديتان. $C(z)=A(z)B(z)\Leftrightarrow [z^{n}]C(z)=\sum _{k=0}^{n}{a_{k}b_{n-k}}$
لنفترض أن $A (z)$ و $B (z)$ هما دالتان مولدتان أسيّتان. $C(z)=A(z)B(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}}\right]C(z)=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k}$
لنفترض المتتالية الملتفة ثلاثياً الناتجة عن حاصل ضرب ثلاث دوال توليد عادية $C(z)=F(z)G(z)H(z)\Leftrightarrow [z^{n}]C(z)=\sum _{j+k+l=n}f_{j}g_{k}h_{l}$
ضع في اعتبارك التسلسل الملتف ثلاثيًا الناتج عن ضرب ثلاث دوال توليد أسية ^{[ 23 ]} $C(z)=F(z)G(z)H(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}}\right]C(z)=\sum _{j+k+l=n}{\frac {n!}{j!k!l!}}f_{j}g_{k}h_{l}$
ضع في اعتبارك عملية الالتفاف $m$ -fold لمتتالية مع نفسها لبعض الأعداد الصحيحة الموجبة $m \geq 1$ (انظر المثال أدناه للتطبيق). $C(z)=G(z)^{m}\Leftrightarrow [z^{n}]C(z)=\sum _{k_{1}+k_{2}+\cdots +k_{m}=n}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}$

يمكن أن يتوافق ضرب الدوال المولدة، أو التفاف متوالياتها الأساسية، مع مفهوم الأحداث المستقلة في بعض سيناريوهات العد والاحتمالات. على سبيل المثال، إذا اعتمدنا الاصطلاح الرمزي بأن دالة توليد الاحتمالات ، أو pgf ، لمتغير عشوائي $Z$ يُرمز لها بـ $GZ (z) ،$ فيمكننا إثبات أنه لأي متغيرين عشوائيين ^{[ 24 ]} $G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,,$ إذا كان $X$ و $Y$ مستقلين.

مثال: مشكلة صرف العملات

عدد طرق دفع $n \geq 0$ سنتًا بفئات العملات المعدنية ذات القيم في المجموعة ${1، 5، 10، 25، 50}$ (أي، بالبنسات، والنيكل، والدايمات، والربع دولار، ونصف الدولار)، حيث نميز الحالات بناءً على العدد الإجمالي لكل عملة معدنية وليس على ترتيب تقديم العملات المعدنية، يُعطى بواسطة الدالة المولدة العادية ${\frac {1}{1-z}}{\frac {1}{1-z^{5}}}{\frac {1}{1-z^{10}}}{\frac {1}{1-z^{25}}}{\frac {1}{1-z^{50}}}\,.$ عندما نميز أيضًا بناءً على ترتيب عرض العملات (على سبيل المثال، بنس واحد ثم خمسة سنتات يختلف عن خمسة سنتات ثم بنس واحد)، فإن الدالة المولدة العادية هي ${\frac {1}{1-z-z^{5}-z^{10}-z^{25}-z^{50}}}\,.$

إذا سمحنا بدفع مبلغ $n سنت بعملات معدنية من$ أي فئة عددية صحيحة موجبة، فإننا نصل إلى دالة التقسيم، وهي دالة توليد عادية موسعة بواسطة حاصل ضرب رمز بوخامر- $q$ اللانهائي . $\prod _{n=1}^{\infty }\left(1-z^{n}\right)^{-1}\,.$ عندما يكون ترتيب العملات المعدنية مهمًا، فإن دالة التوليد العادية هي ${\frac {1}{1-\sum _{n=1}^{\infty }z^{n}}}={\frac {1-z}{1-2z}}\,.$

مثال: دالة توليد الأرقام الكاتالونية

يُتيح لنا مثالٌ يُفيد فيه استخدام التفاف الدوال المولدة إيجاد دالة مغلقة مُحددة تُمثل الدالة المولدة العادية لأعداد كاتالان ، $C n$ . وعلى وجه الخصوص، يُمكن تفسير هذه المتتالية توافقيًا على أنها عدد طرق إدخال الأقواس في حاصل ضرب $x 0 \cdot x 1 \cdot ... \cdot x n$ بحيث يكون ترتيب الضرب مُحددًا تمامًا. على سبيل المثال، $C 2 = 2،$ وهو ما يُقابل التعبيرين $x 0 \cdot (x 1 \cdot x 2)$ و $(x 0 \cdot x 1 ) \cdot x 2$ . وبالتالي، تُحقق المتتالية علاقة تكرارية مُعطاة بـ $C_{n}=\sum _{k=0}^{n-1}C_{k}C_{n-1-k}+\delta _{n,0}=C_{0}C_{n-1}+C_{1}C_{n-2}+\cdots +C_{n-1}C_{0}+\delta _{n,0}\,,\quad n\geq 0\,,$ وبالتالي، فإن لها دالة توليد ملتفة مقابلة، $C (z)$ ، تحقق $C(z)=z\cdot C(z)^{2}+1\,.$

بما أن $C (0) = 1 \neq \infty$ ، فإننا نصل إلى صيغة لهذه الدالة المولدة معطاة بـ $C(z)={\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}z^{n}\,.$

لاحظ أن المعادلة الأولى التي تُعرّف $C (z)$ ضمنيًا أعلاه تعني أن $C(z)={\frac {1}{1-z\cdot C(z)}}\,,$ مما يؤدي بعد ذلك إلى توسيع كسري مستمر "بسيط" آخر (من حيث الشكل) لهذه الدالة المولدة.

مثال: الأشجار الممتدة للمراوح والالتفافات للالتفافات

تُعرَّف المروحة من الرتبة $n$ بأنها رسم بياني على الرؤوس ${0، 1، ...، n}$ مع $2n - 1 حافة$ متصلة وفقًا للقواعد التالية: الرأس 0 متصل بحافة واحدة بكل رأس من الرؤوس $n$ الأخرى ، والرأس $k$ تتصل كل مجموعة فرعية من المجموعة الفرعية n برأسها التالي $k + 1$ عبر حافة واحدة، وذلك لجميع قيم $k حيث 1 \leq k < n$ . ^{[ 25 ]} يوجد مجموعة فرعية واحدة من المجموعة الفرعية n، وثلاث مجموعات فرعية من المجموعة الفرعية n، وثماني مجموعات فرعية من المجموعة الفرعية n، وهكذا. الشجرة الممتدة هي رسم بياني فرعي من رسم بياني يحتوي على جميع الرؤوس الأصلية، ويحتوي على عدد كافٍ من الحواف لجعل هذا الرسم البياني الفرعي متصلاً، ولكن ليس عددًا كبيرًا من الحواف بحيث تتكون دورة في الرسم البياني الفرعي. نسأل: كم عدد الأشجار الممتدة $f n$ الممكنة لمجموعة فرعية من المجموعة الفرعية $n$ لكل $n \geq 1$ ؟

كملاحظة، يمكننا معالجة المسألة بحساب عدد طرق ربط مجموعات الرؤوس المتجاورة. على سبيل المثال، عندما $n = 4$ ، يكون لدينا $f₄ = 4 + 3 \times 1 + 2 \times 2 + 1 \times 3 + 2 \times 1 \times 1 + 1 \times 2 \times 1 + 1 \times 1 \times 2 + 1 \times 1 \times 1 \times 1 = 21$ ، وهو مجموع الالتفافات $m$ -fold للمتتالية $gₙ = n = [zₙ] z / (1 - z) ² ،$ حيث $m ≔ 1، 2، 3، 4. وبشكل أعم$ $،$ يمكننا كتابة صيغة لهذه المتتالية على النحو التالي $:$ $f_{n}=\sum _{m>0}\sum _{\scriptstyle k_{1}+k_{2}+\cdots +k_{m}=n \atop \scriptstyle k_{1},k_{2},\ldots ,k_{m}>0}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}\,,$ ومن ذلك نرى أن الدالة المولدة العادية لهذه المتتالية تُعطى بواسطة مجموع الالتفافات التالي كما يلي $F(z)=G(z)+G(z)^{2}+G(z)^{3}+\cdots ={\frac {G(z)}{1-G(z)}}={\frac {z}{(1-z)^{2}-z}}={\frac {z}{1-3z+z^{2}}}\,,$ ومن خلال ذلك نستطيع استخلاص صيغة دقيقة للمتتالية عن طريق أخذ توسيع الكسور الجزئية للدالة المولدة الأخيرة.

الدوال المولدة الضمنية وصيغة لاغرانج العكسية

كثيرًا ما نجد دوالًا مولدة محددة بمعادلة دالية، بدلًا من تحديدها صراحةً. على سبيل المثال، الدالة المولدة $T(z)$ لعدد الأشجار الثنائية على $n$ عقدة (بما في ذلك الأوراق) تحقق ما يلي:

$T(z)=z\left(1+T(z)^{2}\right)$

تُعد نظرية لاغرانج العكسية أداة تُستخدم لتقييم حلول هذه المعادلات بشكل صريح.

صيغة لاغرانج العكسية — ليكن ${\textstyle \phi (z)\in C[[z]]}$ لتكن متسلسلة قوى رسمية ذات حد ثابت غير صفري. عندئذٍ تكون المعادلة الوظيفية $T(z)=z\phi (T(z))$ يُقرّ بوجود حل فريد في ${\textstyle T(z)\in C[[z]]}$ ، وهو ما يرضي

$[z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(\phi (z))^{n}$

حيث الترميز $[z^{n}]F(z)$ يُعيد معامل $z^{n}$ في $F(z)$ .

بتطبيق النظرية المذكورة أعلاه على معادلتنا الوظيفية، نحصل على (مع ${\textstyle \phi (z)=1+z^{2}}$ ):

$[z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}$

عن طريق توسيع نظرية ذات الحدين ، للأعداد الزوجية $n$ ، تُرجع الصيغة $0$ هذا متوقع، إذ يمكن إثبات أن عدد أوراق الشجرة الثنائية يزيد بواحد عن عدد عقدها الداخلية، لذا يجب أن يكون المجموع الكلي دائمًا عددًا فرديًا. $n$ ومع ذلك، نحصل على

$[z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}={\frac {1}{n}}{\dbinom {n}{\frac {n+1}{2}}}$

يصبح التعبير أكثر دقة إذا تركنا $n$ ليكن عدد العقد الداخلية: الآن يصبح التعبير ببساطة $n$ ^{الرقم الكتالوني} .

إدخال مُعامل حر (طريقة الوهم)

أحيانًا يكون المجموع $s n$ معقدًا، وليس من السهل دائمًا حسابه. طريقة "المعامل الحر" هي طريقة أخرى (أطلق عليها هـ. ويلف اسم "الخداع") لحساب هذه المجاميع.

كلا الطريقتين اللتين نوقشتا حتى الآن تُعتبران $n$ حدًا في عملية الجمع. عندما لا يظهر n صراحةً في عملية الجمع، يمكننا اعتباره مُعاملًا "حرًا" والتعامل مع $s$ $$ $n$ كمُعامل للدالة $F$ $($ $z$ $) = Σ s$ $n$ $$ $z$ $n$ ، وتغيير ترتيب عمليات الجمع على $n$ و $k$ ، ومحاولة حساب المجموع الداخلي.

على سبيل المثال، إذا أردنا حساب $s_{n}=\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\,,\quad m,n\in \mathbb {N} _{0}\,,$ يمكننا اعتبار $n$ كمعامل "حر"، وتعيين $F(z)=\sum _{n=0}^{\infty }{\left(\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\right)}z^{n}\,.$

يؤدي تبادل المجموع ("زيت الأفعى") إلى $F(z)=\sum _{k=0}^{\infty }{{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-k}}\sum _{n=0}^{\infty }{{\binom {n+k}{m+2k}}z^{n+k}}\,.$

الآن، المجموع الداخلي هو $⁠$ $z$ $m$ $+ 2$ $k$ $/$ $(1 -$ $z$ $)$ $m$ $+ 2$ $k$ $+ 1$ $⁠$ . وبالتالي ${\begin{aligned}F(z)&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{C_{k}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}{\frac {1-{\sqrt {1+{\frac {4z}{(1-z)^{2}}}}}}{\frac {-2z}{(1-z)^{2}}}}\\[4px]&={\frac {-z^{m-1}}{2(1-z)^{m-1}}}\left(1-{\frac {1+z}{1-z}}\right)\\[4px]&={\frac {z^{m}}{(1-z)^{m}}}=z{\frac {z^{m-1}}{(1-z)^{m}}}\,.\end{aligned}}$

ثم نحصل على $s_{n}={\begin{cases}\displaystyle {\binom {n-1}{m-1}}&{\text{for }}m\geq 1\,,\\{}[n=0]&{\text{for }}m=0\,.\end{cases}}$

من المفيد استخدام نفس الطريقة مرة أخرى للمجموع، ولكن هذه المرة نأخذ $m$ كمعامل حر بدلاً من $n$ . وهكذا نضع $G(z)=\sum _{m=0}^{\infty }\left(\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}\right)z^{m}\,.$

يؤدي تبادل المجموع ("زيت الأفعى") إلى $G(z)=\sum _{k=0}^{\infty }{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-2k}\sum _{m=0}^{\infty }{\binom {n+k}{m+2k}}z^{m+2k}\,.$

الآن، المجموع الداخلي هو $(1 + z) n + k$ . وبالتالي ${\begin{aligned}G(z)&=(1+z)^{n}\sum _{k=0}^{\infty }{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-(1+z)}{z^{2}}}\right)^{k}\\[4px]&=(1+z)^{n}\sum _{k=0}^{\infty }C_{k}\,\left({\frac {-(1+z)}{z^{2}}}\right)^{k}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&=(1+z)^{n}\,{\frac {1-{\sqrt {1+{\frac {4(1+z)}{z^{2}}}}}}{\frac {-2(1+z)}{z^{2}}}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z{\sqrt {z^{2}+4+4z}}}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z(z+2)}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {-2z}{-2(1+z)}}=z(1+z)^{n-1}\,.\end{aligned}}$

وهكذا نحصل على $s_{n}=\left[z^{m}\right]z(1+z)^{n-1}=\left[z^{m-1}\right](1+z)^{n-1}={\binom {n-1}{m-1}}\,,$ بالنسبة لـ $m \geq 1$ كما كان من قبل.

تُثبت الدوال المولدة التطابقات

نقول إن دالتين مولدتين (متسلسلتين قوى) متطابقتان بتردد $m$ ، ويكتب $A (z) \equiv B (z) (mod m)،$ إذا كانت معاملاتهما متطابقة بتردد $m$ لجميع قيم $n \geq 0$ ، أي $a n \equiv b n (mod m)$ لجميع الحالات ذات الصلة للأعداد الصحيحة $n$ (لاحظ أنه ليس من الضروري افتراض أن $m$ عدد صحيح هنا، فقد تكون دالة متعددة الحدود بدلالة $x$ غير محددة ، على سبيل المثال). إذا كانت الدالة المولدة "الأبسط" في الطرف الأيمن، $B (z)$ ، دالة كسرية لـ $z$ ، فإن شكل هذه المتتالية يشير إلى أن المتتالية دورية في النهاية بتردد ثابت في حالات خاصة من قيم $m الصحيحة \geq 2.$ على سبيل المثال، يمكننا إثبات أن أعداد أويلر ، $\langle E_{n}\rangle =\langle 1,1,5,61,1385,\ldots \rangle \longmapsto \langle 1,1,2,1,2,1,2,\ldots \rangle {\pmod {3}}\,,$ تحقق التطابق التالي بتردد 3: ^{[ 26 ]} $\sum _{n=0}^{\infty }E_{n}z^{n}={\frac {1-z^{2}}{1+z^{2}}}{\pmod {3}}\,.$

إحدى الطرق المفيدة للحصول على تطابقات للمتتاليات المُعَدَّة بواسطة دوال توليد خاصة بتردد أي أعداد صحيحة (أي ليس فقط قوى الأعداد الأولية $p و k$ ) مُوضَّحة في القسم الخاص بتمثيلات الكسور المستمرة لدوال التوليد العادية (حتى غير المتقاربة) بواسطة كسور $J$ المذكورة أعلاه. نذكر فيما يلي نتيجةً محددةً تتعلق بمتسلسلات التوليد المُوسَّعة من خلال تمثيل بواسطة كسر مستمر من محاضرات لاندو حول دوال التوليد :

نظرية: تطابقات المتسلسلات المولدة بواسطة مفكوكات الكسور المستمرة — لنفترض أن الدالة المولدة $A (z)$ ممثلة بكسر مستمر لانهائي على الصورة $A(z)={\cfrac {1}{1-c_{1}z-{\cfrac {p_{1}z^{2}}{1-c_{2}z-{\cfrac {p_{2}z^{2}}{1-c_{3}z-{\ddots }}}}}}}$ وأن $A p (z)$ يرمز إلى التقارب $p$ لهذا التوسع الكسري المستمر المعرف بحيث يكون $a n = [z n] A p (z)$ لجميع $0 \leq n < 2 p$ . إذن:

الدالة $A p (z)$ هي دالة نسبية لجميع $قيم p \geq 2$ حيث نفترض أن أحد معايير قابلية القسمة لـ $p | p 1 ، p 1 p 2 ، p 1 p 2 p 3$ متحقق، أي $p | p 1 p 2 \dots p k$ لبعض $k \geq 1$ ؛ و
إذا كان العدد الصحيح $p$ يقسم حاصل ضرب $p 1 p 2 \dots p k$ ، فإن لدينا $A (z) \equiv A k (z) (mod p)$ .

تُستخدم الدوال المولدة أيضًا في إثبات تطابق معاملاتها. نذكر المثالين التاليين اللذين يستنتجان تطابقات خاصة لأعداد ستيرلينغ من النوع الأول ولدالة التقسيم $p (n)،$ مما يُظهر تنوع الدوال المولدة في معالجة المسائل التي تتضمن متتابعات الأعداد الصحيحة .

أعداد ستيرلينغ بتردد الأعداد الصحيحة الصغيرة

المقال الرئيسي حول أعداد ستيرلينغ الناتجة عن المنتجات المحدودة $S_{n}(x):=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}=x(x+1)(x+2)\cdots (x+n-1)\,,\quad n\geq 1\,,$

يقدم هذا القسم نظرة عامة على التطابقات لهذه الأعداد المستمدة حصراً من خصائص دالتها المولدة، كما ورد في القسم 4.6 من مرجع ويلف الأساسي " علم الدوال المولدة ". نكرر الحجة الأساسية ونلاحظ أنه عند اختزال هذه الدوال المولدة ذات الجداء المحدود بتردد 2، فإنها تحقق جميعاً الشروط التالية.

$S_{n}(x)=[x(x+1)]\cdot [x(x+1)]\cdots =x^{\left\lceil {\frac {n}{2}}\right\rceil }(x+1)^{\left\lfloor {\frac {n}{2}}\right\rfloor }\,,$

وهذا يعني أن زوجية أعداد ستيرلينغ هذه تتطابق مع زوجية معامل ذي الحدين

${\begin{bmatrix}n\\k\end{bmatrix}}\equiv {\binom {\left\lfloor {\frac {n}{2}}\right\rfloor }{k-\left\lceil {\frac {n}{2}}\right\rceil }}{\pmod {2}}\,,$

وبالتالي يظهر أن $[n k]$ زوجي عندما يكون $k < ⌊ ⁠ n / 2 ⁠ ⌋$ .

وبالمثل، يمكننا اختزال نواتج الطرف الأيمن التي تحدد دوال توليد أعداد ستيرلينغ بتردد 3 للحصول على تعابير أكثر تعقيدًا بعض الشيء، بشرط أن ${\begin{aligned}{\begin{bmatrix}n\\m\end{bmatrix}}&\equiv [x^{m}]\left(x^{\left\lceil {\frac {n}{3}}\right\rceil }(x+1)^{\left\lceil {\frac {n-1}{3}}\right\rceil }(x+2)^{\left\lfloor {\frac {n}{3}}\right\rfloor }\right)&&{\pmod {3}}\\&\equiv \sum _{k=0}^{m}{\begin{pmatrix}\left\lceil {\frac {n-1}{3}}\right\rceil \\k\end{pmatrix}}{\begin{pmatrix}\left\lfloor {\frac {n}{3}}\right\rfloor \\m-k-\left\lceil {\frac {n}{3}}\right\rceil \end{pmatrix}}\times 2^{\left\lceil {\frac {n}{3}}\right\rceil +\left\lfloor {\frac {n}{3}}\right\rfloor -(m-k)}&&{\pmod {3}}\,.\end{aligned}}$

تطابقات دالة التقسيم

في هذا المثال، نستعين ببعض آليات الضرب اللانهائي التي تُولّد متسلسلات قوى لها متسلسلات العديد من الدوال الخاصة ، ونُحصي دوال التقسيم. على وجه الخصوص، نُذكّر بأن دالة التقسيم $p (n)$ تُولّد بواسطة الضرب الرمزي المتبادل اللانهائي $q$ -Pochhammer (أو الضرب الرمزي $z$ -Pochhammer حسب الحالة) المُعطى بـ ${\begin{aligned}\sum _{n=0}^{\infty }p(n)z^{n}&={\frac {1}{\left(1-z\right)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots }}\\[4pt]&=1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^{6}+\cdots .\end{aligned}}$

تحقق دالة التقسيم هذه العديد من خصائص التطابق المعروفة ، والتي تشمل على وجه الخصوص النتائج التالية على الرغم من وجود العديد من الأسئلة المفتوحة حول أشكال التطابقات الصحيحة ذات الصلة للدالة: ^{[ 27 ]} ${\begin{aligned}p(5m+4)&\equiv 0{\pmod {5}}\\p(7m+5)&\equiv 0{\pmod {7}}\\p(11m+6)&\equiv 0{\pmod {11}}\\p(25m+24)&\equiv 0{\pmod {5^{2}}}\,.\end{aligned}}$

نوضح كيفية استخدام الدوال المولدة ومعالجة التطابقات لسلاسل القوى الرسمية لتقديم برهان أولي للغاية لأول هذه التطابقات المذكورة أعلاه.

أولاً، نلاحظ أنه في دالة توليد معاملات ذات الحدين ${\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,,$ جميع المعاملات قابلة للقسمة على 5 باستثناء تلك التي تتوافق مع القوى $1، z 5 ، z 10 ، ...$ وعلاوة على ذلك، في هذه الحالات يكون باقي قسمة المعامل هو 1 بتردد 5. وبالتالي، ${\frac {1}{(1-z)^{5}}}\equiv {\frac {1}{1-z^{5}}}{\pmod {5}}\,,$ أو ما يعادل ذلك ${\frac {1-z^{5}}{(1-z)^{5}}}\equiv 1{\pmod {5}}\,.$ ويترتب على ذلك أن ${\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\left(1-z^{15}\right)\cdots }{\left((1-z)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots \right)^{5}}}\equiv 1{\pmod {5}}\,.$

باستخدام توسعات الضرب اللانهائية لـ $z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(1-z\right)\left(1-z^{2}\right)\cdots }}=z\cdot \left((1-z)\left(1-z^{2}\right)\cdots \right)^{4}\times {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(\left(1-z\right)\left(1-z^{2}\right)\cdots \right)^{5}}}\,,$ يمكن إثبات أن معامل $z 5 m + 5$ في $z \cdot ((1 - z)(1 - z 2)\dots) 4$ يقبل القسمة على 5 لجميع قيم $m$ . ^{[ 28 ]} وأخيرًا، بما أن ${\begin{aligned}\sum _{n=1}^{\infty }p(n-1)z^{n}&={\frac {z}{(1-z)\left(1-z^{2}\right)\cdots }}\\[6px]&=z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{(1-z)\left(1-z^{2}\right)\cdots }}\times \left(1+z^{5}+z^{10}+\cdots \right)\left(1+z^{10}+z^{20}+\cdots \right)\cdots \end{aligned}}$ يمكننا مساواة معاملات $z 5 m + 5$ في المعادلات السابقة لإثبات نتيجة التطابق المطلوبة، وهي أن $p (5 m + 4) \equiv 0 (mod 5)$ لجميع $m \geq 0$ .

تحويلات الدوال المولدة

توجد عدة تحويلات للدوال المولدة تُتيح تطبيقات أخرى (انظر المقال الرئيسي ). يوفر تحويل الدالة المولدة العادية (OGF) لمتتالية ما طريقةً لتحويل الدالة المولدة لمتتالية إلى دالة مولدة تُحصي متتاليةً أخرى. تتضمن هذه التحويلات عادةً صيغًا تكاملية تتضمن الدالة المولدة العادية للمتتالية (انظر التحويلات التكاملية ) أو مجاميع مرجحة على المشتقات العليا لهذه الدوال (انظر تحويلات المشتقات ).

يمكن استخدام تحويلات الدوال المولدة عندما نسعى إلى التعبير عن دالة مولدة للمجاميع. $s_{n}:=\sum _{m=0}^{n}{\binom {n}{m}}C_{n,m}a_{m},$

على شكل $S (z) = g (z) A (f (z))$ ، حيث تمثل f(z) دالة توليد المتتالية الأصلية. على سبيل المثال، إذا كانت المجاميع هي $s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\,$ ثم يتم إعطاء الدالة المولدة لتعبيرات المجموع المعدلة بواسطة ^{[ 29 ]} $S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}}\right)$ (انظر أيضًا إلى التحويل ذي الحدين وتحويل ستيرلينغ ).

توجد أيضًا صيغ تكاملية للتحويل بين دالة التوليد العامة (OGF) لمتتالية ما، $F (z)$ ، ودالة التوليد الأسية (EGF)، $F̂ (z)$ ، والعكس، معطاة بواسطة ${\begin{aligned}F(z)&=\int _{0}^{\infty }{\hat {F}}(tz)e^{-t}\,dt\,,\\[4px]{\hat {F}}(z)&={\frac {1}{2\pi }}\int _{-\pi }^{\pi }F\left(ze^{-i\vartheta }\right)e^{e^{i\vartheta }}\,d\vartheta \,,\end{aligned}}$

بشرط أن تتقارب هذه التكاملات لقيم مناسبة لـ $z$ .

جداول الدوال المولدة الخاصة

تجد هنا قائمة أولية بالمتسلسلات الرياضية الخاصة . كما تجد عددًا من دوال توليد المتتابعات المفيدة والخاصة في القسمين 5.4 و7.4 من كتاب الرياضيات الملموسة ، وفي القسم 2.5 من كتاب ويلف " علم دوال التوليد" . وتشمل دوال التوليد الخاصة الأخرى الجديرة بالذكر المدخلات الواردة في الجدول التالي، وهو ليس شاملاً بأي حال من الأحوال. ^{[ 30 ]}

سلسلة القوى الرسمية	صيغة الدالة المولدة	ملحوظات
$\sum _{n=0}^{\infty }{\binom {m+n}{n}}\left(H_{n+m}-H_{m}\right)z^{n}$	${\frac {1}{(1-z)^{m+1}}}\ln {\frac {1}{1-z}}$	$H_{n}$ هو عدد توافقي من الدرجة الأولى
$\sum _{n=0}^{\infty }B_{n}{\frac {z^{n}}{n!}}$	${\frac {z}{e^{z}-1}}$	$B_{n}$ هو عدد برنولي
$\sum _{n=0}^{\infty }F_{mn}z^{n}$	${\frac {F_{m}z}{1-(F_{m-1}+F_{m+1})z+(-1)^{m}z^{2}}}$	$F_{n}$ هو عدد فيبوناتشي و $m\in \mathbb {Z} ^{+}$
$\sum _{n=0}^{\infty }\left\{{\begin{matrix}n\\m\end{matrix}}\right\}z^{n}$	$(z^{-1})^{\overline {-m}}={\frac {z^{m}}{(1-z)(1-2z)\cdots (1-mz)}}$	$x^{\overline {n}}$ يرمز إلى المضروب التصاعدي ، أو رمز بوخامر، وعدد صحيح ما $m\geq 0$
$\sum _{n=0}^{\infty }\left[{\begin{matrix}n\\m\end{matrix}}\right]z^{n}$	$z^{\overline {m}}=z(z+1)\cdots (z+m-1)$
$\sum _{n=1}^{\infty }{\frac {(-1)^{n-1}4^{n}(4^{n}-2)B_{2n}z^{2n}}{(2n)\cdot (2n)!}}$	$\ln {\frac {\tan(z)}{z}}$
$\sum _{n=0}^{\infty }{\frac {(1/2)^{\overline {n}}z^{2n}}{(2n+1)\cdot n!}}$	$z^{-1}\arcsin(z)$
$\sum _{n=0}^{\infty }H_{n}^{(s)}z^{n}$	${\frac {\operatorname {Li} _{s}(z)}{1-z}}$	$\operatorname {Li} _{s}(z)$ هي دالة متعددة اللوغاريتمات و $H_{n}^{(s)}$ هو عدد توافقي معمّم لـ $\Re (s)>1$
$\sum _{n=0}^{\infty }n^{m}z^{n}$	$\sum _{0\leq j\leq m}\left\{{\begin{matrix}m\\j\end{matrix}}\right\}{\frac {j!\cdot z^{j}}{(1-z)^{j+1}}}$	$\left\{{\begin{matrix}n\\m\end{matrix}}\right\}$ هو عدد ستيرلينغ من النوع الثاني ، حيث تحقق الحدود الفردية في التوسع ${\frac {z^{i}}{(1-z)^{i+1}}}=\sum _{k=0}^{i}{\binom {i}{k}}{\frac {(-1)^{k-i}}{(1-z)^{k+1}}}$
$\sum _{k<n}{\binom {n-k}{k}}{\frac {n}{n-k}}z^{k}$	$\left({\frac {1+{\sqrt {1+4z}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {1+4z}}}{2}}\right)^{n}$
$\sum _{n_{1},\ldots ,n_{m}\geq 0}\min(n_{1},\ldots ,n_{m})z_{1}^{n_{1}}\cdots z_{m}^{n_{m}}$	${\frac {z_{1}\cdots z_{m}}{(1-z_{1})\cdots (1-z_{m})(1-z_{1}\cdots z_{m})}}$	تُعطى حالة المتغيرين بالصيغة التالية $M(w,z):=\sum _{m,n\geq 0}\min(m,n)w^{m}z^{n}={\frac {wz}{(1-w)(1-z)(1-wz)}}$
$\sum _{n=0}^{\infty }{\binom {s}{n}}z^{n}$	$(1+z)^{s}$	$s\in \mathbb {C}$
$\sum _{n=0}^{\infty }{\binom {n}{k}}z^{n}$	${\frac {z^{k}}{(1-z)^{k+1}}}$	$k\in \mathbb {N}$
$\sum _{n=1}^{\infty }\log {(n)}z^{n}$	$\left.-{\frac {\partial }{\partial s}}\operatorname {{Li}_{s}(z)} \right\|_{s=0}$

انظر أيضاً

ملحوظات

↑ بالمناسبة، لدينا أيضًا صيغة مقابلة عندما تكون $m < 0$ معطاة بواسطة $\sum _{n=0}^{\infty }g_{n+m}z^{n}={\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}\,.$

مراجع

↑ يمكن العثور على هذا المصطلح البديل بالفعل في EN Gilbert (1956)، "Enumeration of Labeled graphs"، Canadian Journal of Mathematics 3، ص 405-411 ، ولكن استخدامه نادر قبل عام 2000؛ ومنذ ذلك الحين يبدو أنه في ازدياد.
↑ كنوت، دونالد إي. (1997). "§1.2.9 الدوال المولدة". الخوارزميات الأساسية . فن برمجة الحاسوب . المجلد 1 ( الطبعة الثالثة). أديسون-ويسلي. ISBN 0-201-89683-4.
↑ فلاجويه وسيدجويك 2009 ، ص 95
↑ "متطابقة متسلسلة لامبرت" . موقع Math Overflow . 2017.
↑ أبوستول، توم م. (1976)، مقدمة في نظرية الأعداد التحليلية ، نصوص جامعية في الرياضيات، نيويورك-هايدلبرغ: سبرينغر-فيرلاغ، ISBN 978-0-387-90163-3، MR 0434929 ، Zbl 0335.10001 الصفحات 42-43
↑ ويلف 1994 ، ص 56 خطأ في harvnb: أهداف متعددة (2×): CITEREFWilf1994 ( مساعدة )
↑ ويلف 1994 ، ص 59 خطأ في harvnb: أهداف متعددة (2×): CITEREFWilf1994 ( مساعدة )
↑ هاردي، جي إتش ؛ رايت، إي إم ؛ هيث-براون، دي آر؛ سيلفرمان ، جيه إتش (2008). مقدمة في نظرية الأعداد ( الطبعة السادسة). مطبعة جامعة أكسفورد. ص 339. ISBN 9780199219858.
↑ كنوت، دي إي (1992). "متعددات الحدود الالتفافية". مجلة ماتيماتيكا 2 : 67-78 . arXiv : math /9207221 . Bibcode : 1992math......7221K .
↑ سبيفي، مايكل ز. (2007). "المجاميع التوافقية والفروق المحدودة" . الرياضيات المتقطعة . 307 (24): 3130-3146 . doi : 10.1016/j.disc.2007.03.052 . MR 2370116 .
↑ ماثار، آر جيه (2012). "جدول آخر للتكاملات". arXiv : 1207.5845 [ math.CA ].v4 eq. (0.4)
↑ Graham, Knuth & Patashnik 1994 ، الجدول 265 في §6.1 لهويات المجموع المحدود التي تتضمن مثلثات أعداد ستيرلينغ.
↑ لاندو 2003 ، §2.4
↑ مثال من ستانلي، ريتشارد ب.؛ فومين، سيرجي (1997). "الفقرة 6.3". التوافقية العددية: المجلد 2. دراسات كامبريدج في الرياضيات المتقدمة. المجلد 62. مطبعة جامعة كامبريدج. ISBN 978-0-521-78987-5.
↑ كنوت 1997 ، §1.2.9
↑ حل كتاب غراهام، كنوت وباتاشنيك 1994 ، صفحة 569، التمرين 7.36
↑ فلاجويه وسيدجويك 2009 ، §ب.4
↑ شنايدر، سي. (2007). "الجمع الرمزي يساعد في التوافقية" . سيم. لوثار. التوافقية . 56 : 1-36 .
↑ انظر استخدام هذه المصطلحات في Graham, Knuth & Patashnik 1994 ، §7.4 حول الدوال المولدة للتسلسلات الخاصة.
↑ جود، آي جيه (1986). "حول تطبيقات توزيعات ديريشليه المتناظرة ومزيجاتها على جداول التوافق" . حوليات الإحصاء . 4 (6): 1159-1189 . doi : 10.1214/aos/1176343649 .
↑
لمزيد من المعلومات الكاملة حول خصائص الكسور J ، انظر:
- فلاجو، ب. (1980). "الجوانب التوافقية للكسور المستمرة" (ملف PDF) . الرياضيات المتقطعة . 32 (2): 125-161 . doi : 10.1016/0012-365X(80)90050-3 .
- وال، إتش إس (2018) [1948]. النظرية التحليلية للكسور المستمرة . دوفر. ISBN 978-0-486-83044-5.
↑
انظر المقالات التالية:
- شميدت، ماكسي د. (2016). "الكسور المستمرة لدوال توليد المتسلسلات المربعة". arXiv : 1612.02778 [ math.NT ].
- — (2017). "الكسور المستمرة من نوع جاكوبي للدوال المولدة العادية للدوال العاملية المعممة" . مجلة متواليات الأعداد الصحيحة . 20. arXiv : 1610.09691 . 17.3.4.
- — (2017). "الكسور المستمرة من نوع جاكوبي والتطابقات لمعاملات ذات الحدين بتردد الأعداد الصحيحة h ≥ 2". arXiv : 1702.01374 [ math.CO ].
↑ ويلف، هربرت (1994). علم وظائف التوليد ( الطبعة الثانية). دار النشر الأكاديمية، ص 45.
^ جراهام ونوث وباتاشنيك 1994 ، §8.3
↑ انظر غراهام، كنوت ، وباتاشنيك 1994 ، المثال 6 في القسم 7.3 للاطلاع على طريقة أخرى والإعداد الكامل لهذه المسألة باستخدام الدوال المولدة. هذا النهج الأكثر تعقيدًا مُفصّل في القسم 7.5 من المرجع نفسه.
↑ لاندو 2003 ، §5
↑ هاردي وآخرون 2008 ، §19.12
↑ هاردي، جي إتش؛ رايت، إي إم مقدمة في نظرية الأعداد .ص 288، ث 361
↑ غراهام، كنوت وباتاشنيك 1994 ، ص 535، التمرين 5.71
^ انظر أيضًا 1031 وظيفة توليد موجودة في سيمون بلوف (1992). Approximations de séries génératrices et quelques conjectures [ تقريبات توليد الوظائف وبعض التخمينات ] (الماجستير) (بالفرنسية). جامعة كيبيك في مونتريال. أرخايف : 0911.4975 .

الاقتباسات

أيغنر، مارتن (2007). دورة في التعداد . نصوص الدراسات العليا في الرياضيات. المجلد 238. سبرينغر. ISBN 978-3-540-39035-0.
دوبيليه، بيتر؛ روتا، جيان كارلو ؛ ستانلي، ريتشارد (1972). "حول أسس نظرية التوافيق. السادس. فكرة الدالة المولدة" . وقائع ندوة بيركلي السادسة حول الإحصاء الرياضي والاحتمالات . 2 : 267-318 . Zbl 0267.05002 . أُعيد طبعه في: روتا، جيان كارلو (1975). "3. فكرة الدالة المولدة". حساب التفاضل والتكامل للمؤثرات المحدودة . بالتعاون مع: ب. دوبيليه، س. غرين، د. كاهانر، أ. أودليزكو ، و ر. ستانلي . دار النشر الأكاديمية. الصفحات 83-134 . ISBN 0-12-596650-4. Zbl 0328.05007 .
فلاجويه، فيليب ؛ سيدجويك، روبرت (2009). التوافقية التحليلية . مطبعة جامعة كامبريدج. ISBN 978-0-521-89806-5. Zbl 1165.05001 .
غولدين، إيان ب.؛ جاكسون، ديفيد م. (2004). التعداد التوافقي . منشورات دوفر . ISBN 978-0486435978.
غراهام، رونالد ل .؛ كنوت، دونالد إي .؛ باتاشنيك، أورين (1994). "الفصل 7: الدوال المولدة". الرياضيات الملموسة. أساس لعلوم الحاسوب ( الطبعة الثانية). أديسون-ويسلي. ص 320-380 . ISBN 0-201-55802-5. Zbl 0836.00001 .
لاندو، سيرجي ك. (2003). محاضرات في الدوال المولدة . الجمعية الأمريكية للرياضيات. ISBN 978-0-8218-3481-7.
ويلف، هربرت س. (1994). علم وظائف التوليد ( الطبعة الثانية). دار النشر الأكاديمية. رقم ISBN 0-12-751956-4. Zbl 0831.05001 .

روابط خارجية

"مقدمة في الدوال المولدة العادية" بقلم مايك زابروكي، جامعة يورك، قسم الرياضيات والإحصاء
"الدالة المولدة" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
الدوال المولدة، ومؤشرات القوة، وباقي العملات المعدنية في حفل قص العقدة
"الوظائف المولدة" بقلم إد بيج جونيور ، مشروع عروض وولفرام ، 2007.

[23] بالمناسبة، لدينا أيضًا صيغة مقابلة عندما تكون $m < 0$ معطاة بواسطة $\sum _{n=0}^{\infty }g_{n+m}z^{n}={\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}\,.$

[1] يمكن العثور على هذا المصطلح البديل بالفعل في EN Gilbert (1956)، "Enumeration of Labeled graphs"، Canadian Journal of Mathematics 3، ص 405-411 ، ولكن استخدامه نادر قبل عام 2000؛ ومنذ ذلك الحين يبدو أنه في ازدياد.

[2] كنوت، دونالد إي. (1997). "§1.2.9 الدوال المولدة". الخوارزميات الأساسية . فن برمجة الحاسوب . المجلد 1 ( الطبعة الثالثة). أديسون-ويسلي. ISBN 0-201-89683-4.

[3] فلاجويه وسيدجويك 2009 ، ص 95

[4] "متطابقة متسلسلة لامبرت" . موقع Math Overflow . 2017.

[5] أبوستول، توم م. (1976)، مقدمة في نظرية الأعداد التحليلية ، نصوص جامعية في الرياضيات، نيويورك-هايدلبرغ: سبرينغر-فيرلاغ، ISBN 978-0-387-90163-3، MR 0434929 ، Zbl 0335.10001 الصفحات 42-43

[W56-6] ويلف 1994 ، ص 56 خطأ في harvnb: أهداف متعددة (2×): CITEREFWilf1994 ( مساعدة )

[W59-7] ويلف 1994 ، ص 59 خطأ في harvnb: أهداف متعددة (2×): CITEREFWilf1994 ( مساعدة )

[8] هاردي، جي إتش ؛ رايت، إي إم ؛ هيث-براون، دي آر؛ سيلفرمان ، جيه إتش (2008). مقدمة في نظرية الأعداد ( الطبعة السادسة). مطبعة جامعة أكسفورد. ص 339. ISBN 9780199219858.

[9] كنوت، دي إي (1992). "متعددات الحدود الالتفافية". مجلة ماتيماتيكا 2 : 67-78 . arXiv : math /9207221 . Bibcode : 1992math......7221K .

[10] سبيفي، مايكل ز. (2007). "المجاميع التوافقية والفروق المحدودة" . الرياضيات المتقطعة . 307 (24): 3130-3146 . doi : 10.1016/j.disc.2007.03.052 . MR 2370116 .

[11] ماثار، آر جيه (2012). "جدول آخر للتكاملات". arXiv : 1207.5845 [ math.CA ].v4 eq. (0.4)

[12] Graham, Knuth & Patashnik 1994 ، الجدول 265 في §6.1 لهويات المجموع المحدود التي تتضمن مثلثات أعداد ستيرلينغ.

[GFLECT-13] لاندو 2003 ، §2.4

[14] مثال من ستانلي، ريتشارد ب.؛ فومين، سيرجي (1997). "الفقرة 6.3". التوافقية العددية: المجلد 2. دراسات كامبريدج في الرياضيات المتقدمة. المجلد 62. مطبعة جامعة كامبريدج. ISBN 978-0-521-78987-5.

[TAOCPV1-15] كنوت 1997 ، §1.2.9

[16] حل كتاب غراهام، كنوت وباتاشنيك 1994 ، صفحة 569، التمرين 7.36

[17] فلاجويه وسيدجويك 2009 ، §ب.4

[18] شنايدر، سي. (2007). "الجمع الرمزي يساعد في التوافقية" . سيم. لوثار. التوافقية . 56 : 1-36 .

[19] انظر استخدام هذه المصطلحات في Graham, Knuth & Patashnik 1994 ، §7.4 حول الدوال المولدة للتسلسلات الخاصة.

[Good_1986-20] جود، آي جيه (1986). "حول تطبيقات توزيعات ديريشليه المتناظرة ومزيجاتها على جداول التوافق" . حوليات الإحصاء . 4 (6): 1159-1189 . doi : 10.1214/aos/1176343649 .

[21] لمزيد من المعلومات الكاملة حول خصائص $الكسور J$ ، انظر:
فلاجو، ب. (1980). "الجوانب التوافقية للكسور المستمرة" (ملف PDF) . الرياضيات المتقطعة . 32 (2): 125-161 . doi : 10.1016/0012-365X(80)90050-3 .
وال، إتش إس (2018) [1948]. النظرية التحليلية للكسور المستمرة . دوفر. ISBN 978-0-486-83044-5.

[mwBls] فلاجو، ب. (1980). "الجوانب التوافقية للكسور المستمرة" (ملف PDF) . الرياضيات المتقطعة . 32 (2): 125-161 . doi : 10.1016/0012-365X(80)90050-3 .

[mwBmU] وال، إتش إس (2018) [1948]. النظرية التحليلية للكسور المستمرة . دوفر. ISBN 978-0-486-83044-5.

[22] انظر المقالات التالية:
شميدت، ماكسي د. (2016). "الكسور المستمرة لدوال توليد المتسلسلات المربعة". arXiv : 1612.02778 [ math.NT ].
— (2017). "الكسور المستمرة من نوع جاكوبي للدوال المولدة العادية للدوال العاملية المعممة" . مجلة متواليات الأعداد الصحيحة . 20. arXiv : 1610.09691 . 17.3.4.
— (2017). "الكسور المستمرة من نوع جاكوبي والتطابقات لمعاملات ذات الحدين بتردد الأعداد الصحيحة h ≥ 2". arXiv : 1702.01374 [ math.CO ].

[mwBnI] شميدت، ماكسي د. (2016). "الكسور المستمرة لدوال توليد المتسلسلات المربعة". arXiv : 1612.02778 [ math.NT ].

[mwBnk] — (2017). "الكسور المستمرة من نوع جاكوبي للدوال المولدة العادية للدوال العاملية المعممة" . مجلة متواليات الأعداد الصحيحة . 20. arXiv : 1610.09691 . 17.3.4.

[mwBoM] — (2017). "الكسور المستمرة من نوع جاكوبي والتطابقات لمعاملات ذات الحدين بتردد الأعداد الصحيحة h ≥ 2". arXiv : 1702.01374 [ math.CO ].

[24] ويلف، هربرت (1994). علم وظائف التوليد ( الطبعة الثانية). دار النشر الأكاديمية، ص 45.

[25] جراهام ونوث وباتاشنيك 1994 ، §8.3

[26] انظر غراهام، كنوت ، وباتاشنيك 1994 ، المثال 6 في القسم 7.3 للاطلاع على طريقة أخرى والإعداد الكامل لهذه المسألة باستخدام الدوال المولدة. هذا النهج الأكثر تعقيدًا مُفصّل في القسم 7.5 من المرجع نفسه.

[27] لاندو 2003 ، §5

[28] هاردي وآخرون 2008 ، §19.12

[29] هاردي، جي إتش؛ رايت، إي إم مقدمة في نظرية الأعداد .ص 288، ث 361

[30] غراهام، كنوت وباتاشنيك 1994 ، ص 535، التمرين 5.71

[31] انظر أيضًا 1031 وظيفة توليد موجودة في سيمون بلوف (1992). Approximations de séries génératrices et quelques conjectures [ تقريبات توليد الوظائف وبعض التخمينات ] (الماجستير) (بالفرنسية). جامعة كيبيك في مونتريال. أرخايف : 0911.4975 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

9 ] فئة

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ].

[ 14 ]

[

[ 16 ].

[ 17 ].

[ 18 ]

[ 19 ]

tᵣ

[

[ 22 ]

[ ملاحظة 1 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗

تاريخ

تعريف

التقارب

القيود

الأنواع

دالة التوليد العادية (OGF)

دالة التوليد الأسي (EGF)

دالة توليد بواسون

سلسلة لامبرت

سلسلة بيل

دوال توليد متسلسلة ديريشليه (DGFs)

دوال توليد المتتابعات متعددة الحدود

وظائف توليد أخرى

كثيرات الحدود الالتفافية

الدوال المولدة العادية

أمثلة على المتتابعات البسيطة

الدوال الكسرية

العمليات على الدوال المولدة

ينتج عن الضرب عملية الالتفاف

مؤشرات تسلسل الإزاحة

التفاضل والتكامل للدوال المولدة

تعداد المتتابعات الحسابية

المتتابعات المتكررة من النوع P ووظائف التوليد الهولونومية

التعريفات

أمثلة

برنامج للعمل مع المتتاليات المتكررة من النوع P ووظائف التوليد الهولونومية

العلاقة بتحويل فورييه المنفصل زمنيًا

النمو التقاربي للمتتالية

النمو التقاربي لمتتالية المربعات

النمو التقاربي لأعداد كاتالان

الدوال المولدة ثنائية المتغيرات ومتعددة المتغيرات

حالة ثنائية المتغيرات

حالة متعددة المتغيرات

التمثيل بواسطة الكسور المستمرة (كسور جاكوبي من النوع J )

التعريفات

خصائص الدوال المتقاربة من الرتبة h

أمثلة

أمثلة

الأرقام المربعة

التطبيقات

تقنيات متنوعة: تقييم المجاميع ومعالجة المشكلات الأخرى باستخدام الدوال المولدة

مثال 1: صيغة مجموع الأعداد التوافقية

مثال 2: مجموع معاملات ذات الحدين المعدلة وتحويل ذات الحدين

مثال 3: الدوال المولدة للمتتاليات المتكررة المتبادلة

الالتفاف (منتجات كوشي)

مثال: مشكلة صرف العملات

مثال: دالة توليد الأرقام الكاتالونية

مثال: الأشجار الممتدة للمراوح والالتفافات للالتفافات

الدوال المولدة الضمنية وصيغة لاغرانج العكسية

إدخال مُعامل حر (طريقة الوهم)

تُثبت الدوال المولدة التطابقات

أعداد ستيرلينغ بتردد الأعداد الصحيحة الصغيرة

تطابقات دالة التقسيم

تحويلات الدوال المولدة

جداول الدوال المولدة الخاصة

انظر أيضاً

ملحوظات

مراجع

الاقتباسات

روابط خارجية

$المتتابعات المتكررة من النوع P$ ووظائف التوليد الهولونومية

برنامج للعمل مع المتتاليات المتكررة من النوع $P$ ووظائف التوليد الهولونومية

التمثيل بواسطة الكسور المستمرة (كسور جاكوبي من النوع $J$ )

خصائص الدوال المتقاربة من الرتبة $h$