درسنامه کامل ریاضیات گسسته

گزاره

گزاره به يک حکم (يا ادعا) گفته می شود که يا دقيقاً درست و يا دقيقاً نادرست باشد.

اگر گزاره در تمام حالات ممکن درست باشد، گوييم آن گزاره درست است، ولی برای نادرست بودن آن، کافی است فقط در يک مورد نادرست شود.

بنابراين، در مواجهه با يک گزاره، در کل دو راه برای روشن کردن وضعيت آن وجود دارد.

رد کردن يا اثبات درستی

برايی رد يک ادعای کلی، روش زير را به کار می بريم.

مثال نقض

برای نشان دادن اينكه يک حكم کلی نادرست است، کافی است مثالی آورده شود كه كليت آن حكم را رد كند. به چنين مثالی، (مثال نقض) گفته می شود.

ممکن است با بررسی مثال های گوناگون، نتوانيم هيچ مثال نقضی پيدا کنيم و تمام مثال های آورده شده، حکم را تاييد کنند. در اين صورت، توجه کنيد:

1. هر تعداد مثال در تاييد يک حکم آورده شود، باعث اثبات آن نخواهد شد، چون امکان دارد مثال بعدی، يک مثال نقض باشد.
2. وقتی چندين مثال يک حکم را تاييد می کنند، احتمال درست بودن حکم معمولاً بيشتر می شود.

روش نتيجه گيری با بررسی چند مثال و مشاهده ی درستی حکم را (استدلال استقرايی) گويند. اين روش در علوم تجربی کاربرد فراوان دارد. اما در ریاضیات بعد از به کار بردن استدلال استقرايی، حکم را به عنوان يک (حدس) يا (فرضيه) می پذيريم.

برای اينکه فرضيه يا حدس تاييد قطعی شود، نياز به اثبات دارد که توسط دو مؤلفه ی زير انجام می شود.

حقايق پذيرفته شده

اصول و احکامی که قبلاً درستی آنها پذيرفته يا اثبات شده است.

روش های درست استنتاج

معمولاً حقايق پذيرفته شده ی قبلی با روش های درست استدلال، مفروضات مسأله را به کار می برنـد تـا يـک حکـم جديـد اثبات شود.

حقايق پذيرفته شده

برخی حقايق پذيرفته شده که در اثبات ها بيشتر به کار می روند را ببينيد:

هر عدد زوج به صورت \(2k\)  و هر عدد فرد به صورت \(2k - 1\)  است.

هر عدد گويا را ميتوان به صورت کسر \(\frac{m}{n}\)  نوشت که m و n دو عدد صحيح بوده و مخرج غير صفر است.

هر عددی که نتوان آن را به صورت کسر گويا نوشت، گنگ است.

روش های اثبات

می توان روش های اثبات احکام رياضی را در دو نوع کلی طبقه بندی کرد:

اثبات مستقيم و اثبات غيرمستقيم

اثبات مستقيم

در روش هايی که در اين گروه جای می گيرند، فرض مسأله و حقايق قبلی به طور مناسب به کار رفته، حکم تاييد می شود و اثبات صورت می پذيرد.

اثبات غير مستقيم

در اين گروه از روش های اثبات، به نوعی حکم مسأله و حقايق قبلی را مورد استفاده قرار داده و درسـت بـودن حکـم را نتيجه می گيريم.

برسی تمام حالات

گاهی استفاده از تکنيک زير، در اثبات مستقيم احکام مورد نياز است:

تفکیک فرض به تمام حالت های ممکن، و بررسی درستی حکم در هر حالت.

به هم ارزی زير بين گزاره ها توجه کنيد:

\(\begin{array}{l}({P_1} \vee {P_2} \vee ... \vee {P_K}) \Rightarrow q \Leftrightarrow \sim ({P_1} \vee {P_2} \vee ... \vee {P_K}) \vee q\\ \Leftrightarrow ( \sim {P_1} \wedge \sim {P_2} \wedge ... \wedge \sim {P_K}) \vee q\\ \Leftrightarrow ( \sim {P_1} \vee q) \wedge ( \sim {P_2} \vee q) \wedge ... \wedge ( \sim {P_K} \vee q)\\ \Leftrightarrow ({P_1} \Rightarrow q) \wedge ({P_2} \Rightarrow q) \wedge ... \wedge ({P_K} \Rightarrow q)\end{array}\)

یعنی اگر فرض در کل به حالت های \({P_2},{P_1}\)  ... و \({P_K}\)  تفکيک شده و هرکدام از آن ها درستی q را نشان دهند. درستی q در کل اثبات می گردد.

