توزیع اشیای یکسان: روشهای علمی تقسیم اشیای همنوع بین دستهها و افراد
تفاوت اساسی: توزیع اشیای یکسان در برابر اشیای متمایز
در نظریه شمارش، نوع اشیایی که توزیع میکنیم تأثیر زیادی روی تعداد حالتهای ممکن دارد. وقتی اشیا متمایز (مثل دانشآموزان با نامهای متفاوت) هستند، هر ترتیب یا جابهجایی یک حالت جدید ایجاد میکند. اما اگر اشیا یکسان و همنوع باشند (مثل سکههای طلای کاملاً مشابه)، تنها تعداد اشیایی که به هر دسته میرسد مهم است، نه اینکه کدام شیء به کدام دسته رفته است.
برای روشن شدن تفاوت، مثال زیر را در نظر بگیرید: میخواهیم 4 توپ کاملاً شبیه به هم را بین 2 جعبه تقسیم کنیم. در توزیع اشیای یکسان، حالتهای ممکن بر اساس تعداد توپهای جعبه اول عبارتند از: 0,1,2,3,4 توپ → یعنی 5 حالت. اما اگر توپها متمایز و شمارهدار بودند، هر توپ میتوانست به یکی از دو جعبه برود: 2^4 = 16 حالت. این اختلاف بنیادی، پایه تمام محاسبات ما در این مقاله است.
قضیه اصلی: فرمول ستارهها و میلهها
مهمترین ابزار برای شمارش تعداد روشهای توزیع n شیء یکسان بین k دسته (یا نفر) «قضیه ستارهها و میلهها» نام دارد. در این قضیه، هر حالت توزیع را با چیدمانی از n ستاره (نماد اشیا) و k-1 میله (جداکننده دستهها) نشان میدهیم. تعداد کل چیدمانهای ممکن برابر است با تعداد راههای انتخاب جایگاه میلهها از بین کل جایگاهها.
مثال گام به گام: چند راه میتوان 5 آب نبات یکسان را بین 3 کودک تقسیم کرد؟ (برخی کودکان ممکن است چیزی نگیرند).
مرحله اول: مشخص کردن پارامترها. n=5 و k=3. طبق فرمول داریم: $ \binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} $. محاسبه: $ \binom{7}{2} = \frac{7 \times 6}{2 \times 1} = 21 $. بنابراین 21 راه مختلف وجود دارد.
| نوع قید و شرط | فرمول عمومی (تعداد حالتها) | مثال عددی (n=5 , k=3) |
|---|---|---|
| بدون قید (توزیع آزاد، صفر مجاز است) | $ \binom{n+k-1}{k-1} $ | $ \binom{7}{2}=21 $ |
| هر دسته حداقل 1 شیء بگیرد | $ \binom{n-1}{k-1} $ | $ \binom{4}{2}=6 $ |
| هر دسته حداقل a شیء (a مثبت) | $ \binom{n - k \cdot a + k - 1}{k-1} $ | (برای a=2) $ \binom{5-6+2}{2}= \binom{1}{2}=0 $ غیرممکن |
روش گام به گام تبدیل مسئله به ترکیب با تکرار
برای حل مسائل توزیع اشیای یکسان، همیشه میتوانیم مراحل زیر را طی کنیم:
مرحله ۱: تعداد اشیا (n) و تعداد دستهها یا گیرندگان (k) را مشخص کنید.
مرحله ۲: در صورت وجود شرط «حداقل گرفتن» برای هر دسته، آن مقدار را از تعداد کل اشیا کم کنید. مثلاً اگر هر نفر باید حداقل ۱ شیء بگیرد، ابتدا به هر نفر ۱ شیء میدهیم و سپس اشیای باقیمانده (n - k) را آزادانه توزیع میکنیم.
مرحله ۳: از فرمول اصلی $ \binom{(\text{تعداد اشیای باقیمانده}) + k - 1}{k-1} $ استفاده کنید.
کاربرد واقعی: بودجهبندی و تقسیم منابع یکسان
فرض کنید یک شرکت 20 میلیون تومان کمک هزینه یکسان (همه اسکناسها به عنوان اشیای یکسان در نظر گرفته میشوند) را میخواهد بین 5 پروژه تقسیم کند. اگر هیچ پروژهای نباید بیبودجه بماند (هر پروژه حداقل 1 میلیون دریافت کند)، ابتدا 1 میلیون به هر پروژه میدهیم، 20-5=15 میلیون باقی میماند. تعداد حالتهای توزیع برابر است با $ \binom{15+5-1}{5-1} = \binom{19}{4} = 3876 $. این محاسبه به مدیران نشان میدهد که تعداد سناریوهای ممکن بسیار زیاد است و برای تصمیمگیری به قیود اضافی نیاز دارند.
چالشهای مفهومی
پاسخ: زیرا اشیا یکسان هستند. $ k^n $ تعداد توابع از مجموعه اشیای متمایز به مجموعه دستهها را میدهد. وقتی اشیا قابل تشخیص نباشند، تنها تعداد اشیای هر دسته مهم است که معادل «ترکیب با تکرار» است.
پاسخ: این تکنیک «تغییر متغیر» نام دارد. میگذاریم $ y_i = x_i - 1 $ که در آن $ x_i $ تعداد اشیای دستهٔ i است. شرط $ x_i \ge 1 $ معادل $ y_i \ge 0 $ میشود و مجموع $ y_i $ برابر n-k $ خواهد بود. سپس مسئله به حالت آزاد تبدیل میشود.
پاسخ: در تمام فرمولهای این مقاله فرض میشود دستهها یا گیرندگان «قابل تشخیص» هستند (مثلاً نفر اول، دوم و ...). اگر دستهها نامگذاری نشده باشند (یعنی فقط اندازه دستهها مهم باشد بدون برچسب)، مسئله به «تقسیم اعداد صحیح»3 تبدیل میشود که بسیار پیچیدهتر است و فرمول سادهای مانند بالا ندارد.
جمعبندی
پاورقی
1 ترکیب با تکرار (Combination with Repetition): روش انتخاب k شیء از n نوع، به طوری که هر نوع میتواند بیش از یک بار انتخاب شود و ترتیب اهمیتی ندارد. تعداد حالتها برابر $ \binom{n+k-1}{k} $ است.
2 قضیه ستارهها و میلهها (Stars and Bars Theorem): یک قضیه ترکیبیاتی برای شمارش تعداد راههای قرار دادن n اشیای غیرقابل تشخیص در k جعبه قابل تشخیص.
3 تقسیم اعداد صحیح (Integer Partition): تعداد راههای نوشتن یک عدد صحیح به صورت مجموع اعداد صحیح مثبت، بدون در نظر گرفتن ترتیب جمعشوندگان.