روش ستاره و میله؛ شمارش جوابهای صحیح نامنفی
آموزش شمارش جوابهای معادله با متغیرهای نامنفی یا مثبت و اعمال کران پایین با روش ستاره و میله.
پاسخ کوتاه
روش ستاره و میله، توزیع اشیای یکسان میان جعبههای متمایز را به شمارش جای جداکنندهها تبدیل میکند. این روش زمانی مستقیم است که متغیرها صحیح و نامنفی باشند و مجموع ثابتی داشته باشند؛ شرط مثبت یا کران پایین با تغییر متغیر مدیریت میشود.
حالت نامنفی
تعداد جوابهای صحیح نامنفی x1+...+xk=n برابر C(n+k-1,k-1) است. n ستاره نماینده واحدها و k-1 میله مرز میان متغیرها هستند؛ کنارهمقرارگرفتن میلهها یعنی بعضی متغیرها میتوانند صفر باشند.
حالت مثبت
اگر همه متغیرها مثبت باشند، ابتدا به هر متغیر یک واحد بده و yi=xi-1≥0 بگذار. مجموع جدید n-k میشود و تعداد جوابها C(n-1,k-1) است؛ اگر n<k باشد هیچ جواب مثبتی وجود ندارد.
کران پایین متفاوت
برای شرط xi≥ai، جایگذاری yi=xi-ai انجام بده. مجموع مقدارهای حداقل را از کل کم کن و مسئله نامنفی تازه را حل کن؛ فراموشکردن این کاهش باعث شمارش حالتهایی میشود که شرط اولیه را ندارند.
تشخیص اشیای یکسان
ستاره و میله برای واحدهای یکسان و مقصدهای متمایز است. اگر اشیا متمایز باشند، هر شیء انتخاب مستقلی دارد و روش توانی یا اصل ضرب مناسبتر است؛ اگر جعبهها نیز یکسان باشند، فرمول ساده جواب نمیدهد.
مثال حلشده
تعداد جوابهای نامنفی x+y+z=7 برابر C(9,2)=36 است. اگر هر سه متغیر مثبت باشند، پس از کمکردن یک از هرکدام مجموع جدید 4 و تعداد C(6,2)=15 میشود.
کران بالا
شرطهایی مانند x≤m با ستاره و میله مستقیم حل نمیشوند. میتوان کل جوابهای نامنفی را شمرد و حالتهای ناقض کران را با تغییر متغیر و اصل شمول و عدمشمول کم کرد؛ مجموعههای ناقض ممکن است همپوشانی داشته باشند.
چکلیست حل تست
- نامنفی و مثبت دو فرمول متفاوت دارند.
- مجموع کرانهای پایین را پیش از شمارش کم کن.
- برای کران بالا از متمم و شمول و عدمشمول کمک بگیر.