Question

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

Answer 1

تعداد افرازهای یک مجموعهٔ $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)$$ در مورد این عددها مطالب زیادی وجود دارد که خودتان می‌توانید با یک جستجوی ساده پیدا کنید.