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