به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
85 بازدید
سوال شده در دبیرستان توسط

ثابت کنید(ترجیحا با اصل استقرا) تعداد زیر مجموعه های K عضوی یک مجموعه ، $ \binom{|A|}{k} $ است.

مرجع: گسسته و جبر و احتمال خیلی سبز - توسط رسول محسنی منش و سروش موئینی - فصل پنجم - صفحه ی ۲۵۳

1 پاسخ

+1 امتیاز
پاسخ داده شده توسط
انتخاب شده توسط
 
بهترین پاسخ

اگر به پرسش فکر می‌کردید می‌دید که واقعا هیچی ندارد. تعداد زیرمجموعه‌های $k$ عضوی از یک مجموعهٔ $n$ عضوی یعنی چه؟ یعنی تعداد حالت‌هایی که می‌توان $k$ عضو از $n$ عضو انتخاب کرد. و این یعنی $\binom{n}{k}$. نیاز به استقرا نیز ندارد چون دقیقا خود جمله‌ای است که می‌گویید. ولی اگر دنبال استقرا می‌گردید احتمالا اثباتِ $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ است که در چندین جا دیده‌اید. فرض کنید برای کمتر یا مساوی $n$ برقرار باشد اکنون انتخاب $k$ عضو از $n+1$، بیایید یک عضو را ویژه کنید. دو حالت دارید یا همهٔ $k$ عضو را از $n$ عضو ناویژه انتخاب می‌کنید یا یکی از آنها عضو ویژه است و $k-1$ ای از $n$ عضو ویژه برمی‌دارید. پس $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$ چون بالای این انتخاب‌ها $n$ است از فرض استقرا می‌توانید فرمول را برایشان جایگذاری کنید و سپس دو کسر را با هم جمع و ساده‌سازی کنید، کسرِ متناسب با فرمول برای $n+1$ را خواهید داشت.

به محفل ریاضی ایرانیان خوش آمدید!
کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
حمایت مالی
...