چرا تعداد زیر مجموعه های زوج عضوی - و فرد عضوی - هر مجموعه برابر است با نصف تعداد کل زیر مجموعه ها؟

Question

گزارهٔ زیر را در نظر بگیرید.

تعداد زیرمجموعه‌های زوج عضوی - و فرد عضوی - هر مجموعه برابر است با $ 2^{n-1} $.

می‌دانم که این قضیه با استقرای ریاضی به سادگی اثبات می‌شود. اما بنده به دنبال اثبات‌های متفاوت هستم. همچنین این قضیه با اصل دوسویگی هم قابل اثبات است. به نظر من باید بتوان با نوشتن جمع تعداد زیرمجموعه‌های $2k$ عضوی ($2k+1$ عضوی) به عدد $2^{n-1}$ رسید. یعنی

$$\binom{n}{0}+ \binom{n}{2}+\binom{n}{4}+ ... + \binom{n}{2[ \frac{n}{2} ]} = \binom{n}{1}+ \binom{n}{3}+\binom{n}{5}+ ... + \binom{n}{2[ \frac{n}{2} ]-1}= 2^{n-1}$$

اما چگونه باید این فرمول را ثابت کنم؟

Comments

در بسط خیام $ (x+y)^{n} $ قرار بدید x=-1 , y=1

---

x=-1 , y=1 از کجا می یان و نشان دهنده چیه؟

---

ممنون از راهنماییتون.
حذف شد

---

@rafig256 همان عبارتی که در انتهای متن پرسش‌تان را نوشتید بدون $=2^{n-1}$ را نگاه کنید. هر دو عبارت را به یک طرف بیاورید. منفی یک به توان $i$ها درست می‌شود و یک هم که به هر توانی یک می‌شود پس چرا $n-i$ نگذارید؟ سپس به همان دیدگاه @kazomano نمی‌رسید؟ گزینش $x$ و $y$ از همین چند محاسبهٔ ساده می‌آیند و نشأت می‌گیرند. و خود $2^{n-1}$ هم که بدیهی است. جمع دو چیز برابر شده‌است $2^n$ پس تک تک $2^{n-1}$ بوده‌اند.

Answer 1

یک روش ساده دیگه ایهم که هست اینه ما میایم عضو اول رو کنار میزاریم
و بقیه عضو ها دو حالت دارند یا باشند یا نباشند که میشه 2^{n-1}
حالا اگه ما زوج عضوی بخوایم و زیر مجموعه انتخاب شدمون فرد عضو داشته باشه برا اون عدده که کنار گزاشتیم یک حالت وجود داره که باشه یا بالعکسش ما زوج عضوی داریم و زوج عضوی میخوایم یه حالت وجود داره که نباشه

Answer 2

این مسئله به ترکیبیات اشاره دارد. برای یافتن تعداد زیر مجموعه های زوج عضوی و فرد عضوی، می توانیم به صورت زیر عمل کنیم:

فرض کنید مجموعه ما$ n$ عضو داشته باشد. حال برای هر عضو، دو گزینه وجود دارد: یا در زیر مجموعه حضور دارد یا ندارد. بنابراین برای هر عضو، دو حالت وجود دارد. پس تعداد کل زیر مجموعه ها برابر است با $2×2×2....=2^n$

حال برای یافتن تعداد زیر مجموعه های زوج عضوی، می توانیم به این صورت عمل کنیم: ابتدا یک عضو را به عنوان "اولین عضو" انتخاب می کنیم. حال برای هر عضو دیگر، دو گزینه وجود دارد: یا در زیر مجموعه حضور دارد یا ندارد. بنابراین برای هر عضو دیگر، دو حالت وجود دارد. اما برای اینکه زیر مجموعه زوج عضوی باشد، باید تعداد عضوهای حضور دار در زیر مجموعه فرد باشد. بنابراین برای هر عضو دیگر، تنها یک حالت وجود دارد. پس تعداد زیر مجموعه های زوج عضوی برابر است با

$2^{(n-1)}$

حال برای یافتن تعداد زیر مجموعه های فرد عضوی، می توانیم به همین روش عمل کنیم: ابتدا یک عضو را به عنوان "اولین عضو" انتخاب می کنیم. حال برای هر عضو دیگر، دو گزینه وجود دارد: یا در زیر مجموعه حضور دارد یا ندارد. بنابراین برای هر عضو دیگر، دو حالت وجود دارد. اما برای اینکه زیر مجموعه فرد عضوی باشد، باید تعداد عضوهای حضور دار در زیر مجموعه زوج باشد. بنابراین برای هر عضو دیگر، نیز تنها یک حالت وجود دارد. پس تعداد زیر مجموعه های فرد عضوی برابر است با $$2^{n-1}$$

بنابراین، تعداد زیر مجموعه های زوج عضوی و فرد عضوی هر کدام برابر با$$ 2^{(n-1) }$$است. پس تعداد زیر مجموعه های زوج عضوی و فرد عضوی در مجموع برابر است با $$2^n$$ اما این تعداد کل زیر مجموعه هاست. بنابراین تعداد زیر مجموعه های زوج عضوی برابر است با نصف تعداد کل زیر مجموعه ها، و همچنین تعداد زیر مجموعه های فرد عضوی نیز برابر است با نصف تعداد کل زیر مجموعه ها.