[/b][/size]
با سلام به همه
پاسخ سریع به این سوال موجب آرامش و شادی روح من خواهد شد !!
سوال: فرض کنیم گرافی با ویژگیهای زیر داشته باشیم.
G=(V,E) & E={(i,j)|1<=i<j<=7} & V={1,2,3,4,5,6,7
کلا در این گراف چند مسیرجهتدار از ۱ به ۷ وجود دارد؟
ببینید جهت حرکت ما باید از اعداد کوچکتر به اعداد بزرگتر باشه چون مثلا نمیتونیم از ۳ به ۲ بریم. (به خاطر جهت دار بودن یالها و توضیحات سوال)
مسیر به طول ا: فقط همین ۱ حالت وجود داره. [tex]\binom{5}{0}=1[/tex]
[tex]1\rightarrow 7[/tex]
مسیر به طول ۲ یعنی باید از بین ۵ راس باقیمانده (۲و۳و۴و۵و۶) یکی را انتخاب کنیم. [tex]\binom{5}{1}=5[/tex] مثلا اگر ۲ را انتخاب کنیم:
[tex]1\rightarrow 2\rightarrow 7[/tex]
مسیر به طول ۳ یعنی [tex]\binom{5}{2}=15[/tex] ترتیبش مهم نیست چون یک حالت چینش بیشتر نداریم آن هم به صورت صعودی است. مثلا اگر ۲و۳ را انتخاب کنیم:
[tex]1 \rightarrow 2 \rightarrow 3 \rightarrow 7[/tex]
مسیر به طول ۴:
[tex]\binom{5}{3}=10[/tex]
[tex]1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 7[/tex]
مسیر به طول ۵:
[tex]\binom{5}{4}=5[/tex]
[tex]1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 7[/tex]
مسیر به طول ۶:
[tex]\binom{5}{5}=1[/tex]
[tex]1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 6\rightarrow 7[/tex]
که جمعش میشه [tex]2^{5}=32[/tex]