فهرست مندرجات

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

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

حالت ۲ مجموعه

ابتدا حالت ۲ مجموعه را در نظر بگیرید. اصل شمول و عدم شمول می‌گوید: $$|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, ..., 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\}$ که نه بر ۲، نه بر ۳، نه بر ۵ و نه بر ۷ بخش‌پذیرند، چندتاست؟

پاسخ

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

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

پریش‌ها

پریش از پریشانی می‌آید. یک جایگشت $<\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$ وجود دارد که عدد ۹ در مکان ۱۰-ام جایگشت آمده باشد؟

پاسخ

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

پاسخ

مجموعه‌های $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 = ... = A_n = \{1\}$ را در نظر بگیرید. طبق اصل شمول و عدم شمول داریم: $$|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_i|$-ها یک عضوی است، داریم: $$ 1 = \binom{n}{1} - \binom{n}{2} + ... + (-1)^n \binom{n}{n} $$ با قرار دادن $\binom{n}{0}$ به جای ۱ و بردن تمام جملات به سمت چپ داریم: $$ \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ... + (-1)^n \binom{n}{n} = 0 $$ پس: $$\sum_{r=0}^{n}(-1)^r \binom{n}{r}=0$$ پس حکم ثابت شد.

مسائل نمونه