درسنامه کامل ریاضیات گسسته فصل 3 ترکیبیّات (شمارش)

اصل ضرب

اگر کاری در مرحله اول به m روش و در مرحله دوم به n روش و در مرحله سوم به P روش و ... انجام شود کل کار به \(m \times n \times P \times ...\) روش انجام می شود.

جایگشت

تعداد حالت های کنار هم قرار گرفتن n شی متمایز را جایگشت آن n شی متمایز نامیده و برابر است با: \(n!\)

N نفر به چند طریق می توانند در یک صف بایستند به طوری که:

الف) k نفر مشخص همواره کنار هم باشند.

\((n - k + 1)! \times k!\)

ب) k نفر مشخص همواره کنار هم نباشند.

\(n! - (n - k + 1)! \times k!\)

جایگشت k شی از n شی متمایز

تعداد حالت های کنار هم قرار گرفتن k شی از n شی متمایز را با علامت \(P(n,k)\) نشان داده و از فرمول زیر حساب می کنیم:

\(P(n,k) = \frac{{n!}}{{(n - k)!}}\)

ترکیب k شی از n شی متمایز

اگر از بین 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)!}}\)

جایگشت های با تکرار

اگر n شی متمایز داشته باشیم به طوری که P تای آنها از نوع اول، q تای آنها از نوع دوم و r تای آنها از نوع سوم و ... باشد تعداد کل جایگشت های اشیا برابر است با:

\(\frac{{n!}}{{p! \times q! \times r! \times ...}}\)

اگر یک شبکه \(n \times m\) مطابق شکل زیر داشته باشیم و فقط به راست یا بالا حرکت کنیم تعداد مسیر ها از A به B برابر است با:

تعداد مسیر ها = \(\frac{{(n + m)!}}{{n! \times m!}}\)

حل معادله سیاله خطی با ضرایب واحد:

تعداد جواب های صحیح و نا منفی معادله \({x_1} + {x_2} + ... + {x_k} = n\) برابر است با:

\(\left( {\begin{array}{*{20}{c}}{n + k - 1}\\{k - 1}\end{array}} \right)\)

که همان تعداد انتخاب های دلخواه n شاخه گل از بین k نوع گل است.

حل معادله \({x_1} + {x_2} + ... + {x_k} = n\) به روش تغییر متغیر

اگر در مساله سیاله شرط هایی به صورت \({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,2,3,...,n\) به شکل یک مربع \(n \times n\) را که سطر ها و ستون های آن با اعداد \(1,2,3,...,n\) پر شده باشد و در هیچ سطر آن و نیز در هیچ ستون آن عدد تکراری وجود نداشته باشد، مربع لاتین می نامیم و به هر یک از اعداد درون مربع لاتین یک درایه می گوییم.

در حالت کلی شکل زیر یک مربع لاتین \(n \times n\) است که به آن مربع لایتن چرخشی می گوییم.

ساخت مربع لاتین

روش چرخشی

در سطر اول اعداد \(1,2,3,...,n\) را می گذاریم، آخرین عدد سطر اول را که n است در ابتدای سطر دوم نوشته و بقیه عدد ها را در سطر دوم یکی یکی به راست می بریم و این کار را تکرار می کنیم.

روش جا به جایی سطر و ستون

با تعویض جای هر دو سطر یا هر دو ستون یک مربع لاتین می توان مربع لاتین جدیدی ساخت.

در a ستون 1 با ستون 3 تعویض شد و در b سطر 1 با سطر 2 تعویض شد.

روش جایگشت

می توانیم بدون تغییر جای سطر ها و ستون ها، جای خود عدد ها را با هم عوض کنیم، مثلا به جای تمام 3 ها 2 بنویسیم و برعکس یا همه 1 ها را 2 و همه 2 ها را به 3 و همه 3 ها را به 1 تبدیل کنیم و ... . در این صورت می گوییم جایگشت روی 1 عدد اعمال کرده ایم، با این روش مربع لاتین جدیدی ساخته می شود.

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

فرض کنیم A و B دو مربع لاتین هم مرتبه باشند به طوری که از کنار هم قرار دادن درایه های نظیر به نظیر این دو مربع، مربع جدیدی از همان مرتبه حاصل شود که هر خانه آن حاوی یک عدد دو رقمی است که تمام رقم های سمت چپ مربوط به مربع a و تمام رقم های سمت راست مربوط به مربع B (و یا برعکس) است، اگر هیچ یک از اعداد دو رقمی موجود در خانه های مربع جدید تکرار نشده باشند می گوییم دو مربع لاتین A و B متعامدند.

متعامد (عدد تکراری ندارد)

نا متعامد (عدد تکراری دارد)

یک روش برای ساختن دو مربع لاتین متعامد از مرتبه یک عدد فرد:

به عنوان مثال نحوه ایجاد دو مربع لاتین متعامد \(3 \times 3\) (مرتبه فرد است) را توضیح می دهیم:

دو شکل مانند زیر ایجاد می کنیم:

حال دو شکل را با هم ترکیب می کنیم:

اصل شمول و عدم شمول برای دو مجموعه

تعداد عضو هایی که به مجموعه A یا به مجموعه B تعلق دارند برابر است با:

\(\left| {A \cup B} \right| = \left| A \right| + \left| B \right| - \left| {A \cap B} \right|\)

واضح است که تعداد عضو هایی که به هیچ یک از مجموعه های A و B تعلق ندارند برابر است با:

\(\left| {\bar A\bar \cup \bar B} \right| = \left| {\bar A \cap \bar B} \right| = \left| {(A \cup B)'} \right| = \left| S \right| - \left| {A \cup B} \right|\)

اصل شمول و عدم شمول برای سه مجموعه

تعداد عضو هایی که حداقل به یکی از سه مجموعه A یا B یا C تعلق دارد برابر است با:

\(\begin{array}{l}\left| {A \cup B \cup C} \right| = \left| A \right| + \left| B \right| + \left| C \right| - \left| {A \cap B} \right| - \left| {A \cap C} \right| - \left| {B \cap C} \right| + \left| {A \cap B \cap C} \right|\\\left| {{{\left( {A \cap B \cap C} \right)}^\prime }} \right| = \left| {A' \cap B' \cap C'} \right| = \left| S \right| - \left| {A \cup B \cup C} \right|\end{array}\)

تابع شماری

اگر A و B دو مجموعه باشند، تعداد توابع از A به B برابر است با:

\({\left| B \right|^{\left| A \right|}}\)

اگر \(\left| A \right| = m\) و \(\left| B \right| = k\) با شرط \(m \le k\) تعداد توابع یک به یک از مجموعه A به مجموعه B برابر است با:

\({(k)_m} = \frac{{k!}}{{(k - m)!}}\)

تابع f از مجموعه A به مجموعه B را پوشا می نامند هر گاه برد تابع f، شامل کل اعضای B باشد، به عبارت دیگر به هر عضو B یک پیکان رسم شود و آن را به صورت زیر نشان می دهند.

\(\begin{array}{l}A = \{ {a_1},{a_2},...,{a_n}\} ,B = \{ {b_1},{b_2},...,{b_n}\} \\f:A \to B\\{R_f} = B\end{array}\)

برای پیدا کردن تعداد تابع های پوشا از مجموعه n عضوی A به مجموعه m عضوی B از فرمول های زیر استفاده می کنیم که همان اصل شمول و عدم شمول است:

\(\begin{array}{l}{A_j} = \{ f:A \to B|f({a_i}) \ne {b_j},1 \le i \le n,1 \le j \le m\} \\\left| S \right| = {\left| B \right|^{\left| A \right|}} = {m^n},\left| {{A_1}} \right| = \left| {{A_2}} \right| = ... = \left| {{A_m}} \right| = {2^m}\\\left| {{A_1} \cap {A_2}} \right| = \left| {{A_1} \cap {A_3}} \right| = ... = \left| {{A_2} \cap {A_3}} \right| = ... = 1,\left| {{A_1} \cap {A_2} \cap {A_3} \cap ... \cap {A_m}} \right| = 0\\\left| {{{\bar A}_1} \cap {{\bar A}_2} \cap ... \cap {{\bar A}_m}} \right| = \left| {{{\bar A}_1}\bar \cup {{\bar A}_2}\bar \cup ...\bar \cup {{\bar A}_m}} \right| = \left| S \right| - \left| {{A_1} \cup {A_2} \cup ... \cup {A_m}} \right|\end{array}\)

اگر m کبوتر و n لانه داشته باشیم و \(m\rangle n\) و همه کبوتر ها درون لانه ها قرار بگیرند در این صورت لانه ای وجود دارد که حداقل دو کبوتر در آن قرار گرفته است.

تعمیم اصل لانه کبوتری

هر گاه (\(kn + 1\)) کبوتر یا بیشتر در n لانه قرار بگیرند در این صورت لانه ای وجود دارد که حداقل (\(k + 1\)) کبوتر در آن قرار گرفته است.