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

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

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

1 پاسخ

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

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

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
تلگرام محفل ریاضی
44 نفر آنلاین
0 عضو و 44 مهمان در سایت حاضرند
بازدید امروز: 1511
بازدید دیروز: 5291
بازدید کل: 4844995
...