در ادامه، دو روش در اثبات غير مستقيم و نمونه هايی از هر کدام ببينيد:

برهان خلف

برای استفاده از اين روش، طبق گام های زير عمل می کنيم:

حكم مورد نظر را نادرست در نظر می گيريم؛ يعنی فرض می کنيم حکم نادرست باشد.

با توجه به فرض مرحله ی قبل و بيان استدلالی مناسب، (حقايق شناخته شده) يا (فرض) آن قضيه يا مسأله را نقض می كنيم.

نتيجه می گيريم حكم آن مسأله نمی تواند نادرست باشد و از ابتدا صحيح بوده است.

اثبات بازگشتی

در اثبات به طريق بازگشتی به ترتيب زير عمل می کنيم:

درستی حكم را موقتاً می پذيريم.

با شروع از حکم، در چند مرحله به يک رابطه ی بديهی يا فرض داده شده می رسيم.

اکنون اگر تمام مراحل را بتوان از آخر به اول نتيجه گرفت، يعنی اعمال انجام شده برگشت پذير باشـند، درسـتی حكم تأييد می شود.

به بيان دقيق مفهوم (بخش پذيری) در اعداد صحيح توجه کنيد:

بخش پذيری

فرض کنید a و \(b \ne 0\)  عددهایی صحیح باشند.

عدد a را بر b(بخش پذير) گوييم، هرگاه عدد صحيح k يافت شود كه \(a = bk\)  در این صورت می نویسیم: \(b|a\)

برای نمونه

داریم: \(4| - 12\) ، زیرا عدد \( - 12\) را می توان به صورت \(4( - 3)\)  نوشت.

خواص مقدماتی

تمام اعداد بر 1 و \( - 1\) بخش پذير هستند؛ يعنی همواره: \( \pm 1|a\)

زیرا

\(a = 1 \times a \to 1|a,a = - 1 \times ( - a) \to - 1|a\)

تمام اعداد صحيح، عدد صفر را عاد می کنند، زيرا \(0 = a \times 0\)  به عبارت دیگر؛ صفر تنها عددی است که بر تمام اعداد بخش پذير است، يعنی همواره، \(a|0\) .

هيچ عددی بر صفر بخش پذير نيست. ولی چون تساوی \(0 = 0 \times k\)  برای هر عدد صحیح k برقرار است، خواهیم داشت \(0|0\)  بنابراین:

\(0|a \Rightarrow a = 0\)

يعنی عدد صفر فقط خودش را عاد می کند.

هر عددی بر خودش بخش پذير است؛ زيرا:

\(a = a \times 1 \Rightarrow a|a\)

به صورت مشابه، موارد \(a| - a\)  و \( - a|a\)  نيز درست هستند. يعنی \( \pm a| \pm a\)

يادآوری يک مفهوم بسيار پرکاربرد در مبحث نظريه اعداد:

عدد اول

عدد طبیعی \(p\rangle 1\)  را اول گوییم. هرگاه غير از 1 و خودش هيچ مقسوم عليه مثبتی نداشته باشد. بنابراين، اگر p عددی اول باشد:

\(a|p \Rightarrow a = \pm 1,a = \pm p\)

ساير اعداد طبيعی بزرگ تر از يک را (مركب) گوييم. بنابراين:

عدد ١ نه اول است و نه مركب.

در ادامه ويژگی های اصلی شمارش، دليل هر کدام و برخی کاربردهای آنها را ببينيد.

1) اگر a عدد b را عاد کند، aهر مضربd  از b را نيز عاد می کند؛ يعنی برای هر عدد صحيح m :

\(a|b \Rightarrow a|bm\)

برای نمونه؛

\(5|10 \Rightarrow 5|20,5| - 10,5|50,...\)

2) شمارش، خاصيت تعدی دارد. يعنی اگر a بر b و b بر c بخش پذير باشد، آنگاه:a بر c بخش پذير است.

با صورت نمادين

\(c|b \wedge b|a \Rightarrow c|a\)

برای نمونه؛

از این که \(6|12\)  و \(12|48\)  می توان نتیجه گرفت: \(6|48\)

3) اين ويژگی به صورت زير بيان می شود:

اگر دو عدد بر عددی بخش پذير باشند، آنگاه جمع و تفريق آنها هم بر آن عدد بخش پذير است.

با نماد رياضی:

\(a|b \wedge a|c \Rightarrow a|b \pm c\)

