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

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

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

1 پاسخ

+3 امتیاز
پاسخ داده شده توسط AmirHosein

تعداد افرازهای یک مجموعهٔ $n$عضوی عدد $n$اُم بِل (bell) نامیده می‌شود. یک فرمول بازگشتی برای این عدد به این شکل است که نخست یکی از زیرمجموعه‌های داخل افراز را انتخاب کنید. این زیرمجموعه می‌تواند از ۱ تا $n$ داشته باشد (ولی نه صفر چون اعضای افراز باید ناتهی باشند). سپس باید اعضای باقیمانده را در یک سری زیرمجموعهٔ ناتهی دیگر قرار دهیم که با افراز کردن یک مجموعهٔ کوچکتر هم‌ارز است. پس اگر تعداد افرازهای یک مجموعهٔ $i$عضوی با $b(i)$ نمایش داده‌شود و قرارداد کنیم که $b(0)=1$ آنگاه داریم: $$b(n)=\sum_{i=1}^{n}\binom{n}{i}b(n-i)$$ شروع کنید به قرار دادن $n=1$ و سپس یکی یکی بالا آمدن. خواهید داشت $b(7)=877$.

روش دیگر برای محاسبهٔ تعداد افرازهای یک مجموعهٔ $n$ عضوی یا همان عدد $b(n)$ این است که تک تک ببینیم چند تا $k$ زیرمجموعه به ازای $k$ از یک تا $n$ می‌توانیم انتخاب کنیم. برای نمونه بدیهی است که تنها یک $n$تا زیرمجموعه می‌توان انتخاب کرد و آن این است که هر عضو را در یک تک‌عضوی قرار دهیم. اما چگونه محاسبه کنیم؟ تعداد افرازهای یک مجموعهٔ $n$عضوی به $k$ زیرمجموعه را با $S(n,k)$ نمایش دهید به این عدد، عدد استرلینگ نوع دوم (Stirling) می‌گویند. این عدد را نیز به صورت بازگشتی بر حسب مقدارهای مربوط به مقدارهای پیشین دو پارامترش می‌توان محسابه کرد. یک عضو از $n$ عضوتان را بردارید. دو حالت دارد یا این عضو در یک تک‌عضوی قرار دارد یا خیر. اگر در یک تک‌عضوی است پس کافیست تعداد افرازهای یک مجموعهٔ $n-1$ عضوی به $k-1$ زیرمجموعه را بدانید. اگر خیر، آنگاه $n-1$ عنصر را در $k$ زیرمجموعه بریزید و سپس این عضو ویژه را به یکی از آنها ملحق کنید که به $k$ حالت می‌تواند صورت بگیرد. پس $$S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$$ و روشن است که $$b(n)=\sum_{k=1}^nS(n,k)$$ در مورد این عددها مطالب زیادی وجود دارد که خودتان می‌توانید با یک جستجوی ساده پیدا کنید.

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

حمایت مالی


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

ابزارها:

سرگرمی: سودوکو جدید

رسم نمودار: Geogebra جدید

...