ماشین حساب ستاره ها و میله ها
از روش ستاره ها و میله ها برای شمارش ترکیب ها با تکرار استفاده کنید x1 + ... + xk = nاز جمله موارد غیر منفی، مثبت، کران پایین و محدود.
نحوه استفاده (3 مرحله)
- وارد کنید n (کل) و ک (تعداد متغیرها / کادرها).
- شرایط را انتخاب کنید: xi ≥ 0، xi ≥ 1، یا xi ≥ ai (اختیاری: محدود).
- یک URL قابل اشتراکگذاری را برای بازتولید همان حالت کپی کنید.
توجه: این ماشین حساب حساب می شود یکسان توپ ها اگر توپ ها متمایز باشند، مدل متفاوت است.
راهنمای تصویری
برای ورودی های کوچک، این یک مثال را نشان می دهد که با ستاره (*) و نوار (|) رمزگذاری می شود. این یک تصویر است، نه "تنها ترتیب".
نتایج
مراحل (کوتاه)
استدلال را نشان دهید
مثال ها (راه حل ها)
راه حل هایی برای 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 موقعیت ها، شما یک راه حل را به طور کامل شرح داده اید.
در 3 مرحله از آن استفاده کنید
- وارد کنید n برای تعداد کل اقلام یکسان و ک برای تعداد جعبه ها یا متغیرها.
- شرایطی را انتخاب کنید که با مشکل مطابقت دارد: xi ≥ 0، xi ≥ 1، کرانهای پایین یا مقادیر محدود.
- ابتدا تعداد را بخوانید، سپس مراحل کوتاه و مثالها را بررسی کنید تا مطمئن شوید که مدل مناسب را انتخاب کردهاید.
نحوه انتخاب حالت
- استفاده کنید xi ≥ 0 زمانی که جعبه های خالی مجاز هستند.
- استفاده کنید xi ≥ 1 زمانی که هر جعبه باید حداقل یک مورد دریافت کند.
- استفاده کنید xi ≥ ai زمانی که هر متغیر دارای حداقل باشد.
- استفاده کنید ai ≤ xi ≤ bi فقط زمانی که هر دو کران پایین و بالا بخشی از مشکل باشند.
مقایسه های کار شده
اگر 7 توپ یکسان را در 3 جعبه با جعبه های خالی قرار دهید، شمارش می شود 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 میله را در یک ردیف قرار دهید. انتخاب موقعیت های میله به طور منحصر به فرد یک راه حل را تعیین می کند و به C(n+k-1، k-1) می دهد.
وقتی xi≥1 فرمول چگونه تغییر می کند؟
بگذارید yi=xi−1 باشد. سپس y1+…+yk=n−k با yi≥0، بنابراین وقتی n≥k شمارش C(n−1، k−1) است، در غیر این صورت 0 است.
کران های پایین xi≥ai چگونه کار می کنند؟
اجازه دهید yi=xi−ai. سپس y1+…+yk=n−Σai با yi≥0. اگر n≥Σai، شمارش C((n−Σai)+k−1، k−1) است. در غیر این صورت 0.
چه زمانی باید به جای غیر منفی از مثبت استفاده کنم؟
زمانی که هر متغیر یا جعبه باید حداقل یک مورد دریافت کند از حالت مثبت استفاده کنید. وقتی صفر مجاز است از حالت غیر منفی استفاده کنید. همین تغییر عبارت، رایجترین منبع پاسخهای اشتباه در مسائل ستارهها و میلهها است.
اگر توپ ها قابل تشخیص باشند چه؟
این ماشین حساب توپ های یکسان را فرض می کند. اگر توپ ها قابل تشخیص هستند، مدل تغییر می کند (اغلب k^n یا چند جمله ای)، بنابراین بسته به مشکل از یک ماشین حساب متفاوت استفاده کنید.
ابزارهای مرتبط
پرسشهای متداول
روش ستاره و میله چیست؟
تعداد راههایی را برای توزیع n مورد یکسان در k جعبه میشمارد، که تعداد راهحلهای x1+…+xk=n تحت شرایطی مانند xi≥0 است.
چرا حالت غیر منفی C(n+k-1، 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) است، در غیر این صورت 0 است.
کران های پایین xi≥ai چگونه کار می کنند؟
اجازه دهید yi=xi−ai. سپس y1+…+yk=n−Σai با yi≥0. اگر n≥Σai، شمارش C((n−Σai)+k−1، k−1) است. در غیر این صورت 0.
چه زمانی باید به جای غیر منفی از مثبت استفاده کنم؟
زمانی که هر متغیر یا جعبه باید حداقل یک مورد دریافت کند از حالت مثبت استفاده کنید. وقتی صفر مجاز است از حالت غیر منفی استفاده کنید. همین تغییر عبارت، رایجترین منبع پاسخهای اشتباه در مسائل ستارهها و میلهها است.
اگر توپ ها قابل تشخیص باشند چه؟
این ماشین حساب توپ های یکسان را فرض می کند. اگر توپ ها قابل تشخیص هستند، مدل تغییر می کند (اغلب k^n یا چند جمله ای)، بنابراین بسته به مشکل از یک ماشین حساب متفاوت استفاده کنید.