اصل شمول و عدم شمول

اصل شمول و عدم شمول در ترکیبیات شمارشی، تعداد اعضای اجتماع چند مجموعه را محاسبه می‌کند. این اصل کاربردهای بسیاری دارد که برخی از آن‌ها در این صفجه ذکر شده است. استفاده از این اصل را در احتمال، گراف، الگوریتم و بسیاری از مسائل شمارشی از جمله اتحادهای ترکیبیاتی، خواهید دید.

حالت ۲ مجموعه

ابتدا حالت ۲ مجموعه را در نظر بگیرید. اصل شمول و عدم شمول می‌گوید: $| A \cup B | = | A | + | B | - | A \cap B |$ با کشیدن نمودار ون، بیش‌تر می‌توانید عبارت بالا را درک کنید.

مثال: در یک مدرسه، ۲۳ نفر در تیم فوتبال و ۱۲ نفر در تیم والیبال عضو هستند. ۴ نفر نیز در هر دو تیم عضو هستند. چند نفر از دانش‌آموزان مدرسه، در دست کم یکی از ۲ تیم ورزشی مدرسه هستند؟

پاسخ

اگر $A$ و $B$ را به ترتیب، مجموعه‌ی دانش‌آموزان عضو در تیم فوتبال و والیبال در نظر بگیریم، طبق اصل شمول و عدم شمول، پاسخ ما $23 + 12 - 4 = 41$ خواهد بود.

حالت ۳ مجموعه

حال فرض کنیم ۳ مجموعه‌ی $A, B, C$ داریم و می‌خواهیم $| A \cup B \cup C |$ را محاسبه کنیم. اصل شمول و عدم شمول می‌گوید: $| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | B \cap C | - | C \cap A | + | A \cap B \cap C |$ سعی کنید با استفاده از شکل زیر، عبارت بالا را بهتر درک کنید:

مثال: در یک مدرسه، ۱۲ فوتبالیست، ۱۶ والیبالیست و ۸ تیرانداز وجود دارد. ۴ نفر هم فوتبالیست و هم والیبالیست هستند. ۳ نفر هم فوتبالیست و هم تیرانداز هستند. ۱ نفر در هر ۳ ورزش فعالیت می‌کند و در مجموع کسانی که ورزش می‌کنند، ۴۰ نفر هستند. چند نفر در این مدرسه، هم والیبالیست و هم تیرانداز هستند؟

پاسخ

اگر $A$ و $B$ و $C$ را به ترتیب مجموعه‌ی فوتبالیست‌ها، والیبالیست‌ها و تیراندازهای مدرسه در نظر بگیریم، در واقع باید $| B \cap C$ را پیدا کنیم. طبق اصل شمول و عدم شمول داریم: $40 = 12 + 16 + 8 - 4 - 3 - | B \cap C | + 1$ پس پاسخ برابر ۲ است.

حالت کلی

در حالت کلی اگر $n$ مجموعه‌ی، $A_{1}, A_{2}, \dots, A_{n}$ را داشته باشیم، اصل شمول و عدم شمول برای محاسبه‌ی $| A_{1} \cup A_{2} \cup \dots \cup A_{n} |$ می‌گوید: $| A_{1} \cup A_{2} \cup \dots \cup A_{n} | = \sum_{1 \leq i \leq n} | A_{i} | - \sum_{1 \leq i < j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + (- 1)^{n - 1} | A_{1} \cap A_{2} \cap \dots \cap A_{n} |$ در واقع عبارت بالا به صورت خودمانی می‌گوید که ابتدا باید جمع تعداد اعضای تک تک مجموعه‌ها را حساب کنیم؛ سپس آن را منهای تعداد اعضای اشتراک‌های دو به دوی مجموعه‌ها کنیم؛ سپس آن را با تعداد اعضای اشتراک‌های ۳-تایی مجموعه‌ها جمع کنیم و همین طور ادامه دهیم.

به صورت فشرده‌تر، اصل شمول و عدم شمول را می‌توان به صورت زیر هم بیان کرد: $| A_{1} \cup A_{2} \cup \dots \cup A_{n} | = \sum_{i = 1}^{n} (- 1)^{i + 1} (\sum_{1 \leq j_{1} < j_{2} < \dots < j_{i} \leq n} | A_{j_{1}} \cap A_{j_{2}} \cap \dots \cap A_{j_{i}} |)$

مثال:

ثابت کنید تعداد اعضایی از مجموعه‌ی ${1, 2, \dots, n}$ که بر عدد طبیعی $k$ بخش‌پذیر هستند، برابر $⌊ \frac{n}{k} ⌋$ است.
تعداد اعداد طبیعی مجموعه‌ی $M = {1, 2, \dots, 1000}$ که نه بر ۲، نه بر ۳، نه بر ۵ و نه بر ۷ بخش‌پذیرند، چندتاست؟

پاسخ

قسمت اول: اعدادی که بر $k$ بخش‌پذیر هستند، به صورت $c k$ هستند. باید $1 \leq c k \leq n$ باشد. پس داریم $\frac{1}{k} \leq c \leq \frac{n}{k}$ . از آن‌جایی که $c$ نیز عددی طبیعی است، پس داریم $1 \leq c \leq ⌊ \frac{n}{k} ⌋$ . پس $c$ ، $⌊ \frac{n}{k} ⌋$ حالت دارد.

قسمت دوم: اگر $A$ و $B$ و $C$ و $D$ را به ترتیب، تعداد اعدادی از $M$ بگیریم که بر ۲، بر ۳، بر ۵ و بر ۷ بخش‌پذیر هستند، ما باید $| (A \cup B)^{'} |$ را بیابیم. طبق اصل شمول و عدم شمول، پاسخ برابر است با: $| M | - | A \cup B |$ $= 1000 - (⌊ \frac{1000}{2} ⌋ + \dots ⌊ \frac{1000}{7} ⌋ - ⌊ \frac{1000}{2 \times 3} ⌋ - \dots ⌊ \frac{1000}{5 \times 7} ⌋ + ⌊ \frac{1000}{2 \times 3 \times 5} ⌋ + \dots ⌊ \frac{1000}{3 \times 5 \times 7} ⌋ - ⌊ \frac{1000}{2 \times 3 \times 5 \times 7} ⌋)$ $= 1000 - 500 - 333 - 200 - 142 + 166 + 100 + 71 + 66 + 47 + 28 - 33 - 23 - 14 - 9 + 4 = 251$

پریش‌ها

پریش از پریشانی می‌آید. یک جایگشت $< π_{1}, π_{2}, \dots, π_{n} >$ از اعداد $1, 2, \dots, n$ را پریش (پریشان) می‌گوییم، هرگاه هیچ $i$ -ای وجود نداشته باشد که $π_{i} = i$ باشد. در واقع هیچ کس سر جای خودش نیست. مثلن جایگشت $< 2, 3, 4, 1 >$ یک پریش است. تعداد پریش‌های $n$ -عنصره را با $D_{n}$ نشان می‌دهیم؛ هر چند در برخی از منابع، آن را $! n$ نیز نمایش داده‌اند.

می‌خواهیم تعداد پریش‌های $n$ عنصره را بیابیم. زیرمجموعه‌های $A_{1}, A_{2}, \dots, A_{n}$ از تمام جایگشت‌های خطی $n$ عنصره را به این صورت تعریف می‌کنیم که $A_{i}$ ، شامل جایگشت‌هایی است که عنصر $i$ -ام سر جای خودش باشد. در واقع ما باید $n! - | A_{1} \cup A_{2} \cup \dots \cup A_{n} |$ را پیدا کنیم.

ابتدا با اصل شمول و عدم شمول، مقدار $S = | A_{1} \cup A_{2} \cap \dots \cup A_{n} |$ را می‌یابیم. $S = \sum_{1 \leq i \leq n} | A_{i} | - \sum_{1 \leq i < j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + (- 1)^{n - 1} | A_{1} \cap A_{2} \cap \dots \cap A_{n} |$ از طرفی می‌دانیم هر یک از $\sum$ های بالا، شامل تعدادی جمله‌ی برابر هستند؛ زیرا $A_{i}$ -ها تقارن دارند. پس داریم: $S = n \times | A_{1} | - (\binom{n}{2}) | A_{1} \cap A_{2} | + (\binom{n}{3}) | A_{1} \cap A_{2} \cap A_{3} | - \dots + (- 1)^{n - 1} (\binom{n}{n}) | A_{1} \cap A_{2} \cap \dots \cap A_{n} |$ حال بیابید به ازای یک $k$ ، مقدار $| A_{1} \cap A_{2} \cap \dots \cap A_{k} |$ را محاسبه کنیم. به وضوح باید عناصر $1, 2, \dots, k$ سر جای خود باشند و بقیه‌یک جایگشت $(n - k)$ -عنصره هستند که $(n - k)!$ حالت دارند. پس داریم: $S = (\binom{n}{1}) \times (n - 1)! - (\binom{n}{2}) \times (n - 2)! + \dots + (- 1)^{n - 1} (\binom{n}{n}) \times 0!$ از طرفی داریم: $(\binom{n}{k}) \times (n - k)! = \frac{n!}{k! (n - k)!} \times (n - k)! = \frac{n!}{k!}$ پس داریم: $S = \frac{n!}{1!} - \frac{n!}{2!} + \dots + (- 1)^{n - 1} \frac{n!}{n!}$ پس پاسخ برابر است با: $n! - S = \frac{n!}{0!} - S = \frac{n!}{0!} - \frac{n!}{1!} + \dots + (- 1)^{n} \frac{n!}{n!}$ پس: $D_{n} = n! (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \dots + (- 1)^{n} \frac{1}{n!})$

یک نکته: اگر چنان‌چه مفهوم حد در بی‌نهایت و بسط تیلور $e^{x}$ ( $e$ همان عدد نپر است که حدود $2.71$ می‌باشد) را بدانید، با بردن $n$ به سمت $\infty$ و قرار دادن $x = - 1$ ، $D_{n}$ به $\frac{n!}{e}$ میل می‌کند و این نتیجه می‌دهد اگر $n$ به حد کافی زیاد باشد (از حدود $n = 10$ به بعد این را خواهید دید)، از حدود هر ۳ جایگشت تصادفی، انتظار می‌رود حدود یکی از آن‌ها پریش باشد! در شکل زیر می‌توانید رشد تعداد پریش‌ها را با رشد تعداد کل جایگشت‌ها، با بالا رفتن $n$ ، مقایسه کنید:

مثال: چند پریش از اعداد $1, 2, \dots, 10$ وجود دارد که عدد ۹ در مکان ۱۰-ام جایگشت آمده باشد؟

پاسخ

در یک پریش، مکان عدد ۹ هر جایی جز مکان ۹-ام می‌تواند باشد؛ پس ۹ حالت دارد و طبق تقارن، این ۹ حالت تفاوتی با هم ندارند. پس پاسخ برابر $\frac{D_{10}}{9}$ است که $D_{10}$ از فرمول بالا به دست می‌آید.

در بخش روابط بازگشتی، بیش‌تر در مورد پریش‌ها بحث خواهد شد.

تابع فی اویلر

تعداد اعداد $M = {1, 2, \dots, n}$ که نسبت به $n$ اول هستند را $φ (n)$ می‌نامیم. این تابع را فی اویلر می‌گویند. برای مثال $φ (4) = 2$ زیرا ۱ و ۳ نسبت به ۴، اول هستند.

فرض کنید تجزیه‌ی $n$ به عوامل اول، به صورت $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ باشد. می‌خواهیم فرمولی برای $φ (n)$ بر حسب $p_{i}$ ها (عوامل اول $n$ ) بیابیم. مجموعه‌های $A_{1}, A_{2}, \dots, A_{n}$ را به این صورت تعریف می‌کنیم که $A_{i}$ ، شامل اعدادی از $M$ است که بر $P_{i}$ بخش‌پذیر هستند. داریم: $φ (n) = n - | A_{1} \cup A_{2} \cup \dots \cup A_{n} |$ طبق اصل شمول و عدم شمول داریم: $φ (n) = n - (\sum_{1 \leq i \leq n} | A_{i} | - \sum_{1 \leq i < j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + (- 1)^{n - 1} | A_{1} \cap A_{2} \cap \dots \cap A_{n} |)$

از طرفی، طبق مثال‌های ذکر شده، مقدار $| A_{i_{1}} \cap A_{i_{2}} \cap \dots \cap A_{i_{k}} |$ برابر $⌊ \frac{n}{p_{i_{1}} p_{i_{2}} \dots p_{i_{k}}} ⌋$ است. از آن‌جایی که تمام $p_{j}$ ها عامل اول $n$ هستند، پس مقدار داخل $⌊ ⌋$ عددی طبیعی است. پس: $| A_{i_{1}} \cap A_{i_{2}} \cap \dots \cap A_{i_{k}} | = \frac{n}{p_{i_{1}} p_{i_{2}} \dots p_{i_{k}}}$

پس داریم: $φ (n) = n - \sum_{i = 1}^{n} \frac{n}{p_{i}} + \sum_{1 \leq i < j \leq n} \frac{n}{p_{i} p_{j}} - \dots + (- 1)^{n - 1} \frac{n}{p_{1} p_{2} \dots p_{k}}$

از طرفی با بسط دادن عبارت $n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{k}})$ مقدار بالا به دست می‌آید. پس داریم: $φ (n) = n \times \prod_{i = 1}^{k} (1 - \frac{1}{p_{i}})$ برای مثال، با استفاده از فرمول، مقدار $φ (4)$ برابر $4 \times (1 - \frac{1}{2})$ به دست می‌آید که برابر ۲ است (همان مقداری که به دست آورده بودیم).

تعداد توابع پوشا

فرض کنید مجموعه‌های $A$ و $B$ به ترتیب $a$ و $b$ عضو داشته باشند. می‌خواهیم تعداد توابع پوشای $f : A \to B$ را بیابیم.

مجموعه‌های $S_{1}, S_{2}, \dots, S_{b}$ را به این صورت تعریف می‌کنیم که $S_{i}$ شامل توابعی است که عضو $i$ -ام $B$ پوشش داده نشده باشد (یعنی هیچ $x$ -ای وجود نداشته باشد که $f (x)$ برابر عضو $i$ -ام $B$ شود).

ابتدا مقدار $| S_{i_{1}} \cap S_{i_{2}} \cap \dots \cap S_{i_{k}} |$ را به ازای $1 \leq i_{1} < i_{2} < \dots < i_{k} \leq b$ حساب می‌کنیم. تابع ما باید عضوهای $i_{1}$ -ام، $i_{2}$ -ام، … و $i_{k}$ -ام از $B$ را پوشش ندهد. پس برای هر عضو $A$ مانند $x$ ، مقدار $f (x)$ ، $b - k$ حالت دارد. پس تعداد حالات مطلوب، $(b - k)^{a}$ است.

اگر تعداد کل توابع $f : A \to B$ را با $M$ نشان دهیم، پاسخ طبق اصل شمول و عدم شمول برابر است با: $M - | S_{1} \cup S_{2} \cup \dots \cup S_{b} |$ $= b^{a} - (\sum_{i = 1}^{b} | S_{i} | - \sum_{1 \leq i < j \leq b} | S_{i} \cap S_{j} | + \dots + (- 1)^{b - 1} | S_{1} \cap S_{2} \cap \dots \cap S_{b} |)$ $= (\binom{b}{0}) b^{a} - (\binom{b}{1}) (b - 1)^{a} + (\binom{b}{2}) (b - 2)^{a} - \dots + (- 1)^{b} (\binom{b}{b}) (b - b)^{a}$ $= \sum_{i = 0}^{b} (- 1)^{i} (\binom{b}{i}) (b - i)^{a}$

سایر مثال‌ها

مثال: به چند طریق می‌توان ۱۰ خانه از یک جدول $3 \times 20$ را علامت زد؛ طوری که در هر سطر، حداقل یک خانه، علامت زده شده باشد؟

پاسخ

مجموعه‌های $A_{1}, A_{2}, A_{3}$ را به این صورت تعریف می‌کنیم که $A_{i}$ شامل حالاتی است که سطر $i$ -ام، خانه‌ی علامت زده نداشته باشد. طبق اصل شمول و عدم شمول برای حالت ۳ مجموعه، داریم: $S = | A_{1} \cup A_{2} \cup A_{3} | = | A_{1} | + | A_{2} | + | A_{3} | - | A_{1} \cap A_{2} | - | A_{2} \cap A_{3} | - | A_{3} \cap A_{1} | + | A_{1} \cap A_{2} \cap A_{3} |$ با توجه به این‌که $A_{i}$ ها از نظر تعداد شبیه هم هستند و تقارن دارند، داریم: $S = 3 | A_{1} | - 3 | A_{1} \cap A_{2} | + | A_{1} \cap A_{2} \cap A_{3} |$ از طرفی، $| A_{1} | = (\binom{40}{10})$ ، $| A_{1} \cap A_{2} | = (\binom{20}{10}) = 1 |$ و $| A_{1} \cap A_{2} \cap A_{3} | = 0$ . پس: $S = 3 (\binom{40}{10}) - 3 (\binom{20}{10})$ اگر $M$ تعداد کل حالات قرار دادن مهره‌ها در جدول باشد، پاسخ برابر است با: $| (A_{1} \cup A_{2} \cup A_{3})^{'} | = M - S = (\binom{60}{10}) - 3 (\binom{40}{10}) + 3 (\binom{20}{10})$

مثال: با استفاده از اصل شمول و عدم شمول ثابت کنید: $\sum_{r = 0}^{n} (- 1)^{r} (\binom{n}{r}) = 0$

پاسخ

مجموعه‌های $A_{1} = A_{2} = \dots = A_{n} = {1}$ را در نظر بگیرید. طبق اصل شمول و عدم شمول داریم: $| A_{1} \cup A_{2} \cup \dots \cup A_{n} | = \sum_{1 \leq i \leq n} | A_{i} | - \sum_{1 \leq i < j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + (- 1)^{n - 1} | A_{1} \cap A_{2} \cap \dots \cap A_{n} |$ از آن‌جایی که اشتراک و اجتماع هر چندتا از $| A_{i} |$ -ها یک عضوی است، داریم: $1 = (\binom{n}{1}) - (\binom{n}{2}) + \dots + (- 1)^{n} (\binom{n}{n})$ با قرار دادن $(\binom{n}{0})$ به جای ۱ و بردن تمام جملات به سمت چپ داریم: $(\binom{n}{0}) - (\binom{n}{1}) + (\binom{n}{2}) - \dots + (- 1)^{n} (\binom{n}{n}) = 0$ پس: $\sum_{r = 0}^{n} (- 1)^{r} (\binom{n}{r}) = 0$ پس حکم ثابت شد.

مسائل نمونه

سوال ۲ مرحله اول دوره ۵

اُپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

اصل شمول و عدم شمول

حالت ۲ مجموعه

حالت ۳ مجموعه

حالت کلی

پریش‌ها

تابع فی اویلر

تعداد توابع پوشا

سایر مثال‌ها

مسائل نمونه

ابزار صفحه

ابزار کاربر

اصل شمول و عدم شمول

حالت ۲ مجموعه

حالت ۳ مجموعه

حالت کلی

پریش‌ها

تابع فی اویلر

تعداد توابع پوشا

سایر مثال‌ها

مسائل نمونه