ترکیب با تکرار و کاربرد آن در محاسبه تعداد جوابهای صحیح نامنفی معادلات
ترکیب با تکرار و کاربرد آن در محاسبه تعداد جوابهای صحیح نامنفی معادلات و ضرایب چند جمله ایها –بخش 1
فرمول ترکیب
[math]\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right)[/math]
تا اینجا دانستیم که در فرمول ترکیب بالا همیشه مقدار r کوچکتر از n بود . اما در این مطلب میخواهیم حالتهایی را بررسی کنیم که [math]r>n[/math] باشد در واقع می توان گفت اینجا با ترکیب با تکرار مواجه هستیم.
مثال 1: فرض کنید قراره 8 نفر از دوستانتان را به یک فست فود دعوت کنید و منوی فست فود شما شامل غذاهای زیر است :
{پیتزا ، جوجه سوخاری ،همبرگر}
سوال اینجاست به چند طریق این 8 نفر می توانند این غذاها را انتخاب کنند به شرطی که هر کدام فقط یک نوع غذا را سفارش دهد ؟
همانطور که می بینید اینجا با مساله ترکیبات با تکرار مواجه هستیم و همچنین اینجا [math]r>n[/math] می باشد . پس باید با روشی متفاوت آن را حل کنیم .
ما شکلی بصورت زیر ایجا می کنیم تا حالتهای مختلف انتخاب غذا را ثبت کنیم .
هر بار که یکیاز مهمانان غذایی را سفارش دهد ما یک علامت ستاره در یکی از قسمتهای بالا قرار می دهیم مثلا اولین نفر همبرگر سفارش داده است :
دومین نفر پیتزا سفارش داده است :
به همین طریق اگر هر هشت نفر غذا سفارش دهند حالتهای مختلفی خواهیم داشت یکی از حالتها مثلا بصورت زیر است :
حالت فوق یعنی مهمانان ما 4 تا همبرگر و سه تا سوخاری و 1 پیتزا سفارش داده اند . یا حالتی دیگر که مثلا مهمانان ممکنه 4 تا همبرگر و 4 تا سوخاری سفارش بدن و هیچ کس پیتزا نخواد مانند شکل زیر:
یا حالتی ممکنه همگی همبرگر سفارش بدن 8 تا همبرگر و سفارش سوخاری و پیتزا اصلا نداشته باشیم مانند شکل زیر :
اگر دقت کنید ما در تمام شکلهای بالا با احتساب خطوط در واقع ما داریم ده تا شی را مرتب جابجا می کنیم که 8 تای آنها ستاره و دوتای آنها خط هستند ، و مشاهده کردیم که هر کجا که این خطوط( دوتا خط) قرار بگیرند حالتی متفاوتی را تشکیل می دهند .
طبق فیلم بالا می بینیم آنچه اینجا مهم است جایگاه خطوط هست منظور همین دوتا خط هست و این دوتا خط در واقع در 10 جایگاه می توانند قرار بگیرند پس اینجا ما یک ترکیب 2 تایی از میان 10 شی را خواهیم داشت و در نتیجه تعداد حالتهای مساله ما :
[math]\left( {\begin{array}{*{20}{c}}{10}\\2\end{array}} \right) = 45[/math]
قضیه :اگر بخواهیم از میان اعضای مجموعه S که دارای n عضو است r شیء را طوری انتخاب کنیم که از هر عضو مجموعه S چندبار بخواهیم استفاده کنیم و از طرف دیگر ترتیب قرار گرفتن این اشیا در کنار هم مهم نباشد در این صورت تعداد این انتخابها بصورت زیر است :
[math]\left( {\begin{array}{*{20}{c}}{n + r – 1}\\{n – 1}\end{array}} \right)[/math]
مثال :به چند طریق می توان 40 سکه را بین 3 نفر تقسیم کرد ؟سکه ها مثل هم هستند
این مثال مثل حالت بالا است که ما اینجا 40+2 جای خالی داریم که با 2 خط عمودی و 40 ستاره باید پر شوند پس جواب :
[math]\left( {\begin{array}{*{20}{c}}{40 + 3 – 1}\\{3 – 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{42}\\2\end{array}} \right)[/math]
نکته مهم : تساوی زیر همیشه برقرار است .
[math]\left( {\begin{array}{*{20}{c}}{n + r – 1}\\r\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{n + r – 1}\\{n – 1}\end{array}} \right)[/math]
مثال 2: یک نفر 7 سیب دارد و می خواهد اینها را بین 4 نفر تقسیم کند بطوری که ممکن است بعضیها اصلا هیچ سیبی نگیرند.به چند روش می تواند این کار را انجام دهد .
برای پاسخ میتوان از همین فرمول بالا براحتی استفاده کرد که n=4 , r=7 است پس :
[math]\left( {\begin{array}{*{20}{c}}{n + k – 1}\\{n – 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{4 + 7 – 1}\\{4 – 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{10}\\3\end{array}} \right) = \frac{{10!}}{{3!7!}} = \frac{{10 \times 9 \times 8}}{6} = 120\\[/math]
اما من الان میخواهم این مساله را با دید معادله حل کنم و در واقع روشی دیگر در نظر بگیرم .یک معادله با چهار متغیر بصورت زیر ایجاد می کنیم :
تعداد سیب های نفر اول | [math] {x_1} [/math] |
تعداد سیب های نفر دوم | [math] {x_2} [/math] |
تعداد سیب های نفر سوم | [math] {x_3} [/math] |
تعداد سیب های نفر سوم | [math] {x_4} [/math] |
از طرف دیگر می دانیم تعداد کل سیب ها برابر 7 تا است پس جواب مساله ما برابر است با تعداد جواب های صحیح نامنفی معادله زیر است :
[math] {x_1} + {x_2} + {x_3} + {x_4} = 7[/math]
چندتا از حالتهای مختلف جواب این معادله را بصورت جدول زیر بررسی می کنیم :
حالت | [math] {x_4} [/math] | [math] {x_3} [/math] | [math] {x_2} [/math] | [math] {x_1} [/math] |
xx|xx|xx|x | 1 | 2 | 2 | 2 |
xxxx|x|x|x | 1 | 1 | 1 | 4 |
xxxxxx|||x | 1 | 0 | 0 | 6 |
|x|xx|xxxx | 4 | 2 | 1 | 0 |
||xxxxx|xx | 2 | 5 | 0 | 0 |
اگر سیب را با x نشان دهیم و تعداد x های قبل از خط اول را با [math] {x_1} [/math] و تعداد x های بین خط اول و دوم را [math] {x_2} [/math] و تعداد x های بین خط دوم و سوم را با
[math] {x_3} [/math] و تعداد x های بعد از خط سوم را با [math] {x_4} [/math] نشان دهیم .یک تناظر یک به یک بین جوابهای معادله [math] {x_1} + {x_2} + {x_3} + {x_4} = 7[/math]
و تعداد توزیع هایی که با 7 علامت x و 3 علامت خط می توان ساخت بر قرار می شود. به عنوان مثال سطر اول از جدول فوق xx|xx|xx|x نشان دهنده جواب :
[math] {x_1} = 2,{x_2} = 2,{x_3} = 2,{x_4} = 1[/math]
پس در واقع تعداد جوابهای صحیح نا منفی معادله فوق برابر است با :
[math]\left( {\begin{array}{*{20}{c}}{10}\\3\end{array}} \right)[/math]
قضیه : تعداد جوابهای صحیح نامنفی معادله
[math] {x_1} + {x_2} + {x_3} + {x_4} + … + {x_n} = r[/math]
برابر است با :
[math]\left( {\begin{array}{*{20}{c}}{n + r – 1}\\{n – 1}\end{array}} \right)[/math]
مثال :تعداد جوابهای معادله
[math] {x_1} + {x_2} + {x_3} + {x_4} = 9[/math]
برابر است با :
[math]\left\{ \begin{array}{l}n = 4\\r = 9\end{array} \right\} \to \left( {\begin{array}{*{20}{c}}{n + r – 1}\\{n – 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{4 + 9 – 1}\\{4 – 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{12}\\3\end{array}} \right)[/math]
در بخش دوم مقاله در مورد ضرایب چند جمله ایها و ارتباط آن با ترکیب توضیح خواهیم داد.