بنام خدا.قبل از اینکه مسئله را حل کنیم یک مثال می زنیم فرض کنیم $n=3$باشد 3عضومتمایز$A= \lbrace aوbوc\rbrace $ و3 عضو یکسان $B= \lbrace dوdوd \rbrace $ میخواهیم 3عضو از کل این 6 حروف که 3عضو متمایز و3 عضو دیگر تکراری است انتخاب کنیم مجموعه زیر را خواهیم داشت :
$ \lbrace abc-abd-acd-bcd-add-bdd-cdd-ddd\rbrace $ اگر به این مجموعه دقت کنیم abc یعنی 3 عضو انتخاب شده از مجموعه A وسه عضو بعدی یعنیabdوacdوbcd دوعضو از مجموعه A ویک عضو از مجموعه B وسه عضو انتخاب بعدی یعنی addوbddوcdd یک عضو از مجموعه A ودو عضو از مجموعه B وآخرین عضو ddd یعنی هیچ از مجموعه A وسه عضواز مجموعه B میباشدباز اگر دقت کنیم با نادیده گرفتن حرف d و به جای ddd عضو آخر تهی قرار دهیم $ \lbrace abc-ab-ac-bc-a-b-c- \Phi \rbrace $ تمام زیر مجموعه های A بدست می آید $ 2^{3} =8$
حال مسئله را در حالت کلی حل می کنیم اگر n شئ از یک مجموعه 2n شئ که n شئ متمایز وn شئ یکسان انتخاب کنیم تعدادحالاتی که از n شئ یکسان انتخاب میکنیم در هر حالت یک خواهد بود چون nشئ یکسان یک شئ متمایز در نظر گرفته می شودوانتخاب r شئ با تکرار از یک شئ متمایز مساوی یک است $ \binom{1+r-1}{r} =1$
بنابراین n شئ که انتخاب میکنیم یا همه از مجموعه A که تمام اعضای آن متمایزند یک حالت دارد $ \binom{n}{n} =1 $ یاهمه از مجموعه B که همه اعضای آن یکسان است وآن هم یک حالت دارد.در حالات دیگر تعدادی از مجموعه A وبقیه در مجموعه B خواهد بود حالاتی که از مجموعه B انتخاب میکنیم در هر مورد جواب یک است بنابر این داریم $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} +...+ \binom{n}{n} = 2^{n} $
یعنی تعداد زیر مجموعه های A میباشد.
