تابع مولد – از صفر تا صد

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

یک «تابع مولد معمولی» (Ordinary Generating Function) به فرم $$f ( x ) = \displaystyle \sum _ { n = 0 } ^ { \infty } a _ n x ^ n$$ نوشته می‌شود که در حل مسائل مختلف کاربرد دارد.

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

به چند روش می‌توان اعدادی را نوشت که مجموع آن‌ها برابر با ۱۰ باشد، به طوری که دقیقاً یکی از عناصر دو مجموعه $$\{ 2 , 3 , 6 , 7 \}$$ و $$\{ 3 , 4 , 5 , 8 \}$$ را داشته باشد؟

حل: دو چندجمله‌ای $$x ^ 2 + x ^ 3 + x ^ 6 + x ^ 7$$ و $$x ^ 3 + x ^ 4 + x ^ 5 + x ^ 8$$ را در نظر بگیرید. در چندجمله‌ای نخست، ضریب $$x ^ n$$ عددی است که با استفاده از یک عنصر از مجموعه اول جمع $$n$$ را می‌سازد. همین گفته برای چندجمله‌ای دوم نیز برقرار است. برای مثال، ضریب $$x ^ 4$$ در چندجمله‌ای دوم برابر با ۱ است و یک راه برای تشکیل مجموع ۴ با استفاده از فقط یک عنصر از مجموعه دوم وجود دارد.

$$\large \big ( x ^ 2 + x ^ 3 + x ^ 6 + x ^ 7 \big ) \big ( x ^ 3 + x ^ 4 + x ^ 5 + x ^ 8 \big ) .$$

می‌خواهیم بدانیم که ضریب $$x ^ n$$ در ضرب چندجمله‌ای‌ها چه مفهومی دارد. این ضریب تعداد راه‌هایی را نشان می‌دهد که می‌توان مجموع $$n$$ را با استفاده از دقیقاً‌ یک عنصر از هر مجموعه تشکیل داد. حاصل‌ضرب به صورت زیر است:

$$\large \begin {aligned} & \big ( x ^ 2 + x ^ 3 + x ^ 6 + x ^ 7 \big ) \big ( x ^ 3 + x ^ 4 + x ^ 5 + x ^ 8 \big ) \\ & = x ^ 5 + 2 x ^ 6 + 2 x ^ 7 + x ^ 8 + x ^ 9 + 3 x ^ { 1 0 } + 3 x ^ { 1 1 } + x ^ { 1 2 } + x ^ { 1 4 } + x ^ { 1 5 } . \end {aligned}$$

لازم به ذکر است که ضریب $$x ^ n$$ برای $$n >15$$ برابر با $$0$$ است، زیرا نمی‌توانیم مجموعی را بزرگ‌تر از $$15$$ با استفاده از یکی از مجموعه‌ها بسازیم. همین گفته برای $$n < 5$$ نیز صادق است.

وقتی $$n = 10$$ باشد، ضریب $$3$$ است. این بدین معنی است که ۳ راه برای ساختن $$10$$ وجود دارد. اگر ضرب را به طور کامل با فرمول توزیعی گسترش دهیم، خواهیم دید که سه تا $$x ^{ 10}$$ از ضرب $$x ^2$$ در $$x^8$$، ضرب $$x ^ 6$$ در $$x ^ 4$$ و ضرب $$x ^ 7$$ در $$x ^ 3$$ وجود دارد.

ایده معنی دادن به ضریب $$x ^ n$$ بدون معنی دادن به $$x$$ در حقیقت ایده تابع مولد است. یک تابع مولد تعداد اشیا را با استفاده از سری‌های توانی رسمی که چند‌جمله‌ای با احتمالاً بی‌نهایت جمله (توان‌های صحیح) است، رمزگذاری می‌کند. توجه کنید که اصطلاح رسمی به این دلیل استفاده می‌شود که یک مفهوم جبری است، نه یک مفهوم تحلیلی.

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

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

برای ۲ تاس، می‌توانیم به همین ترتیب مقادیر احتمالی را فهرست کرده و بنویسیم:

$$\large R _ 2 ( x ) = x ^ 2 + 2 x ^ 3 + 3 x ^ 4 + 4 x ^ 5 + 5 x ^ 6 + 6 x ^ 7 + 5 x ^ 8 + 4 x ^ 9 + 3 x ^ { 1 0 } + 2 x ^ { 1 1 } + x ^ { 1 2 } .$$

یک راه سرراست‌تر، استفاده از $$R _ 2 ( x ) = [ R _ 1 ( x ) ] ^ 2$$ است، بنابراین، می‌توانیم بدون شمارش هر جمله، آن را محاسبه کنیم.

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

چه تعداد جواب صحیح نامنفی در معادله $$a + b + c = 20$$ صدق می‌کند؟

حل: ابتدا مسئله عمومی‌تر یافتن تعداد جواب‌های صحیح نامنفی معادله $$a + b + c = n$$ را در نظر می‌گیریم. از آنجا که مقدار $$a$$ می‌تواند هر عدد صحیح نامنفی $$0$$، $$1$$، $$2$$، $$\cdots$$، $$i$$ و ... باشد، می‌توانیم آن را با یک تابع مولد نشان دهیم:

$$\large A ( x ) = 1 + x + x ^ 2 + \cdots + x ^ i + \cdots .$$

تابع مولد مشابهی برای مقادیر ممکن $$b$$ و $$c$$ داریم. بنابراین، تابع مولد برای تعداد جواب‌ها $$A ( x ) \times B ( x ) \times C ( x ) = [ A ( x ) ] ^ 3$$ است. با این حال، یافتن این ضرب می‌تواند بسیار خسته‌کننده باشد.

$$\large \frac { 1 } { ( 1 - x ) ^ 3 } = { 2 \choose 2 } + { 3 \choose 2 } x + { 4 \choose 2 } x ^ 2 + \cdots + { i + 2 \choose 2 } x ^ i + \cdots .$$

بنابراین، وقتی $$n = 20$$ باشد، عبارت $${ 2 2 \choose 2 }$$ را خواهیم داشت.

حل رابطه بازگشتی همگن

در حالت کلی، یک رابطه بازگشتی برای اعداد $$\{ c _ i \} _ { i = 1 } ^ { \infty }$$ راهی برای بیان $$c _ n$$ برحسب $$k$$ جمله قبلی دنباله، به ازای تعدادی عدد صحیح مثبت $$k$$ است. یک رابطه بازگشتی خطی همگن رابطه‌ای به فرم $$c _ n + q _ 1 c _ { n - 1 } + q _ 2 c _ { n - 2 } + \cdots +q_ k c _ { n - k } = 0$$ است. این رابطه خطی است، زیرا هر جمله آن فقط یک تک‌جمله‌ای به فرم $$c _ i$$ است و همگن است، زیرا سمت راست آن برابر با ۰ است.

فیلم آموزش حل روابط بازگشتی و مفاهیم کلیدی در فرادرس

کلیک کنید

اگر سمت راست این رابطه تابعی غیرصفر از $$n$$ باشد، آنگاه معادله ناهمگن نامیده می‌شود. برای حل کامل یک رابطه بازگشتی، به مقادیر اولیه $$k$$ جمله ابتدایی نیاز داریم.

مثال رابطه بازگشتی همگن

مقدار صریح $$c _ n$$ را بیابید، در صورتی که داشته باشیم: