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

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 تبدیل می‌شود.

در مثال فوق: