ماشینحساب ستارهها و میلهها
با روش ستارهها و میلهها، تعداد جوابهای صحیح معادلهٔ x1 + ... + xk = n را در حالتهای نامنفی، مثبت، دارای کران پایین یا کراندار بشمارید.
روش استفاده (۳ مرحله)
- n (مجموع اقلام) و k (تعداد متغیرها یا جعبهها) را وارد کنید.
- شرط مسئله را انتخاب کنید: xi ≥ 0، xi ≥ 1، xi ≥ ai یا حالت کراندار.
- برای بازسازی همین حالت، لینک قابل اشتراک را کپی کنید.
این ماشینحساب اقلام یکسان را فرض میکند. اگر اقلام متمایز باشند، باید از مدل شمارشی دیگری استفاده کنید.
راهنمای تصویری
برای ورودیهای کوچک، یک نمونه با ستاره (*) و میله (|) نمایش داده میشود. این فقط یک نمایش نمونه است، نه تنها چینش ممکن.
نتایج
مراحل کوتاه
نمایش روش حل
مثالها (جوابها)
نمایش جوابها برای n و k کوچک
برای حفظ کارایی، تعداد جوابهای فهرستشده محدود است. برای ورودیهای بزرگ فقط از مقدار شمارش استفاده کنید.
فرمولها و خطاهای رایج
- نامنفی (xi≥0):
C(n+k−1, k−1) - این همان «ترکیب با تکرار» است:
k multichoose n = C(n+k−1, n). - مثبت (xi≥1):
C(n−1, k−1)؛ اگرn<kباشد، نتیجه0است. - کرانهای پایین (xi≥ai): ابتدا
n−Σaiرا بهدست آورید، سپسC((n−Σai)+k−1, k−1)را حساب کنید.
خطاهای رایج
- اقلام یکسان را با اقلام متمایز اشتباه نگیرید. این ماشینحساب جوابهای صحیح برای اقلام یکسان را میشمارد.
- در حالت xi≥1، اگر
n<kباشد، نتیجه0است. - در حالت کران پایین باید مجموع
Σaiرا کم کنید، نه فقط یک مقدار a؛ مگر اینکه همهٔ aiها برابر باشند.
ماشینحسابهای مرتبط
چگونه حالت مناسب را انتخاب کنیم؟
این ماشینحساب برای توزیع اقلام یکسان میان جعبهها یا متغیرهاست. اگر ترتیب مهم است یا اقلام متمایز هستند، از مدل شمارشی دیگری استفاده کنید.
نقش میلهها چیست؟
در نمایش کلاسیک، هر ستاره یک قلم و هر میله مرز میان دو جعبه است. با انتخاب جایگاه k−1 میله در میان n+k−1 جایگاه، دقیقاً یک جواب معادله مشخص میشود.
سه گام برای محاسبه
- n را برای مجموع اقلام یکسان و k را برای تعداد جعبهها یا متغیرها وارد کنید.
- شرط مناسب مسئله را انتخاب کنید: xi ≥ 0، xi ≥ 1، کرانهای پایین یا حالت کراندار.
- مقدار شمارش را بخوانید و سپس مراحل کوتاه و مثالها را بررسی کنید تا از انتخاب مدل درست مطمئن شوید.
انتخاب حالت
- اگر جعبهٔ خالی مجاز است، از xi ≥ 0 استفاده کنید.
- اگر هر جعبه باید دستکم یک قلم داشته باشد، از xi ≥ 1 استفاده کنید.
- اگر هر متغیر حداقل مشخصی دارد، از xi ≥ ai استفاده کنید.
- اگر مسئله هم کران پایین و هم کران بالا دارد، از ai ≤ xi ≤ bi استفاده کنید.
مقایسهٔ دو نمونه
برای توزیع ۷ توپ یکسان در ۳ جعبه با امکان خالیبودن جعبهها، تعداد جوابها C(9,2) است. اگر هر جعبه باید دستکم یک توپ داشته باشد، حالت مثبت را انتخاب کنید؛ در این صورت تعداد جوابها C(6,2) است. مقایسهٔ این دو حالت کمک میکند شرط نامنفی را با شرط مثبت اشتباه نگیرید.
خطاهای رایج
- این روش را برای اقلام متمایز بهکار نبرید؛ در آن مسائل ممکن است جایگشت، شمارش چندجملهای یا ترکیب عدد صحیح مدل درست باشد.
- وقتی هر جعبه باید دستکم یک قلم داشته باشد، حالت xi ≥ 0 را انتخاب نکنید.
- پیش از واردکردن کرانها بررسی کنید که مجموع آنها با مقدار n سازگار باشد.
- نمونهٔ تصویری را فهرست کامل جوابها در نظر نگیرید.
ابزارهای مرتبط
پرسش های متداول
روش ستارهها و میلهها چیست؟
این روش راههای توزیع n قلم یکسان میان k جعبه را میشمارد؛ یعنی تعداد جوابهای صحیح معادلهٔ x1+…+xk=n را با شرطهایی مانند xi≥0 بهدست میآورد.
چرا در حالت نامنفی فرمول C(n+k−1، k−1) است؟
n ستاره و k−1 میله را در یک ردیف میچینیم. انتخاب جایگاه میلهها از میان n+k−1 جایگاه، هر جواب را بهطور یکتا مشخص میکند؛ بنابراین تعداد جوابها C(n+k−1، k−1) است.
وقتی xi≥1 است، فرمول چگونه تغییر میکند؟
قرار دهید yi=xi−1. در این صورت y1+…+yk=n−k و yi≥0 است؛ پس اگر n≥k باشد، تعداد جوابها C(n−1، k−1) و در غیر این صورت صفر است.
کرانهای پایین xi≥ai چگونه اعمال میشوند؟
قرار دهید yi=xi−ai. سپس y1+…+yk=n−Σai و yi≥0 است. اگر n≥Σai باشد، تعداد جوابها C((n−Σai)+k−1، k−1) و در غیر این صورت صفر است.
چه زمانی حالت مثبت را بهجای نامنفی انتخاب کنم؟
اگر هر متغیر یا جعبه باید دستکم یک قلم داشته باشد، حالت مثبت را انتخاب کنید. وقتی صفر مجاز است، حالت نامنفی مناسب است. تفاوت این دو شرط یکی از علتهای رایج پاسخ نادرست است.
اگر اقلام متمایز باشند چه؟
این ماشینحساب اقلام یکسان را فرض میکند. برای اقلام متمایز، مدل شمارش تغییر میکند و معمولاً به k^n یا ضرایب چندجملهای نیاز است؛ بنابراین ابزار متناسب با آن مسئله را انتخاب کنید.