شاه کلید نکات
شاه کلید سوال
![[شاه کلید مای درس] | مباحثی در ترکیبیات](https://dl.my-dars.com/upload/image/01 (8)1728768461.jpg)
اگر کاری در مرحله اول به m روش و در مرحله دوم به n روش و در مرحله سوم به P روش و ... انجام شود کل کار به \(m \times n \times P \times ...\) روش انجام می شود.
مثال
1 با حروف کلمه Stop چند کلمه چهار حرفی با تکرار حروف می توان نوشت در صورتی که:
الف) با حرف T شروع شود؟
\(1 \times 4 \times 4 \times 4 = 64\)
ب) با حرف P شروع شده و به حرف O ختم شود؟
\(1 \times 4 \times 4 \times 1 = 16\)
2 می خواهیم 5 توپ با شماره های \(1,2,3,4,5\) را در 3 جعبه به رنگ های آبی، زرد و قرمز توزیع کنیم. این کار به چند طریق امکان پذیر است؟
برای هر توپ 3 انتخاب وجود دارد؛ بنابراین طبق اصل ضرب \(3 \times 3 \times 3 \times 3 \times 3 = {3^5}\) است.
تعداد حالت های کنار هم قرار گرفتن n شی متمایز را جایگشت آن n شی متمایز نامیده و برابر است با: \(n!\)
مثال
5 دانش آموز به چند طریق می توانند در یک صف بایستند؟
\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
الف) k نفر مشخص همواره کنار هم باشند.
\((n - k + 1)! \times k!\)
ب) k نفر مشخص همواره کنار هم نباشند.
\(n! - (n - k + 1)! \times k!\)
مثال
به چند طریق می توان 7 دانش آموز را در یک صف قرار داد به طوری که:
الف) دو نفر از آنها که برادرند کنار هم باشند؟
\(\begin{array}{l}(n - k + 1)! \times k!\\(7 - 2 + 1)! \times 2! = 6! \times 2! = 720 \times 2 = 1440\end{array}\)
ب) دو نفر از آنها که برادرند کنار هم نباشند؟
\(\begin{array}{l}n! - (n - k + 1)! \times k!\\7! - (7 - 2 + 1)! \times 2! \to 7! - 6! \times 2! = 5040 - 1440 = 3600\end{array}\)
\(\begin{array}{l}0! = 1\\1! = 1\end{array}\)
تعداد حالت های کنار هم قرار گرفتن k شی از n شی متمایز را با علامت \(P(n,k)\) نشان داده و از فرمول زیر حساب می کنیم:
\(P(n,k) = \frac{{n!}}{{(n - k)!}}\)
مثال
1 با حروف کلمه FAMILY و بدون تکرار حروف چند کلمه 4 حرفی شامل حرف M می توان ساخت؟
قرار دادن حرف M در یکی از چهار مکان به 4 طریق ممکن است و پر کردن سه مکان باقی مانده توسط 5 حرف باقی مانده به صورت زیر ممکن است:
\(P(5,3) = \frac{{5!}}{{(5 - 3)!}} = 60\)
طبق اصل ضرب = \(4 \times 60 = 240\)
2 شرکتی در نظر برای هر یک از شغل های نگهبانی، دفترداری، روابط عمومی و مسئول رایانه، یک نفر را استخدام کند، 10 نفر برای استخدام در این شغل ها داوطلب شده اند. شرکت به چند روش می تواند افراد را برای این مشاغل استخدام کند؟
برای نگهبانی هر کدام از 10 نفر را می توان انتخاب کرد پس 10 روش، برای دفترداری نیز 9 روش و برای روابط عمومی 8 روش و برای مسئول رایانه نیز 7 روش وجود دارد. در نتیجه \(10 \times 9 \times 8 \times 7\) طریق وجود دارد. (یا می توان ابتدا 4 نفر از 10 نفر را انتخاب کرده و سپس آن چهار نفر را برای شغل ها انتخاب نمود)
\(\left( {\begin{array}{*{20}{c}}{10}\\4\end{array}} \right) \times 4! = \frac{{10!}}{{6!}}\)
اگر از بین n شی متمایز بخواهیم k شی (\(k \le n\)) را انتخاب کنیم و حالت های کنار هم قرار گرفتن آنها اهمیتی نداشته باشد آن را یک ترکیب k شی از n شی می گوییم و با علامت \(C(n,k)\) یا \(\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)\) نشان داده و از فرمول زیر محاسبه می کنیم:
\(C(n,k) = \frac{{n!}}{{k! \times (n - k)!}}\)
مثال
1 به چند طریق می توان از بین 8 نفر، یک تیم 3 نفری انتخاب کرد؟
\(C(8,3) = \frac{{8!}}{{3! \times 5!}} = 56\)
2 شرکتی در نظر برای هر یک از شغل های نگهبانی، دفترداری، روابط عمومی و مسئول رایانه، به ترتیب \(3,2,2,1\) را استخدام کند، 10 نفر برای استخدام در این شغل ها داوطلب شده اند. شرکت به چند روش می تواند افراد را برای این مشاغل استخدام کند؟
\(\left( {\begin{array}{*{20}{c}}{10}\\3\end{array}} \right) \times \left( {\begin{array}{*{20}{c}}7\\2\end{array}} \right) \times \left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right) \times \left( {\begin{array}{*{20}{c}}3\\1\end{array}} \right)\)
اگر n شی متمایز داشته باشیم به طوری که P تای آنها از نوع اول، q تای آنها از نوع دوم و r تای آنها از نوع سوم و ... باشد تعداد کل جایگشت های اشیا برابر است با:
\(\frac{{n!}}{{p! \times q! \times r! \times ...}}\)
مثال
1 9 نفر به چند طریق می توانند در سه اتاق 2 نفره، 3 نفره و 4 نفره در یک هتل اسکان یابند؟
\(\begin{array}{l}\frac{{n!}}{{p! \times q! \times r! \times ...}}\\\frac{{9!}}{{2! \times 3! \times 4!}} = \frac{{362880}}{{288}} = 1260\end{array}\)
2 با حروف کلمات (انتخابات) چند کلمه 8 حرفی بدون توجه به مفهوم آن می توان ساخت؟
با توجه به اینکه 3 حرف (الف) و 2 حرف (ت) وجود دارد، در نتیجه \(\frac{{8!}}{{3! \times 2!}}\) است.
اگر یک شبکه \(n \times m\) مطابق شکل زیر داشته باشیم و فقط به راست یا بالا حرکت کنیم تعداد مسیر ها از A به B برابر است با:
تعداد مسیر ها = \(\frac{{(n + m)!}}{{n! \times m!}}\)
مثال
چند مسیر از A به B وجود دارد به طوری که فقط مجاز باشیم به راست یا بالا جرکت کنیم؟
\(\begin{array}{l}\frac{{(n + m)!}}{{n! \times m!}}\\\frac{{(4 + 5)!}}{{4! \times 5!}} = \frac{{362880}}{{2880}} = 126\end{array}\)
حل معادله سیاله خطی با ضرایب واحد:
تعداد جواب های صحیح و نا منفی معادله \({x_1} + {x_2} + ... + {x_k} = n\) برابر است با:
\(\left( {\begin{array}{*{20}{c}}{n + k - 1}\\{k - 1}\end{array}} \right)\)
که همان تعداد انتخاب های دلخواه n شاخه گل از بین k نوع گل است.
مثال
1 معادله \({x_1} + {x_2} + {x_3} = 7\) چند جواب صحیح و نا منفی دارد؟
n = 7
k = 3
\(\left( {\begin{array}{*{20}{c}}{n + k - 1}\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{7 + 3 - 1}\\{3 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}9\\2\end{array}} \right) = \frac{{9!}}{{2! \times 7!}} = 36\)
2 به چند طریق می توان از بین 4 نوع گل، دسته گلی شامل 8 شاخه گل را به دلخواه انتخاب کرد؟
تعداد گل های نوع اول را \({x_1}\) و نوع دوم را \({x_2}\) و .... آنگاه در نظر می گیریم:
\(\begin{array}{l}{x_1} + {x_2} + {x_3} + {x_4} = 8\\n = 8,k = 4\\\left( {\begin{array}{*{20}{c}}{n + k - 1}\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{8 + 4 - 1}\\{4 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{11}\\3\end{array}} \right) = \frac{{11!}}{{3! \times 8!}} = 165\end{array}\)
تعداد جواب های طبیعی معادله \({x_1} + {x_2} + ... + {x_k} = n\) برابر است با:
\(\left( {\begin{array}{*{20}{c}}{n - 1}\\{k - 1}\end{array}} \right)\)
مثال
1 معادله \({x_1} + {x_2} + {x_3} = 5\) چند جواب صحیح و مثبت (طبیعی) دارد؟
n = 5
k = 3
\(\left( {\begin{array}{*{20}{c}}{n - 1}\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{5 - 1}\\{3 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right) = \frac{{4!}}{{2! \times 2!}} = 6\)
2 به چند طریق می توان دسته گلی شامل 9 شاخه گل را از بین 4 نوع گل انتخاب کرد به شرط آن که از هر نوع گل حداقل 1 شاخه انتخاب شود؟
چون از هر نوع گل حداقل 1 شاخه باید انتخاب شود و جواب های معادله عدد طبیعی هستند، آنگاه:
\(\begin{array}{l}{x_1} + {x_2} + {x_3} + {x_4} = 9\\n = 9,k = 4\\\left( {\begin{array}{*{20}{c}}{n - 1}\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{9 - 1}\\{4 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}8\\3\end{array}} \right) = 56\end{array}\)
اگر در مساله سیاله شرط هایی به صورت \({x_1} \ge a\) و \({x_2} \ge b\) و ... داشته باشیم در این صورت متغیر را تغییر داده و معادله را طبق شرایط زیر حل می کنیم:
\(\begin{array}{l}{x_1} \ge a \to {x_1} - a \ge 0 \to {x_1} - a = {y_1} \to {x_1} = {y_1} + a,{y_1} \ge 0\\{x_2} \ge b \to {x_2} - b \ge 0 \to {x_2} - b = {y_2} \to {x_2} = {y_2} + b,{y_2} \ge 0\end{array}\)
مثال
1 معادله \({x_1} + {x_2} + {x_3} = 7\) چند جواب طبیعی دارد؟
\(\begin{array}{l}{x_1} \ge {x_1} = {y_1} + 1\\{x_2} \ge {x_2} = {y_2} + 1\\{x_3} \ge {x_3} = {y_3} + 1\\{y_1} + 1 + {y_2} + 1 + {y_3} + 1 = 7 \to {y_1} + {y_2} + {y_3} = 4\\n = 4,k = 3\\\left( {\begin{array}{*{20}{c}}{n + k - 1}\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{4 + 3 - 1}\\{3 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}6\\2\end{array}} \right) = 15\end{array}\)
2 به چند طریق می توان 8 توپ یکسان را بین 4 نفر توزیع کرد، هرگاه بخواهیم هر نفر حداقل یک توپ داشته باشد؟
\(\begin{array}{l}{x_1} + {x_2} + {x_3} + {x_4} = 8,{x_i} \ge 1,i = 1,2,3,4\\n = 8,k = 4\\\left( {\begin{array}{*{20}{c}}{n - 1}\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{8 - 1}\\{4 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}7\\3\end{array}} \right) = 35\end{array}\)
تمرین
1 با حروف کلمه (می سی سی پی) چند جایگشت 8 حرفی با معنا یا بی معنا می توان نوشت؟
تعداد (ی) = 4
تعداد (س) = 2
\(\frac{{8!}}{{4! \times 2!}} = 840\)
2 اگر داشته باشیم \(A = \{ 1,2,3,4\} \) و \(B = \{ 5,6,7,8,9\} \) در این صورت چند کد یا رمز 5 رقمی می توان نوشت که هر یک شامل دو رقم متمایز از A و سه رقم متمایز از B باشد؟
\(\left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right) \times \left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right) \times 5! = 7200\)
3 6 کتاب ریاضی مختلف و 5 کتاب فیزیک متمایز را به چند طریق می توان کنار هم در یک ردیف قرار داد به طوری که:
الف) کتاب ها یکی در میان قرار گیرند؟
\(6! \times 5!\)
ب) کتاب های ریاضی کنار هم و کتاب های فیزیک نیز کنار هم باشند؟
\(6! \times 5! \times 2!\)
4 به چند طریق می توان 4 خودکار متفاوت را بین 8 نفر توزیع کرد به شرطی که هیچکس بیشتر از یک خودکار نداشته باشد؟ (به هر نفر حداکثر یک خودکار داده باشیم)
\(P(8,4) = \frac{{8!}}{{(8 - 4)!}} = \frac{{8!}}{{4!}} = 1680\)
5 7 نفر به چند طریق می توانند در دو اتاق دو نفره و یک اتاق سه نفره قرار بگیرند؟
\(\frac{{7!}}{{2! \times 2! \times 3!}} = 210\)
6 به چند طریق می توان 5 توپ یکسان را بین 3 نفر و به دلخواه توزیع کرد؟
\(\begin{array}{l}\left( {\begin{array}{*{20}{c}}{n + k - 1}\\{k - 1}\end{array}} \right)\\{x_1} + {x_2} + {x_3} = 5 \to \left( {\begin{array}{*{20}{c}}{5 + 3 - 1}\\{3 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}7\\3\end{array}} \right) = 21\end{array}\)
7 به چند طریق می توان 8 توپ یکسان را بین 4 نفر توزیع کرد هر گاه بخواهیم هر نفر حداقل یک توپ داشته باشد؟
\(\left( {\begin{array}{*{20}{c}}{n - 1}\\{k - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{8 - 1}\\{4 - 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}7\\3\end{array}} \right) = 35\)
تهیه کننده: عادل نقدی
