ترکیب
ترکیب
مطلب را با مثالی آغاز می کنیم .فرض کنید پنج عدد {1,2,3,4,5} داده شده باشند و از ما دو سوال زیر را می پرسند که باید حالتهای آنها را حساب کنیم
الف)چند عدد سه رقمی می توان با این پنج رقم ساخت؟
ب)چند زیر مجموعه سه عضوی می توان با این پنج رقم ساخت ؟
ابتدا گزینه الف را بررسی می کنیم . همانطور که می دانیم ترتیب قرار گرفتن اعداد بسیار مهم است یعنی مثلا عدد 123 و عدد 231 دو عدد متفاوت هستند ، درسته که ارقام آنها یکی است یعنی در هر دوتا رقمهای 1و2و3 بکار برده شده اما این دو عدد متفاوت هستند پس با توجه به مساله که ترتیب اعداد برامون مهم است و از طرف دیگر ما اینجا با جابجایی سر و کار داریم پس اینجا ما با جایگشت طرف هستیم . یعنی باید جایگشت سه تایی از این 5 رقم می خواهیم ایجاد کنیم .
[math]P(5,3) = \frac{{5!}}{{(5 – 3)!}} = 60[/math]
اینجا ما جایشگت سه تایی از 5 رقم داریم که حساب کردیم 60 عدد می توان ساخت. در جدول زیر تمام این 60 عدد را نمایش داده ایم .
در جدول بالا رقم های موجود در هر ستون یکسان هستند ،اما جایگشتهای مختلف باعث بوجود آمدن اعداد سه رقمی متفاوتی می شود . مثلا ستون اول سمت چپ را ببینید همه اعداد این ستون از ارقام 1و2و3 تشکیل شده اند . اما از نظر عددی 6 عدد متفاوتی هستند .
حالا می رسیم به قسمت دوم سوال یعنی قسمت ب سوال که از ما خواسته زیر مجموعه های سه عضوی بسازیم .
یادآوری :در مجموعه ها تکرار و جابجایی مجاز است و با جابجایی اعداد مجموعه جدیدی بوجود نمی آید. اگر خواص مجموعه ها را فراموش کرده اید پیشنهاد می کنم مبحث مجموعه ها را در همین سایت مطالعه کنید.
مفهوم مقدماتی نظریه مجموعه ها |
کلیه مطالب آموزشی مبحث مجموعه ها در سایت |
اگر به جدول بالا دقت کنید گفتیم که هر ستون جدول ارقام موجود یکسان هستند در واقع هر ستون جدول یک زیر مجموعه را نشان می دهد من اینجا ارقام تشکیل دهنده عددهای هر ستون جدول بالا را به ترتیب بصورت زیر مجموعه می نویسم .
مجموعه های بالا ،تمام زیر مجموعه های سه عضوی از این پنج رقم هستند .
در بخش الف ترتیب قرار گرفتن ارقام مهم بود
اما در بخش ب ترتیب قرار گرفتن ارقام اهمیتی نداشت . هر ستون جدول بالا ارقام تشکیل دهنده اعداد در کنار هم فقط یک زیر مجموعه را نشان می دهند .خوب تا اینجا دیدیم که 10 زیر مجموعه داریم . یعنی جواب قسمت ب برابر است با 10 حالت است .
ما در قسمت الف گفتیم که 60 عدد داریم و در قسمت ب دیدیم که فقط 10 زیر مجموعه داریم یعنی از تقسیم جواب قسمت الف بر عدد 6 می توان عدد تعداد زیر مجموعه ها یعنی 10 را بدست آورد .
اما یک سوال این عدد 6 در بالا از کجا بدست آوردیم .
اگر دقت کنید ما هر سه عضو از اعضای زیر مجموعه را به [math]3!=6[/math] روش می توان در ترتیب های مختلف نوشت و اعداد متفاوتی ساخت پس در واقع 6 همان ترتیب متفاوت آنها است .
پس همانطور که در بخش الف دیدیم ترتیب قرار گرفتن هر سه عدد انتخاب شده در کنار هم اهمیت دارد ، اما در بخش ب تمام 6 روش چینش هر سه عدد انتخاب شده فقط یک زیر مجموعه را مشخص می کند ، در واقع هر زیر مجموعه 3 عضوی ، فقط یک حالت را مشخص می کند و فقط تعداد زیر مجموعه های سه عضوی از پنج عضو مهم است .
از طرفی می دانی که تعداد جایگشت های r شی از n شی متمایز برابر است با :
[math]P(n,r) = \frac{{n!}}{{(n – r)!}}[/math]
و با توجه به مطالبی که در بخش الف و ب گفتیم تعداد زیر مجموعه های r عضوی از n شی متمایز می شود :
[math]\frac{{P(n,r)}}{{r!}}=\frac{{n!}}{{r!(n – r)!}}[/math]
پس با این مقدمه می توانیم ترکیب را بصورت زیر تعریف کنیم :
ترکیب : تعداد حالات انتخاب r شی از n شی متمایز ،اگر ترتیب انتخاب آنها مهم نباشد، و فقط انتخاب r شی ملاک باشد یک ترکیب r شی از n شی می گوییم و با فرمول زیر حساب می کنیم:
[math]\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n – r)!}}[/math]
مثال 1:در یک مسابقه کشتی از بین 4 داور ایرانی ،3 داور ژاپنی ،2 داور روسی قرار است کمیته ای از داوران تشکیل شود .به چند روش می توان این کار را انجام داد اگر :
الف) کمیته 4 نفره باشد؟
ب)کمیته 3 نفره باشد و از هر یک از سه کشور یک نفر در کمیته باشد؟
پ)کمیته 5 نفره باشد و دقیقا دو داور ایرانی داشته باشد؟
ت)کمیته 5 نفره باشد و حداقل 3 داور ایرانی داشته باشد؟
ث)کمیته 7 نفره باشد و شامل 3 داور ایرانی ،2 داور ژاپنی و 2 داور روسی باشد؟
ج)حداقل یک داور ایرانی در کمیته باشد.
پاسخ:
الف) اینجا قراره فقط 4 نفر انتخاب کنیم و مهم نیست که این 4 نفر از کدام کشور باشند ، پس در واقع ما اینجا قراره از مجموع همه افراد که 9 نفر هستند ، 4 نفر را انتخاب کنیم پس در واقع شبیه به حالت زیر مجموعه ها ما تنها تعداد زیر مجموعه های 4 نفره از این 9 نفر را باید حساب کنیم . اینجا یه ترکیب 4 تا از 9 عنصر را داریم :
[math]\left( {\begin{array}{*{20}{c}}9\\4\end{array}} \right) = \frac{{9!}}{{4!(9 – 4)!}} = \frac{{9!}}{{4! \times 5!}} = 126[/math]
ب)از هر کشور باید یک نفر انتخاب کنیم انتخاب یک نفر برای ایران به
[math]\left( {\begin{array}{*{20}{c}}4\\1\end{array}} \right) = \frac{{4!}}{{1!(4 – 3)!}} = 4[/math]
به 4 روش قابل انجامه و به همین روش برای ژاپنی هم 3 روش و برای روسی هم 2 روش برای انتخاب داریم . از طرف دیگر طبق اصل ضرب اینها باید در هم ضرب شوند پس :
[math]4 \times 3 \times 2 = 24[/math]
پ) چون گفته دقیقا 2 داور ایرانی داشته باشد یعنی انتخاب (ترکیب) 2 داور ایرانی از 5 داور ایرانی موجود است :
[math]\left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right) = \frac{{4!}}{{2!(4 – 2)!}} = 6[/math]
الان 3 داور دیگر باید از بین 5 داور غیر ایرانی انتخاب شوند ، اینجا باز مهم نیست چه ملیتی داشته باشند چون در سوال ذکر نشده پس ما اینجا انتخاب 3 داور از 5 داور باقی مانده را خواهیم داشت :
[math]\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right) = \frac{{5!}}{{3!(5 – 3)!}} = 10[/math]
و سرانجام بنابه اصل ضرب تعداد روشهای انجام کار برابر است با :
[math]6 \times 10 = 60[/math]
ت)در این حالت لفظ حداقل خیلی مهمه در این قسمت ، اینجا تعداد داوران ایرانی 3 یا 4 نفر می تواند باشد . 5 نفر نمی تونه باشه چون در این حالت کل کمیته ایرانی خواهند شد . در حالیکه در سوال گفته حداقل 3 نفر پس همان منظور ما سه یا چهار نفر است .
اول فرض می کنیم کمیته 3 داور ایرانی دارد خوب تعداد انتخاب 3 داور ایرانی
[math]\left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right) = \frac{{4!}}{{3!(4 – 3)!}} = 4[/math]
در این صورت 2 داور باقی مانده باید از میان 5 داور غیر ایرانی باقی مانده انتخاب شوند که اینکار به :
[math]\left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right) = \frac{{5!}}{{2!(5 – 2)!}} = 10[/math]
قابل انجامه و سرانجام بنابراصل ضرب داریم :
[math]4 \times 10 = 40[/math]
فرض می کنیم کمیته 4 داور ایرانی دارد خوب تعداد انتخاب 3 داور ایرانی
[math]\left( {\begin{array}{*{20}{c}}4\\4\end{array}} \right) = \frac{{4!}}{{4!(4 – 4)!}} = 1[/math]
در این صورت یک داور باقی مانده باید از میان 5 داور غیر ایرانی باقی مانده انتخاب شوند که اینکار به :
[math]\left( {\begin{array}{*{20}{c}}5\\1\end{array}} \right) = \frac{{5!}}{{1!(5 – 1)!}} = 5[/math]
قابل انجامه و سرانجام بنابراصل ضرب داریم :
[math]5 \times 1 = 5[/math]
و نهایتا بنابراصل جمع ، با جمع کردن هر دو حالت ، جواب کل ما :
[math]40+5=45[/math]
ث) تعداد روش انتخاب
انتخاب 2 داور روسی |
انتخاب 2 داور ژاپنی |
تعداد روش انتخاب 3 داور ایرانی |
[math]\left( {\begin{array}{*{20}{c}}2\\2\end{array}} \right) = 1[/math]
|
[math]\left( {\begin{array}{*{20}{c}}3\\2\end{array}} \right) = 3[/math] |
[math]\left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right) = 4[/math] |
لذا طبق اصل ضرب جواب برابر است با :
[math]4 \times 3 \times 1 = 12[/math]
ج) وقتی میگه حداقل یک ایرانی باشد یعنی
1)کمیته هایی که یک ایرانی دارند و 4 نفر غیر ایرانی
2)کمیته هایی که دو ایرانی دارند و 3 نفر غیر ایرانی
3)کمیته هایی که سه ایرانی دارند و 2 نفر غیر ایرانی
4)کمیته هایی که چهارایرانی دارند و 1نفر غیر ایرانی
اجتماع و جمع تمام حالتهای بالا میشه جواب ما ، اما من چون میخواهم روش متمم را توضیح دهم ، سعی می کنم از روش متمم حل کنم .روش متمم را پایین تر توضیح داده ام.
اولش من می دانم که مجموعه ای هم هست که هیچ ایرانی ندارد و پنج عضو آن همگی غیر ایرانی هستند این مجموعه در واقع متمم تمام مجموعه های فوق است.
کمیته ای که هیج ایرانی ندارد ، خوب 5 نفر غیر ایرانی داریم . انتخاب 5 نفر از میان این 5 نفر :
[math]\left( {\begin{array}{*{20}{c}}5\\5\end{array}} \right) = 1[/math]
از طرف دیگر می دانیم که انتخاب 5 نفر از کل اعضا طبق حالت الف برابر 126 حالت بود اینجا میخواهیم مجموعه مرجع کل حالتهای انتخاب را حساب کنیم .پس جواب این گزینه برابر با :
تعداد حالات بدون هیچ ایرانی-تعداد کل حالات ایرانی و غیر ایرانی=تعداد حالات مطلوب
[math]126-1=125[/math]
حداقل ،حداکثر و روش متمم
در مساله بالا چند جا با عبارت حداکثر و حداقل مواجه شدیم ، از این عبارتها در مسائل ترکیب زیاد خواهید دید ، که با لفظ حداقل و حداکثر هستند . اکنون میخواهیم در مورد این دو عبارت بیشتر توضیح دهیم :
1)عبارتهایی که در آن گفته شود ((حداکثر k نفر )) :
این عبارت یعنی باید k نفر یا کمتر از k نفر باشند تا صفر نفر .به عبارت دیگر یعنی k نفر یا k-1 نفر یا … 2 نفر یا 1 نفر یا صفر نفر .
k,k-1, k-2,….2,1,0
2)عبارتهایی که در آن گفته ((حداقل k نفر )):
این عبارت یعنی k نفر یا بیشتر از k نفر به عبارت دیگر : k نفر یا k+1 نفر یا k+2 نفر یا ….
روش متمم :بعضی وقتها محاسبه تعداد حالات مطلوب مساله خیلی وقت گیر است می شود این مسائل را به روشی دیگر حل کرد در واقع حالات نامطلوب مساله را حل می کنیم .
تعداد حالات نامطلوب یا متمم -تعداد کل حالات=تعداد حالات مطلوب
نکته : یکی ار موارد کاربرد روش متمم در مواردی است که عبارت (( حداقل یکی )) گفته شده باشد .مثل همین حالت ج مساله قبل
مثال : به چند طریق از بین 5 زن و 4 مرد ، انجمنی 3 نفری می توان تشکیل داد که :
الف)حداقل یک نفر آن ها مرد باشد.
ب)حداکثر دو نفر از آنها زن باشد.
پاسخ :
در حالت الف چون گفته حداقل یک مرد باشد ، یعنی یا یکی از مردها انتخاب شود یا دوتا مرد و یا سه تا مرد انتخاب شوند .
حالت انتخاب یک مرد و دو زن:
[math]\left( {\begin{array}{*{20}{c}}4\\1\end{array}} \right)\left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right) = 40[/math]
حالت انتخاب دو مرد و یک زن :
[math]\left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right)\left( {\begin{array}{*{20}{c}}5\\1\end{array}} \right)=30[/math]
حالت انتخاب سه مرد و صفر زن :
[math]\left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right)\left( {\begin{array}{*{20}{c}}5\\0\end{array}} \right)=4[/math]
و سرانجام جواب کلی ما :
[math]\left( {\begin{array}{*{20}{c}}4\\1\end{array}} \right)\left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right) + \left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right)\left( {\begin{array}{*{20}{c}}5\\1\end{array}} \right) + \left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right)\left( {\begin{array}{*{20}{c}}5\\0\end{array}} \right)=40+30+4=74[/math]
همین حالت را می توان از روش متمم حل کرد
ابتدا تعداد حالتهای انتخاب انجمن سه نفره از میان کل اعضا یعنی 9 نفر :
[math]\left( {\begin{array}{*{20}{c}}9\\3\end{array}} \right)=84[/math]
حالا حالتی که هیچ مردی انتخاب نشود یعنی همه شون زن باشن .
[math]\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)=10[/math]
طبق روش متمم :
تعداد حالات مطلوب=تعداد کل حالات-تعداد حالات نامطلوب
[math]\left( {\begin{array}{*{20}{c}}9\\3\end{array}} \right) – \left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)=84-10=74[/math]
دیدیم که در روش متمم همان جواب بدست آمد ، اینجاست که اهمیت و سرعت محاسبات روش متمم برای ما مشخص می شود.
ب)حداکثر دو نفر از آنها زن باشد.
یعنی یا دو تا از آنها زن باشند یا یکی و یا هیچکدام زن نباشن .هر سه حالت را در زیر محاسبه میکنیم .
[math]\left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right)\left( {\begin{array}{*{20}{c}}4\\1\end{array}} \right) + \left( {\begin{array}{*{20}{c}}5\\1\end{array}} \right)\left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right) + \left( {\begin{array}{*{20}{c}}5\\0\end{array}} \right)\left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right)\\[/math]
تمرینات
1-به چند طریق میتوان از میان 5 مرد و 3 زن ،یک گروه 5 نفری انتخاب کرد به طوریکه این گروه شامل حداقل 2 زن باشد ؟
2-در یک امتحان نهایی 10 سوال داده شده است ،به چند طریق می توان 8 سوال را جهت پاسخ گویی انتخاب کرد ،به شرط آنکه حداقل 4 سوال از 5 سوال اول انتخاب شده باشند؟
3-از میان 7 کشتی گیر و 5 وزنه بردار به چند روش می توان 3 نفر انتخاب کرد به طوری که حداقل یک نفر کشتی گیر باشد؟
4-به چند طریق می توان 8 نفر را در 7 اتاق متمایز قرار داد بطوریکه در هر اتاق حداقل یک نفر قرار گیرد ؟
5-چند تا عدد 7 رقمی با ارقام 2و3و8 داریم بطوریکه دقیقا دو رقم 8 داشته باشند؟