بودجهٔ مرور پیشنهادی
ریاضیات گسسته دوازدهم / فصل ۳فرمول، آخرین گام مدلسازی است
من راهنمای منطق رندو هستم. بیا پیش از نوشتن فرمول، یک خروجی نمونه بسازیم و مسیر تولیدش را با هم دنبال کنیم؛ این کار دوبارهشماری را زود آشکار میکند.
آیا ترتیب مهم است؟ آیا حالتها ناسازگارند؟ آیا تعداد انتخابهای هر مرحله ثابت است؟
جمع برای «یا»، ضرب برای «و سپس»
اصل جمع به ناسازگاری نیاز دارد
اگر خروجیهای دو حالت هیچ اشتراکی نداشته باشند و بهترتیب m و n راه داشته باشند، کل تعداد m+n است. اگر اشتراک دارند، جمع ساده دوبارهشماری میکند.
اصل ضرب به تعداد ثابت ادامهها نیاز دارد
اگر مرحلهٔ اول m انتخاب و پس از هر انتخاب دقیقاً n ادامهٔ مجاز داشته باشد، تعداد مسیرها mn است. اگر تعداد ادامهها وابسته است، حالتها را جدا کن.
درخت تصمیم خطای مدل را نشان میدهد
هر مسیر ریشه تا برگ باید دقیقاً یک خروجی مجاز بسازد و هر خروجی باید دقیقاً یک مسیر داشته باشد. نبود یا تکرار یک خروجی یعنی مدل ناقص است.
ریاضیات گسسته دوازدهم / فصل ۳جایگشت یا ترکیب؟ نقشها را ببین
نقش متفاوت یعنی ترتیب مهم است
انتخاب رئیس و نایبرئیس از n نفر، n(n−۱) حالت دارد؛ جابهجایی دو نفر خروجی تازه میسازد.
تیم بینقش با ترکیب شمرده میشود
برای انتخاب r عضو از n نفر وقتی ترتیب مهم نیست و ۰≤r≤n، از C(n,r) استفاده کن. هر تیم در جایگشت r! بار ظاهر میشود؛ تقسیم بر همین عامل دوبارهشماری را حذف میکند.
در جایگشت تکراری فقط همسانها را تقسیم کن
اگر از n شیء، گروههای همسان با تعدادهای n۱,…,nk داشته باشیم و n۱+…+nk=n، تعداد چیدمانها n!/(n۱!…nk!) است.
ریاضیات گسسته دوازدهم / فصل ۳کران پایین را با تغییر متغیر حذف کن
ستاره و میله برای جواب نامنفی است
برای عدد صحیح n≥۰ و عدد صحیح k≥۱، تعداد جوابهای صحیح نامنفی x۱+…+xk=n برابر C(n+k−۱,k−۱) است؛ شرط نامنفی و ضریبهای یک، بخش ضروری مدلاند.
شرط مثبت را یک واحد کم کن
اگر xi≥۱، بگذار yi=xi−۱. برای کران xi≥ai نیز yi=xi−ai میگذاریم.
قید بالا با فرمول ساده حل نمیشود
پس از حذف کران پایین، اگر شرطی مانند x۱≤b باقی بماند، حالتهای نامجاز را کم کن یا برحسب مقدار آن متغیر حالتبندی کن.
ریاضیات گسسته دوازدهم / فصل ۳تکرار ممنوع در هر سطر و ستون
مرتبه یعنی تعداد نمادها و طول ضلع
برای عدد صحیح مثبت n، مربع لاتین مرتبهٔ n جدولی n×n با n نماد است که هر نماد در هر سطر و هر ستون دقیقاً یک بار میآید.
جابهجایی چرخهای یک ساخت استاندارد است
سطر نخست را ۱،۲،…،n بنویس و در هر سطر همهٔ نمادها را یک خانه بهطور چرخهای جابهجا کن. شرط سطر و ستون مستقیماً برقرار میشود.
تعامد با زوجهای مرتب سنجیده میشود
دو مربع لاتین متمایز و هممرتبه متعامدند اگر با رویهمگذاری آنها، هر زوج مرتب نمادها دقیقاً یک بار ظاهر شود. فقط متفاوتبودن خانههای متناظر کافی نیست.
| ۱ | ۲ | ۳ |
| ۲ | ۳ | ۱ |
| ۳ | ۱ | ۲ |
| ۱ | ۲ | ۳ |
| ۳ | ۱ | ۲ |
| ۲ | ۳ | ۱ |
ریاضیات گسسته دوازدهم / فصل ۳مسئله را به مجموعهای آشنا منتقل کن
تناظر یکبهیک تعداد را حفظ میکند
اگر هر شیء مجموعهٔ اول دقیقاً به یک شیء مجموعهٔ دوم و برعکس متناظر شود، دو مجموعه هماندازهاند. باید هم یکتایی تصویر و هم امکان بازگشت را توضیح دهی.
مسیر شبکهای یک دنباله از حرکتهاست
برای اعداد صحیح نامنفی r,u، اگر فقط حرکت راست و بالا مجاز باشد، کافی است جای r حرکت راست را میان r+u جایگاه انتخاب کنیم؛ پاسخ C(r+u,r) است.
عبور از نقطهٔ معین، مسئله را دو تکه میکند
تعداد مسیرهای مبدأ تا نقطهٔ اجباری را در تعداد مسیرهای آن نقطه تا مقصد ضرب کن. این ضرب مجاز است چون هر مسیر کامل دقیقاً یک پیشوند و یک پسوند دارد.
اشتراک را کم کن؛ پوشا را دقیق مدل کن
برای دو مجموعه، اشتراک یک بار کم میشود
|A∪B|=|A|+|B|−|A∩B|. اعضای اشتراک در دو جمع نخست دوبار آمدهاند، پس یک بار کم میشوند.
تابع یعنی برای هر عضو دامنه یک انتخاب
برای مجموعههای متناهی با m≥۰ عضو در دامنه و n≥۱ عضو در همدامنه، تعداد تابعها برابر nm است؛ هر عضو دامنه مستقل یکی از n تصویر را میگیرد.
پوشا یعنی هیچ عضو همدامنه بیتصویر نماند
برای شمارش تابع پوشا، از همهٔ تابعها آغاز کن و تابعهایی را که دستکم یک عضو همدامنه را استفاده نکردهاند با شمول و عدم شمول حذف کن.
ریاضیات گسسته دوازدهم / فصل ۳میانگین را به تضمین تبدیل کن
بیش از تعداد لانهها، تکرار را تضمین میکند
اگر بیش از n شیء در n دسته قرار گیرند، دستکم یک دسته حداقل دو شیء دارد. شیء و دسته را باید صریح تعریف کنی.
نسخهٔ تعمیمیافته سقف میخواهد
برای اعداد صحیح N≥۰ و k≥۱، با قرار دادن N شیء در k دسته، دستکم یک دسته حداقل ⌈N/k⌉ شیء دارد.
دستهها را از نتیجهٔ مطلوب بساز
برای تضمین دو عدد همنهشت پیمانهٔ ۴، چهار باقیماندهٔ ۰،۱،۲،۳ را لانه بگیر. از میان هر ۵ عدد صحیح، دو عدد در یک لانه میافتند.
- خروجی را پیش از فرمول تعریف کردهام.
- ترتیب و تکرار را روشن کردهام.
- دوبارهشماری را با یکتایی یا شمول کنترل کردهام.