اثبات فرمول تعداد زیرمجموعه های یک مجموعه

ش

بدست آوردن تعداد زیرمجموعه های یک مجموعه آسان است کافیست ۲ را به توان تعداد اعضای مجموعه برسانیم، به عنوان مثال اگر یک مجموعه ۵ عضو داشته باشد، ۲ به توان ۵ برابر با ۳۲ می شود. در ادامه به اثبات فرمول تعداد زیرمجموعه های یک مجموعه می پردازیم. دو اثبات برای این موضوع ارائه داده می شود که یکی از آنها ساده تر می باشد. فرض می کنیم که تعداد کل اعضای مجموعه برابر با n باشد. 

اثبات اول برای فرمول تعداد زیرمجموعه های یک مجموعه (راه حل ساده)

این اثبات ساده است. کافیست وضعیت هریک از اعضای مجموعه در زیرمجموعه ها را مشخص نماییم. این گونه تصور کنیم که هریک از اعضای مجموعه n تایی یک لامپ می باشند که می توانند روشن یا خاموش باشند. در این حالت هر زیرمجموعه را می توان با یک رشته لامپ صفر و یک در نظر گرفت اگر لامپ مربوط به یک عضو خاموش باشد یعنی آن عضو در زیرمجموعه حضور ندارد و برعکس روشن بودن لامپ مربوط به یک عضو به معنای حضور آن در زیرمجموعه می باشد، مثلا مجموعه تهی مربوط به حالتی است که کلیه لامپ ها خاموش باشند، یا یک مجموعه دو عضوی حالتی است که فقط دو لامپ از n لامپ (n همان تعداد کل اعضای مجموعه است) روشن و بقیه خاموش باشند. حال باید ببینیم چند حالت برای تشکیل این رشته های n لامپی وجود دارد. از آنجاییکه هر لامپ دو وضعیت روشن و خاموش را دارد، تعداد کل رشته ها بر اساس ضرب و به صورت زیر بدست می آید که برابر با ۲ به توان n می شود:

1

اثبات دوم برای فرمول تعداد زیرمجموعه های یک مجموعه

برای اثبات بدین صورت می توانیم عمل نماییم که تعداد زیرمجموعه های تهی، ۱ عضوی، ۲ عضوی، ۳ عضوی و ….. تا n عضوی یک مجموعه را بدست آورده و آنها را با هم جمع نماییم. می دانیم که تعداد اعضای k عضوی یک مجموعه از فرمول زیر بدست می آید:

2

حال در فرمول فوق به جای k هریک از اعداد از صفر تا n را قرار می دهیم. پس داریم:

تعداد زیرمجموعه های تهی (صفر عضوی) برابر می شود با:

3

تعداد زیرمجموعه های ۱ عضوی برابر می شود با:

4

تعداد زیرمجموعه های ۲ عضوی برابر می شود با:

5

تعداد زیرمجموعه های ۳ عضوی برابر می شود با:

6

تعداد زیرمجموعه های n-1 عضوی برابر می شود با:

7

تعداد زیرمجموعه های n عضوی برابر می شود با:

8

پس در نهایت تعداد کل زیرمجموعه های یک مجموعه n عضوی برابر با جمع ترکیب های فوق می شود، پس تعداد کل زیرمجموعه ها به صورت زیر بدست می آید:

9

برای محاسبه جمع فوق از فرمول کلی بسط یک عبارت دو جمله ای استفاده می کنیم که به صورت زیر می باشد:

10

حال در صورتیکه در عبارت فوق به جای a و b عدد ۱ را قرار دهیم، عبارت فوق به صورت زیر در می آید:

11

پس ثابت می شود که جمع کل تعداد ترکیب های مختلف (تعداد زیرمجموعه ها) برابر با ۲ به توان n (که n تعداد اعضای زیرمجموعه است) می باشد.

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *