در شکل روبهرو چند مسیر از A به B وجود دارد که از C میگذرد ولی از D نمی گذرد؟(در طول مسیر فقط میتوان به سمت راست یا بالا حرکت کرد.)
پاسخ
گزینه (۵) درست است.
در یک شبکه m×n برای رفتن از گوشهی سمت چپ و پایین به گوشه سمت راست و بالا با شرایط مسئله(جهت حرکت فقط به سمت راست یا بالا)(m+n)!m!n! مسیر وجود دارد. زیرا اگر حرکت به سمت بالا را با U و حرکت به سمت راست با R نمایش دهیم تعداد مسیرها برابر با تعداد حالات چیدن m عدد U و n عدد R در پیش همدیگر میباشد که برابر با (m+n)!m!n! میباشد. در این مسئله از C به B مجموعا 11!4!7! مسیر و از A به C مجموعا 3!2!1! مسیر وجود دارد. همینطور تعداد مسیرهای موجود بین C و D برابر با 6!2!4! و تعداد مسیر بین D و B برابر با 5!2!3! میباشد. لذا تعداد مسیرها با شرایط مسئله برابر خواهد بود با:
3!2!1!×[11!4!7!−5!2!3!×6!2!4!]=540