4) اگر داشته باشيم \(a|b\)  و \(b \ne 0\)  باشد، آنگاه \(\left| a \right| \le \left| b \right|\)  به صورت نمادین:

\(a|b \wedge b \ne 0 \Rightarrow \left| a \right| \le \left| b \right|\)

به بیان ساده؛ يک عدد مثبت نمی تواند بر عددهای بزرگتر از خود بخش پذير باشد. زیرا:

طبق فرض، عدد \(k \in \mathbb{Z} - \{ 0\} \)  هست که \(b = ak\)  در نتیجه:

\(\left| b \right| = \left| a \right|\left| k \right| \to \left| k \right| \ge 1 \to \left| b \right| \ge \left| a \right|\)

قضیه تقسیم

در تقسيم عدد صحيح a بر عدد طبيعی b ، اعداد صحيح و يكتای q و r وجود دارند که:

\(\begin{array}{l}a = bq + r\\0 \le r\langle b\end{array}\)

عددهای q و r به ترتيب (خارج قسمت) و (باقيمانده) تقسيم a بر b نام دارند.

دسته بندی اعداد صحیح

فرض کنید \(m\rangle 1\)  عدد طبيعی ثابتی باشد. عدد صحيح دلخواه a را در نظر گرفته و آن را بر m تقسيم می کنيم:

\(\begin{array}{l}a = mk + r\\r = 0,1,2,...,m - 1\end{array}\)

می بينيد که می توان عددهای صحيح را بر حسب باقيمانده تقسيم بر m در يک مجموعه قرار داد.

اگر باقيمانده صفر باشد، عددها به صورت زير هستند:

\(a = mk,k \in \mathbb{Z}\)

مجموعه ی تمام اين نوع اعداد را با \({[0]_m}\)  نشان می دهیم:

\({[0]_m} = \{ mk|k \in \mathbb{Z}\} \)

اگر باقيمانده ی تقسيم برابر 1 شود، عددها به اين صورت هستند:

\({[1]_m} = \{ mk + 1|k \in \mathbb{Z}\} \)

ساير عددهای صحيح نيز به يکی از صورت های زير خواهند بود:

\(\begin{array}{l}{[2]_m} = \{ mk + 2|k \in \mathbb{Z}\} \\{[3]_m} = \{ mk + 3|k \in \mathbb{Z}\} \\.\\.\\{[m - 1]_m} = \{ mk + m - 1|k \in \mathbb{Z}\} \end{array}\)

بنابراين:

با انتخاب عدد طبيعی m ، مجموعه ی  \(\mathbb{Z}\) دقيقاً به تعداد m زير مجموعه افراز می شود:

\({[0]_m},{[1]_m},{[2]_m},...,{[m - 1]_m}\)

یعنی

1. اين مجموعه ها هيچکدام تهی نيستند.
2. دو به دو اشتراک ندارند.
3. هر عدد صحيح در يکی از آنها جای دارد.

دو مفهوم ب.م.م و ک.م.م کاربردهای زيادی در نظريه اعداد دارند.

ب.م.م اعداد

فرض كنيد a و b دو عدد صحيح باشند كه لااقل یكی از آنها غيـر صـفر اسـت. عـدد طبيعـی d را (ب.م.م) يعنـی بزرگترين مقسوم عليه مشترک اين دو عدد گوئيم، هرگاه:

1) \(d|b,d|a\)

2) ساير مقسوم عليه های مشترک a و b از d كوچكتر باشند. در اين صورت می نويسيم:

\((a,b) = d\)

در حالت خاص:

اگر \(a|b\) ، آنگاه \((a,b) = \left| a \right|\)  است. به ویژه:

\((a,a) = \left| a \right|,(a,0) = \left| a \right|\)

البته عبارت \((0,0)\)  بی معنی است.

حالت خاص زير در مورد ب.م.م اعداد اهميت بسياری دارد.

اعداد متباين:

دو عدد a و b را نسبت به هم اول يا (مُتَبايِن) گوئيم، هرگاه:

\((a,b) = 1\)

به دو مورد در ارتباط با اين مفهوم توجه کنيد:

واضح است که \((4,9) = 1\)  و بنابراين متباين بودن اعداد ربطی به اول بودن تک تک آنها ندارد.

ولی عکس آن صحيح است:

اگر p و q دو عدد اول مختلف باشند، همواره: \((p,q) = 1\) .

