چنانچه محفل ریاضی را سودمند یافتید، لطفا برای حمایت از ما به کانال تلگرامی محفل ریاضی بپیوندید!
به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+2 امتیاز
843 بازدید
سوال شده در دانشگاه توسط iman_aa

تعداد جواب های صحیح نامنفی معادله $ x_{1}+ x_{2}+...+ x_{r}=n $ برابر با $ \binom{n+r-1}{r-1} $ است. با استفاده از تابع مولد این مسئله را بیان کنید.

1 پاسخ

+1 امتیاز
پاسخ داده شده توسط amirabbas
انتخاب شده توسط iman_aa
 
بهترین پاسخ

نگاهی به روند ضرب چند جمله ای ها می تواند به ما ایده ای برای حل این مسئله بدهد.

به روند ضرب سه عبارت زیر دقت کنید.

$$ (x^0 + x^1 + x^2)(x^0+x^1+x^2)(x^0 + x^1 + x^2) $$

برای بدست آوردن حاصل این ضرب به نوبت از پرانتز اول یک جمله و از پرانتز دوم یک جمله دیگر و از پرانتز سوم هم یک جمله انتخاب می کنیم در یکدیگر ضرب می کنیم. برای مثال فرض کنید می خواهیم ضریب $x^3$ را در حاصلضرب این سه عبارت محاسبه کنیم.با انتخاب جمله ها از پرانتز ها به صورت های زیر می توان به $x^3$ رسید.

  • پرانتز اول $x^0$ - پرانتز دوم $x^1$ - پرانتز سوم $x^2$
  • پرانتز اول $x^0$ - پرانتز دوم $x^2$ - پرانتز سوم $x^1$
  • پرانتز اول $x^1$ - پرانتز دوم $x^0$ - پرانتز سوم $x^3$
  • پرانتز اول $x^1$ - پرانتز دوم $x^1$ - پرانتز سوم $x^1$
  • پرانتز اول $x^1$ - پرانتز دوم $x^2$ - پرانتز سوم $x^0$
  • پرانتز اول $x^2$ - پرانتز دوم $x^0$ - پرانتز سوم $x^1$
  • پرانتز اول $x^2$ - پرانتز دوم $x^1$ - پرانتز سوم $x^0$

با توجه به این که به 7 طریق می توان به $x^3$ رسید پس ضریب $x^3$ در این حاصلضرب برابر 7 خواهد بود.با دقت در روند انجام این ضرب می توانیم بفهمیم که ضریب $x^3$ در عبارت بالا متناظر با تعداد جواب های صحیح و نامنفی معادله زیر است به طوریکه : $ 0 \leq x_i \leq 2$

$$ x_1 + x_2 + x_3 = 3 $$

در مثالی که گفتم به تابع $f(x) = (1 + x + x^2)^3$ تابع مولد می گویند. به عنوان مثالی دیگر فرض کنید که می خواهیم تعداد روش های توزیع 10 کتاب بین سه شخص $p_1, p_2, p_3$ را پیدا کنیم به طوریکه تعداد کتاب های p1 زوج ، تعداد کتاب های p2 مربع کامل و تعداد کتاب های p3 کمتر از پنج باشد.در این مثال تابع مولد به صورت زیر است که ضریب $x^{10}$ در آن پاسخ مطلوب ما است:

$$ g(x) = (1 + x^2 + x^4 + ... + x^{10})(1 + x + x^4 + x^9)(1 + x + ... + x^4) $$

در مثالی که خود شما مطرح کردید. تابع مولد به صورت زیر است:

$$ h(x) = (1 + x + x^2 + ...)^r $$

ضریب $x^n$ در این تابع برابر با تعداد جواب ها است.

همانطور که مشاهده کردید تابع مولد در حل مسائلی که با روش های معمول آنالیز ترکیبی نیاز به حالت گیری های بسیار دارند کمک فراوانی می کند.توابع مولدی که به شما معرفی کردم توابع مولد معمولی می گویند. دسته دیگری هم به نام توابع مولد نمایی وجود دارد که کاربرد آن ها در مسائل دیگری است.نکته ای که باید به آن دقت کنید این است که در مثال هایی که زدیم ضرب کردن عبارت ها کاری طولانی است.موضوع اصلی در بحث توابع مولد یافتن ضریب جمله موردنظر بدون انجام عمل ضرب است.این موضوع نیازمند آشنایی کافی با سری های توانی و دیگر مباحث تابع مولد است.این توابع یکی از ابزار های قدرتمند ریاضیات گسسته هستند که ما تنها بخشی از کاربرد آن ها را در مسائل شمارشی دیدیم.این توابع در زمینه های دیگری مانند حل روابط بازگشتی هم کاربردی هستند.برای یادگیری مواردی که گفتم دو منبع معرفی می کنم که منبع اول مختصر و منبع دوم جامع تر و کامل تره.

  • ریاضیات گسسته مقدماتی تالیف و.ک.بالاکریشنان، ترجمه : دکتر بیژن شمس و دکتر محمدعلی رضوانی ،انتشارات فاطمی
  • ریاضیات گسسته ترکیبیاتی رالف.پ.گریمالدی جلد دوم، ترجمه : دکتر محمدعلی رضوانی و دکتر بیژن شمس ،انتشارات فاطمی
لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
85 نفر آنلاین
0 عضو و 85 مهمان در سایت حاضرند
بازدید امروز: 3590
بازدید دیروز: 7287
بازدید کل: 4705916
...