بلاگ

پایگـاه اطلاعات علمی جهاد دانشگاهی

مساله ستاره‌ها و حائل‌ها


combinatorics Stars and bars

فرض کنید می‌خواهیم m شی یکسان را در n دسته قرار بدهیم به گونه‌ای که هر دسته حداقل صفر و حداکثر  m شی داشته باشد. به چند حالت می‌توانیم این دسته‌بندی را انجام بدهیم؟
برای حل این مساله از یک ترفند استفاده می‌کنیم و فرض می‌کنیم n-1 حائل داشته باشیم. توجه می‌کنیم که هر حائل فضا را به دو قسمت تقسیم می‌کند. بنابراین برای تقسیم فضا به n قسمت به n-1 حائل نیاز داریم. هم‌چنین m ستاره داریم. حال کافی است تمام حالات قرار گرفتن ستاره‌ها و حائل‌ها را محاسبه کنیم. به عنوان نمونه در شکل زیر سه ستاره و یک حائل داریم. بناراین می‌خواهیم سه شی را به دو دسته تقسیم کنیم:

 

**|*

|***

***|

*|**

هشتمین کارگاه آموزشی یادگیری عمیق (deep learning) (مجازی)

به این ترتیب m+n-1! حالت خواهیم داشت. اما چون هم اشیا و هم حائل‌ها یکسان هستند، لازم حالا تکراری را حذف کنیم. بنابراین کافی است مقدار فوق را بر m!*(n-1)! تقسیم کنیم. به این ترتیب، مساله به انتخاب n-1 از m+n+1 تبدیل می‌شود.

در مثال فوق:

پست های مرتبط

چگونه 10 مهره را در سه ظرف به صورت فرد تقسیم کنیم

تاریخ: 1400/03/22

بازدید: 945

1400

زمان مطالعه: 5 دقیقه دقیقه

استعداد تحصیلی

مدرس

@ins

مصورسازی هم آیندی کلیدواژگان

تاریخ: 1400/02/31

بازدید: 1835

1400

زمان مطالعه: 5 دقیقه دقیقه

کشف دانش از طریق تجزیه و تحلیل هم رخدادی واژگان

مدرس

@ins