دو عدد a و b وقتی نسبت به هم اول هستند که در تجزيه ی اين دو عدد به عددهای اول، عامـل اول مـشترکی وجود نداشته باشد. برای نمونه؛

چون \(35 = 5 \times 7,48 = {2^2} \times 3\) ، بنابراین \((48,35) = 1\)  است.

اکنون مضرب های مشترک دو عدد صحيح را بررسی می کنيم:

ک.م.م اعداد

فرض كنيم a و b دو عدد صحيح باشند كه هر دو غير صفر هستند. عدد طبيعـی c را (ک.م.م) يعنـی کوچـکتـرين مضرب مشترک اين دو عدد گوئيم، هرگاه:

1) \(b|c,a|c\)

2) ساير مضرب های مثبت و مشترک a و b از c بزرگتر باشند. در اين صورت می نويسيم:

\([a,b] = c\)

در يک حالت خاص

هر گاه \(a|b\) ، آنگاه \([a,b] = \left| b \right|\)  است؛ به ویژه:

\([a, \pm a] = |a|,[ \pm 1,a] = |a|\)

تکنیک \(a'\) و \(b'\)

ابتدا توجه کنيد:

اگر a و b دو عدد صحيح و \((a,b) = d\)  باشد، آنگاه \((\frac{a}{d},\frac{b}{d}) = 1\)  است.

اکنون فرض کنيد \((a,b) = d\)  باشد، آنگاه:

قرار می دهيم: \(\frac{b}{d} = b',\frac{a}{d} = a'\)

طبق مرحله ی قبل خواهيم داشت: \(a = a'd\)  و \(b = b'd\)  و البته \((a',b') = 1\)

ک.م.م بر حسب  \(a'\) و \(b'\)

ک.م.م برابر \([a,b] = a'b'd\)  است، زیرا:

\([a,b] = \frac{{a'd \times b'd}}{d} \Rightarrow [a,b] = a'b'd\)

گراف از مجموعه ای از نقاط (که به هر کدام راس می گوییم) و مجموعه ای از خطوط (که به هرکدام یال می گوییم) تشکیل شده است. هر یال بین دو راس قرار دارد. در گراف G مجموعه ی راس ها را با (Vertex) V (G) و مجموعه یال ها را با (Edge) E (G) نشان می دهیم.

گراف یک روش مدل سازی برای نشان دادن رابطه بین اعضای یک مجموعه است.

به گرافی که یال های آن جهت داشته باشند، گراف جهت دار می گوییم. در نمایش گراف جهت دار با استفاده از نماد های ریاضی، یال هارا با زوج مرتب نشان می دهیم.

برای رسم نمودار یک گراف روش یکتایی وجود ندارد و شکل گراف صرفا باید مشخص کند که کدام راس ها به هم متصل اند.

مثلا دو نمودار زیر هر دو یک گراف را نمایش می دهند.

بین هر دو راس گراف ممکن است بیش از یک یال موجود باشد و همچنین یک یال ممکن است یک راس را به خود آن راس وصل کند که در این صورت به آن یال طوقه می گویند.

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

مرتبه و اندازه گراف

به تعداد راس های گراف G، مرتبه ی گراف گفته و آن را با P نشان می دهیم. به تعداد یال های گراف G، اندازه ی گراف گفته و آن را با q نشان می دهیم.

تعریف درجه راس گراف

به تعداد یال های متصل به گراف G که به راس V متصل اند، درجه ی آن راس گفته و آن را با \({\deg _G}(v)\) یا \(\deg (v)\) نشان می دهیم. اگر درجه یک راس عددی فرد باشد، به آن راس فرد و اگر درجه زوج باشد، به آن راس زوج می گوییم. در صورتی که \(\deg (v) = 0\) باشد (یعنی راس مورد نظر به راس دیگر متصل نباشد) به v راس تنها یا ایزوله می گوییم.

دو راس مجاور

دو راس که توسط یالی به هم متصل شده باشند را مجاور (یا همسایه) می نامیم. مثلا در گراف زیر راس های مجاور و غیر مجاور عبارت اند از:

مجموعه های همسایه های یک راس

فرض کنیم \(v \in V(G)\)، به مجموعه راس هایی از گراف g که به راس v متصل هستند، همسایگی باز راس v می گوییم و با \({N_G}(v)\) نمایش می دهیم. اضافه کردن خود راس v به \({N_G}(v)\) همسایگی بسته ی راس v را به دست می دهد که آن را با \({N_G}[v]\) نمایش می دهیم. می توان این دو مجموعه را به صورت زیر نشان داد:

