تعداد زیرمجموعه‌ های یک مجموعه

قضیه. تعداد زیرمجموعه‌های یک مجموعهٔ \(n\)عضوی برابر \(2^n\) است.

اثبات. ابتدا با چند مثال، روش اثبات را شرح می‌دهیم.
فرض کنید \(A=\{1,2,3,4,5,6,7\}\). یکی از زیرمجموعه‌های \(A\) را انتخاب می‌کنیم. برای مثال، \(M=\{1,3,6,7\}\). حالا می‌توان مجموعهٔ \(M\) را با یک کد نمایش دهیم:
\[\checkmark\times\checkmark\times\times\checkmark\checkmark\]

هریک از اعضای مجموعهٔ \(A\) و \(M\) را به‌ترتیب از کوچک به بزرگ در نظر بگیرید. اگر عضوی از \(M\) داخل \(A\) باشد، در آن جایگاه \(\checkmark\) می‌گذاریم و اگر نباشد \(\times\) می‌گذاریم:
\[\begin{matrix}&1&2&3&4&5&6&7\\\{1,3,6,7\}&\checkmark&\times&\checkmark&\times&\times&\checkmark&\checkmark\end{matrix}\]

همهٔ زیرمجموعه‌های مجموعهٔ \(A=\{1,2\}\) را با استفاده از کد بالا نمایش دهید.

\[\begin{matrix}&1&2\\\{\}&\times&\times\\\{1\}&\checkmark&\times\\\{2\}&\times&\checkmark\\\{1,2\}&\checkmark&\checkmark\\\end{matrix}\]

همهٔ زیرمجموعه‌های مجموعهٔ \(A=\{1,2,3\}\) را با استفاده از کد بالا نمایش دهید.

\[\begin{matrix}&1&2&3\\\{\}&\times&\times&\times\\\{1\}&\checkmark&\times&\times\\\{2\}&\times&\checkmark&\times\\\{3\}&\times&\times&\checkmark\\\{1,2\}&\checkmark&\checkmark&\times\\\{1,3\}&\checkmark&\times&\checkmark\\\{2,3\}&\times&\checkmark&\checkmark\\\{1,2,3\}&\checkmark&\checkmark&\checkmark\\\end{matrix}\]

به‌همین ترتیب می‌توان هریک از زیرمجموعه‌های یک مجموعهٔ \(n\)عضوی را با \(n\)تا \(\times\) یا \(\checkmark\) نمایش داد. در نتیجه، برای شمارش تعداد زیرمجموعه‌های یک مجموعهٔ \(n\)عضوی کافی است پاسخ مسئلهٔ زیر را بدانیم.

مسئله. به چند طریق می‌توان \(n\) جایگاه را با علامت‌های \(\times\) یا \(\checkmark\) پر کرد.
راه‌حل. چون برای پر کردن هر جایگاه، \(2\) حالت وجود دارد، پس تعداد کل‌ حالت‌ها برابر است با:
\[\underbrace{2\times2\times2\times\dots\times2}_{تاn}=2^n.\]

بنابراین، تعداد زیرمجموعه‌های یک مجموعهٔ \(n\)عضوی، برابر است با \(2^n\).