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

ش

پیش از این در مقاله فرمول تعداد زیرمجموعه های یک مجموعه به بحث و ارائه مثال در رابطه با تعداد زیر مجموعه های یک مجموعه و فرمول آن پرداختیم. جمع بندی اینکه بدست آوردن تعداد زیرمجموعه های یک مجموعه آسان است و کافیست ۲ را به توان تعداد اعضای مجموعه برسانیم، به عنوان مثال اگر یک مجموعه ۵ عضو داشته باشد، ۲ به توان ۵ برابر با ۳۲ می شود. در ادامه به اثبات فرمول تعداد زیرمجموعه های یک مجموعه می پردازیم. دو اثبات برای این موضوع ارائه داده می شود که یکی از آنها ساده تر می باشد. فرض می کنیم که تعداد کل اعضای مجموعه برابر با 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 تعداد اعضای زیرمجموعه است) می باشد. 

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

    • مدیرسایت میگوید:

      سلام، از نظر مفهومی این جوری می تونید در نظر بگیرید که یک زیرمجموعه شامل چند عضو است مثلا a, b, c پس می گوییم این زیرمجموعه شامل عضوی به نام a “و” عضوی به نام b “و” عضوی به نام c است. پس اینجا عملگر “و” یا همون And ایفای نقش می کند، پس برای شمارش حالات از ضرب استفاده می شود، چرا که هر عضو در یک زیر مجموعه می تواند به دو حالت ایفای نقش کند: یا حضور داشته باشد (۰) و یا حضور نداشته باشد (۱)، اگر باز ابهام تون برطرف نشد لطفا اعلام بفرمایید که دوباره روش صحبت کنیم، موفق باشید

  1. ع میگوید:

    سلام
    ممنون از مقاله مفیدتون
    میخواستم بدونم چرا مجموعه nعضوی هم در محاسبه تعداد بعنوان یک زیر مجموعه خودش حساب میشه

    • مدیرسایت میگوید:

      با سلام
      کلا وقتی که می خواهیم یک زیرمجموعه تشکیل بدیم باید در مورد تک تک اعضای مجموعه اصلی تصمیم بگیریم که آیا آن عضو در زیرمجموعه ما حضور دارد یا ندارد. برای سادگی فرض کنید که وارد یک فروشگاه شدید که ۱۰ کالا در جلوی شما قرار دارد و شما می توانید هرکدام از آنها را در درون سبد خرید بگذرید یا نگذارید. پس شما تک تک کالاها را بررسی می کنید و تصمیم می گیرید که آن کالا را داخل سبد خرید خودتون قرار بدید یا نه، یکی از حالات ممکن هم این است که تمامی ۱۰ کالا را بپسندید و داخل سبد خریدتون بگذارید، در رابطه با تشکیل یک زیرمجموعه از یک مجموعه هم دقیقا همین موضوع صادق است. به جای کل کالاهای موجود در فروشگاه، مجموعه اصلی و به جای زیرمجموعه سبد خرید خود را در نظر بگیرید.

    • مدیرسایت میگوید:

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

    • مدیرسایت میگوید:

      سلام آقای مهرداد گرامی
      فکر کنم به اشتباه اینجا این نظر را فرمودید. یا مطلب دیگری مد نظرتان بوده یا اینکه کامنت مربوط به مقاله دیگری هست
      در هر صورت از شما سپاسگزاریم

  2. ... میگوید:

    چقدر خوب برای هر سوال با مثال های مختلف توضیح میدین
    و هر ابهامی رو رفع میکنین
    مرسی🤗 دمتونم گرم
    کاش شما معلم ریاضیمون بودید

  3. یسنا میگوید:

    سلام . خسته نباشید . اگه به ما اعداد زیر مجموعه را بدهند و تعداد عضو های یک مجموعه را بخواهند باید چیکار کنیم؟

    • مدیرسایت میگوید:

      سلام باید از تعداد زیرمجموعه ها لگاریتم در پایه ۲ گرفته شود. مثلا اگر تعداد زیرمجموعه ها ۱۶ باشد تعداد اعضا برابر با ۴ می گردد.

  4. پریسا میگوید:

    سلام متشکرم که وقت می گذارید اگر امکان دارد جواب سوال مرا هم توضیح دهید
    مجموعه {۱,۲,۳,۰۰۰,۴۹,۵۰} چند زیر مجموعه داردکه ۵۰بزرگترین عضو هر یک از آن زیر مجموعه ها باشد؟

    • مدیرسایت میگوید:

      با سلام خواهش می کنم
      برای پاسخ به این سوال شما باید زیرمجموعه های مورد نظر را در دو قسمت در نظر بگیرید. قسمت اول قسمت فیکس و ثابت این زیرمجموعه است که طبق صورت مسئله شما عدد ۵۰ می باشد یعنی تمامی زیرمجموعه‌ها حتماً بایستی شامل عدد ۵۰ باشند. قسمت دوم قسمت متغیر این زیر مجموعه است که می تواند تعدادی از اعداد از یک تا ۴۹ را در بر بگیرد که این موضوع کاملاً اختیاری هست و الزامی به این موضوع نیست که حتماً اعداد مشخصی را از مجموع اعداد از یک تا ۴۹ در بر داشته باشد. پس شما بایستی در نظر بگیرید که چه تعداد زیر مجموعه از مجموعه اعداد از یک تا ۴۹ می توانید انتخاب نمایید که می دانیم که تعداد این زیرمجموعه ها برابر میشود با ۲ به توان ۴۹. پس پاسخ شما برابر میشود با تعداد زیر مجموعه های مجموعه اعداد از یک تا ۴۹ که برابر است با ۲ به توان ۴۹
      امیدوارم که پاسخ برای شما مفید بوده باشد و در درس خود موفق و پیروز و سربلند باشید

  5. یه سمپادی میگوید:

    سلام خیلی ممنون از توضیح فقط اینکه هیچ فرمولی وجود ندارد که مثالا بگه تعداد سه عضوی مجموعه {۱,۲,۳,۴,۵}چیه ؟

  6. بی نام میگوید:

    سلام خیلی ممنون از توضیح فقط اینکه هیچ فرمولی وجود ندارد که مثالا بگه تعداد سه عضوی مجموعه {۱,۲,۳,۴,۵}چیه ؟

    • مدیرسایت میگوید:

      سلام به دوست سمپادی گرامی
      در رابطه با تعداد زیر مجموعه های سه عضوی یک مقاله مستقل در سایت نگرش هوشمند با عنوان «تعداد زیرمجموعه های سه عضوی یک مجموعه» داریم که فرمول دقیق و مثال ها در این مقاله ذکر شده است. سوال شما نیز به عنوان مثال شماره ۲ به این مقاله اضافه شد و هم اکنون می توانید مقاله و پاسخ سوال خود را در لینک فوق مطالعه نمایید.
      هر سوال دیگری در رابطه با این مبحث یا سایر مطالب و مقالات سایت میتونید مطرح نمایید تا توسط تیم نگرش هوشمند بررسی و پاسخ شما آماده و ارسال شود.

دیدگاهتان را بنویسید

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