معادلهٔ شمارشی: مدلسازی ریاضیِ حالتهای انتخاب در مسائل گسسته
۱. تعریف معادلهٔ شمارشی و مفهوم جوابهای حالتهای انتخاب
در ریاضیات گسسته، گاهی با معادلهای روبرو میشویم که متغیرهای آن فقط مقادیر صحیح (معمولاً طبیعی یا نامنفی) میگیرند و هر جواب معادله، نشاندهندهٔ یک حالت ممکن از انتخاب است. به چنین معادلهای، معادلهٔ شمارشی2 میگوییم. به عنوان مثال، معادلهٔ $x_1 + x_2 + x_3 = 5$ را در نظر بگیرید که در آن $x_1, x_2, x_3 \ge 0$ هستند. هر جواب مانند $(2,1,2)$ یک توزیع $5$ شیء یکسان در $3$ جعبه است. بنابراین «تعداد جوابهای معادله» برابر است با «تعداد حالتهای انتخاب».
برای درک بهتر، فرض کنید $4$ سیب یکسان داریم و میخواهیم آنها را بین $2$ کودک تقسیم کنیم (هر کودک میتواند $0$ سیب نیز بگیرد). این مسئله به معادلهٔ $x_1 + x_2 = 4$ تبدیل میشود که در آن $x_1$ سیبهای کودک اول و $x_2$ سیبهای کودک دوم است. جوابهای ($0,4$)، ($1,3$)، ($2,2$)، ($3,1$) و ($4,0$) تمام حالتهای تقسیم را نشان میدهند. بنابراین تعداد جوابها همان تعداد روشهای توزیع است.
۲. فرمول اصلی شمارش برای معادلهٔ خطی با متغیرهای نامنفی
برای معادلهٔ $x_1 + x_2 + \dots + x_k = n$ که در آن $x_i \ge 0$ و $n, k$ اعداد صحیح نامنفی هستند، تعداد جوابهای صحیح (حالتهای انتخاب) برابر است با:
این فرمول از روش «جداسازی و انتخاب» به دست میآید: $n$ شیء یکسان و $k-1$ جداکننده را در یک ردیف در نظر میگیریم. تعداد کل مکانها $n+k-1$ است و انتخاب جای $k-1$ جداکننده (یا $n$ شیء) همان ترکیب را میدهد.
| معادله | تعداد متغیرها ($k$) | مقدار سمت راست ($n$) | تعداد جوابها (حالتهای انتخاب) |
|---|---|---|---|
| $x_1+x_2=5$ | $2$ | $5$ | $\binom{5+2-1}{2-1}=\binom{6}{1}=6$ |
| $x_1+x_2+x_3=4$ | $3$ | $4$ | $\binom{4+3-1}{3-1}=\binom{6}{2}=15$ |
| $x_1+x_2+x_3+x_4=2$ | $4$ | $2$ | $\binom{2+4-1}{4-1}=\binom{5}{3}=10$ |
نکته مهم: اگر متغیرها محدودیت $x_i \ge a_i$ (با $a_i$ عدد صحیح مثبت) داشته باشند، با تغییر متغیر $y_i = x_i - a_i \ge 0$ و جایگذاری در معادله، به حالت نامنفی استاندارد میرسیم. مثلاً معادلهٔ $x_1+x_2=7$ با شرط $x_1\ge2, x_2\ge1$ با تعریف $y_1=x_1-2, y_2=x_2-1$ به $y_1+y_2=4$ تبدیل میشود که تعداد جوابهای آن $\binom{4+2-1}{2-1}=5$ است.
۳. کاربرد عملی: توزیع جوایز و انتخاب اعضای تیم
فرض کنید در یک مسابقه، $10$ جایزهٔ یکسان به $4$ نفر برتر میدهیم (امکان دارد یک نفر چندین جایزه بگیرد و حتی کسی جایزه نگیرد). تعداد روشهای توزیع جوایز برابر است با تعداد جوابهای معادلهٔ $x_1+x_2+x_3+x_4=10$ که $x_i \ge 0$ است. با استفاده از فرمول داریم:
یک مثال دیگر: مدیر یک شرکت میخواهد $8$ پروژهٔ یکسان را بین $3$ تیم کاری تقسیم کند، اما به هر تیم حداقل $1$ پروژه برسد. با تعریف $y_i = x_i - 1 \ge 0$، معادله به $y_1+y_2+y_3 = 5$ تبدیل میشود. تعداد جوابها $\binom{5+3-1}{3-1}=\binom{7}{2}=21$ است. این اعداد نشان میدهند که معادلات شمارشی ابزاری قدرتمند برای شمردن حالتهای انتخاب بدون نیاز به فهرست کردن تک تک موارد هستند.
۴. چالشهای مفهومی و پرسشهای رایج
پاسخ: با تغییر متغیر $y_i = x_i - 1 \ge 0$، مجموع $y_i$ برابر $n - k$ میشود. بنابراین تعداد جوابها برابر $\binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}$ خواهد بود.
پاسخ: خیر، ایدهٔ اصلی برای هر ساختاری که بتوان آن را به معادلهٔ خطی با متغیرهای گسسته تبدیل کرد، به کار میرود. مثلاً در شمارش حالتهای یک تابع با دامنهٔ محدود یا توزیع اشیاء با محدودیتهای خاص، از همین الگو استفاده میشود. البته برای معادلات غیرخطی یا با قیود مرکب، روشهای ترکیبیاتی پیشرفتهتری نیاز است.
پاسخ: $k^n$ زمانی به کار میرود که $n$ شیء متمایز را بین $k$ جعبه توزیع کنیم. اما در معادلهٔ شمارشی، متغیرها فقط تعداد اشیاء را نشان میدهند و خود اشیاء یکسان فرض میشوند. به همین دلیل از ترکیب (تکرار) استفاده میشود نه توان.
جمعبندی
پاورقی
1 جداسازی و انتخاب (Stars and Bars): روشی در ترکیبیات که برای شمارش تعداد راههای توزیع اشیاء یکسان در جعبههای مجزا به کار میرود.2 معادلهٔ شمارشی (Enumeration Equation): معادلهای که جوابهای صحیح آن نشانگر تعداد حالتهای ممکن در یک فرایند انتخابی است.
3 متغیر نامنفی (Non‑negative Variable): متغیری که فقط میتواند مقادیر $0,1,2,\dots$ بگیرد.