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

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

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

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

حال فرض کنیم ۳ مجموعه‌ی $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|$$ سعی کنید با استفاده از شکل زیر، عبارت بالا را بهتر درک کنید:

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

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

به صورت فشرده‌تر، اصل شمول و عدم شمول را می‌توان به صورت زیر هم بیان کرد: $$|A_1 \cup A_2 \cup ... \cup A_n| = \sum_{i=1}^{n}(-1)^{i+1}(\sum_{1\le j_1 < j_2 < ... < j_i \le n}|A_{j_1} \cap A_{j_2} \cap ... \cap A_{j_i}|)$$

مثال:

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

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

می‌خواهیم تعداد پریش‌های $n$ عنصره را بیابیم. زیرمجموعه‌های $A_1, A_2, ..., A_n$ از تمام جایگشت‌های خطی $n$ عنصره را به این صورت تعریف می‌کنیم که $A_i$، شامل جایگشت‌هایی است که عنصر $i$-ام سر جای خودش باشد. در واقع ما باید $n!-|A_1 \cup A_2 \cup ... \cup A_n|$ را پیدا کنیم.

ابتدا با اصل شمول و عدم شمول، مقدار $S=|A_1 \cup A_2 \cap ... \cup A_n|$ را می‌یابیم. $$ S = \sum_{1\le i\le n}|A_i| - \sum_{1\le i < j \le n}|A_i \cap A_j| + \sum_{1\le i < j < k \le n}|A_i \cap A_j \cap A_k| - ... + (-1)^{n-1}|A_1 \cap A_2 \cap ... \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| - ... + (-1)^{n-1}\binom{n}{n} |A_1 \cap A_2 \cap ... \cap A_n|$$ حال بیابید به ازای یک $k$، مقدار $|A_1 \cap A_2 \cap ... \cap A_k|$ را محاسبه کنیم. به وضوح باید عناصر $1, 2, ..., k$ سر جای خود باشند و بقیه یک جایگشت $(n-k)$-عنصره هستند که $(n-k)!$ حالت دارند. پس داریم: $$ S = \binom{n}{1} \times (n-1)! - \binom{n}{2} \times (n-2)! + ... + (-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!}+...+(-1)^{n-1}\frac{n!}{n!}$$ پس پاسخ برابر است با: $$ n! - S = \frac{n!}{0!} - S = \frac{n!}{0!} - \frac{n!}{1!} + ...+(-1)^{n}\frac{n!}{n!} $$ پس: $$D_n = n! (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ... + (-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, ..., 10$ وجود دارد که عدد ۹ در مکان ۱۰-ام جایگشت آمده باشد؟

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

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

فرض کنید تجزیه‌ی $n$ به عوامل اول، به صورت $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ باشد. می‌خواهیم فرمولی برای $\varphi(n)$ بر حسب $p_i$ها (عوامل اول $n$) بیابیم. مجموعه‌های $A_1, A_2, ..., A_n$ را به این صورت تعریف می‌کنیم که $A_i$، شامل اعدادی از $M$ است که بر $P_i$ بخش‌پذیر هستند. داریم: $$ \varphi(n) = n - |A_1 \cup A_2 \cup ... \cup A_n| $$ طبق اصل شمول و عدم شمول داریم: $$ \varphi(n) = n - (\sum_{1\le i\le n}|A_i| - \sum_{1\le i < j \le n}|A_i \cap A_j| + \sum_{1\le i < j < k \le n}|A_i \cap A_j \cap A_k| - ... + (-1)^{n-1}|A_1 \cap A_2 \cap ... \cap A_n|) $$

از طرفی، طبق مثال‌های ذکر شده، مقدار $|A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}|$ برابر $\lfloor \frac{n}{p_{i_1}p_{i_2}...p_{i_k}} \rfloor$ است. از آن‌جایی که تمام $p_j$ها عامل اول $n$ هستند، پس مقدار داخل $\lfloor \ \rfloor$ عددی طبیعی است. پس: $$ |A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}| = \frac{n}{p_{i_1}p_{i_2}...p_{i_k}} $$

پس داریم: $$ \varphi(n) = n - \sum_{i=1}^{n}\frac{n}{p_i} + \sum_{1\le i<j \le n} \frac{n}{p_i p_j} - ... + (-1)^{n-1}\frac{n}{p_1 p_2 ... p_k} $$

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

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

مجموعه‌های $S_1, S_2, ..., S_b$ را به این صورت تعریف می‌کنیم که $S_i$ شامل توابعی است که عضو $i$-ام $B$ پوشش داده نشده باشد (یعنی هیچ $x$-ای وجود نداشته باشد که $f(x)$ برابر عضو $i$-ام $B$ شود).

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

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

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

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

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