\(\begin{array}{l}{N_G}(v) = \{ u \in V(G):uv \in E(G)\} \\{N_G}[v] = {N_G}(v) \cup \{ v\} \end{array}\)

دو یال مجاور

دو یال را مجاور می نامیم هر گاه راسی وجود داشته باسد که هر دو یال به آن وصل باشند. مثلا در گراف زیر یال های \({v_1}{v_2}\) و \({v_2}{v_3}\) مجاورند. ولی یال های \({v_1}{v_2}\) و \({v_3}{v_4}\) مجاور نیستند.

بزرگ ترین و کوچک ترین درجه گراف

بزرگ ترین درجه در بین راس های یک گراف را ماکزیمم درجه نامیده و آن را با نماد \(\Delta (G)\) نمایش می دهیم. به صورت مشابه، کوچک ترین درجه را مینیمم درجه نامیده و با نماد \(\delta (G)\) نمایش می دهیم.

برای مثال در گراف زیر \(\Delta = 3\) و \(\delta = 1\)

حواستان باشد ممکن است چند راس از درجه ماکسیمم یا مینیمم وجود داشته باشد.

در گراف از مرتبه p، راسی که با همه رئوس دیگر مجاور باشد، را راس فول (پر) می نامیم. در واقع راس فول دارای درجه \(p - 1\) است.

ارتباط درجه راس ها با تعداد یال ها

فرض کنید گراف G از مرتبه ی p و اندازه ی q باشد، در این صورت:

\(\sum\limits_{i - 1}^p {\deg ({v_i}) = } \deg ({v_1}) + \deg ({v_2}) + ... + \deg ({v_p}) = 2q\)

در نتیجه تعداد راس های فرد هرگراف عددی زوج است.

گراف های منتظم

گرافی که درجه ی همه راس های آن r باشد، گراف r-منظم (از مرتبه p) نامیده می شود. برای نمونه گراف های زیر 2-منتظم و 3-منتظم هستند:

گراف های کامل

گرافی از مرتبه ی p که هر دو راس آن مجاور باشند را گراف کامل نامیده و با \({K_p}\) نشان می دهیم.

در واقع گراف های کامل حداکثر تعداد یال ها را در مرتبه ی خود دارند و دیگر نمی توانیم به آن ها یال اضافه کنیم.

در جدول زیر گراف های کامل تا مرتبه 5 را مشاهده کنید:

مکمل گراف

مکمل گراف G که آن را با \({G^c}\) یا \(\bar G\) نشان می دهیم، گرافی است که مجموعه راس های آن همان مجموعه ی راس ها است و دو راس در \(\bar G\) مجاورند اگر در G مجاور نباشند. برای مثال در شکل زیر یک گراف کامل و مکمل آن را می بینید:

زیر گراف

گراف H را یک زیر گراف از G می گوییم هر گاه \(E(H) \subseteq E(G),V(H) \subseteq V(G)\)

برای مثال گراف G و سه زیر گراف آن را در زیر مشاهده می کنید:

فرض کنیم u و v دو راس از گراف G باشند. یک مسیر از u به v در G دنباله ای متشکل از راس های دو به دو متمایز است که از u شروع و به v ختم می شود به طوری که هر دو راس متوالی در این مسیر، مجاور هستند. طول مسیر همان تعداد یال های طی شده است که یکی کمتر از تعداد راس ها است.

قرارداد

هر راس به تنهایی، یک مسیر به طول صفر از خودش به خودش است.

گرافی که تنها از یک مسیر n راسی تشکیل شده باشد با \({P_n}\) نمایش می دهیم.

گراف های همبند

گراف G را همبند گوییم، هر گاه بین هر دو راس آن حداقل یک مسیر وجود داشته باشد، مانند گراف زیر:

گرافی که همبند نباشد را ناهمبند می نامیم. مانند گراف های زیر:

دور در گراف

یک دور به طول m در گراف G دنباله ای از \(m + 1\) راس، که راس های متوالی مجاور بوده و m راس اول آن دو به دو متمایز بوده و راس آخر همان راس اول باشد. در شکل زیر دور \({v_1}{v_2}{v_3}{v_4}{v_1}\) را ببینید. این دور به طول 4 است.

گرافی را که تنها از یک دور n راسی تشکیل شده باشد با \({C_n}\) نمایش می دهیم.

برای مثال \({C_5}\) را در شکل زیر می بینید:

اصل ضرب

اگر کاری در مرحله اول به 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\)) کبوتر در آن قرار گرفته است.