پرش به محتویات

ستاره و خط

ستاره و خط یک تکنیک ریاضی برای حل مسائل ترکیبیاتی خاصی است. این تکنیک زمانی به کار می‌آید که بخواهیم تعداد راه‌های دسته‌بندی اشیاء یکسان را بشماریم.

قضیه

تعداد راه‌های قرار دادن $n$ شیء یکسان در $k$ جعبه‌ی متمایز برابر است با:

$$\binom{n + k - 1}{n}$$

اثبات این قضیه شامل تبدیل اشیاء به ستاره و جدا کردن جعبه‌ها با استفاده از خط است (و به همین دلیل این نام را دارد). برای مثال، می‌توانیم وضعیت زیر را با $\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$ نمایش دهیم: در جعبه‌ی اول یک شیء، در جعبه‌ی دوم دو شیء، جعبه‌ی سوم خالی و در جعبه‌ی آخر دو شیء قرار دارد. این یک راه برای تقسیم ۵ شیء در ۴ جعبه است.

باید کاملاً واضح باشد که هر افراز را می‌توان با $n$ ستاره و $k-1$ خط نمایش داد و هر جایگشت از $n$ ستاره و $k-1$ خط نیز یک افراز را نشان می‌دهد. بنابراین، تعداد راه‌های تقسیم $n$ شیء یکسان در $k$ جعبه‌ی متمایز، برابر با تعداد جایگشت‌های $n$ ستاره و $k-1$ خط است. ضریب دوجمله‌ای فرمول مورد نظر را به ما می‌دهد.

تعداد مجموع‌های اعداد صحیح نامنفی

این مسئله یک کاربرد مستقیم از قضیه است.

می‌خواهیم تعداد جواب‌های معادله‌ی زیر را بشماریم:

$$x_1 + x_2 + \dots + x_k = n$$

با شرط $x_i \ge 0$.

دوباره می‌توانیم یک جواب را با استفاده از ستاره و خط نمایش دهیم. برای مثال، جواب $1 + 3 + 0 = 4$ برای $n=4$ و $k=3$ را می‌توان با $\bigstar | \bigstar \bigstar \bigstar |$ نمایش داد.

به راحتی می‌توان دید که این دقیقاً همان قضیه‌ی ستاره و خط است. بنابراین، جواب برابر است با $\binom{n + k - 1}{n}$.

تعداد مجموع‌های اعداد صحیح مثبت

قضیه‌ی دوم، تفسیر جالبی برای اعداد صحیح مثبت ارائه می‌دهد. جواب‌های معادله‌ی زیر را در نظر بگیرید:

$$x_1 + x_2 + \dots + x_k = n$$

با شرط $x_i \ge 1$.

می‌توانیم $n$ ستاره را در نظر بگیریم، اما این بار می‌توانیم حداکثر یک خط بین ستاره‌ها قرار دهیم، زیرا دو خط بین ستاره‌ها به معنای $x_i=0$ است، یعنی یک جعبه‌ی خالی. $n-1$ فاصله بین ستاره‌ها برای قرار دادن $k-1$ خط وجود دارد، بنابراین جواب برابر است با $\binom{n-1}{k-1}$.

تعداد مجموع‌های اعداد صحیح با کران پایین

این روش را به سادگی می‌توان به مجموع اعداد صحیح با کران‌های پایین متفاوت تعمیم داد. یعنی می‌خواهیم تعداد جواب‌های معادله‌ی زیر را بشماریم:

$$x_1 + x_2 + \dots + x_k = n$$

با شرط $x_i \ge a_i$.

پس از جایگذاری $x_i' := x_i - a_i$ معادله‌ی اصلاح‌شده‌ی زیر را به دست می‌آوریم:

$$(x_1' + a_1) + (x_2' + a_2) + \dots + (x_k' + a_k) = n$$
$$\Leftrightarrow ~ ~ x_1' + x_2' + \dots + x_k' = n - a_1 - a_2 - \dots - a_k$$

با شرط $x_i' \ge 0$. بنابراین، مسئله را به حالت ساده‌تر با شرط $x_i' \ge 0$ کاهش دادیم و دوباره می‌توانیم از قضیه‌ی ستاره و خط استفاده کنیم.

تعداد مجموع‌های اعداد صحیح با کران بالا

با کمی کمک از اصل شمول و طرد، می‌توانید اعداد صحیح را با کران‌های بالا نیز محدود کنید. بخش تعداد مجموع‌های صحیح با کران بالا را در مقاله‌ی مربوطه ببینید.

مسائل تمرینی