به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
1,238 بازدید
سوال شده در دبیرستان و دانشگاه توسط OXIDE

ثابت کنید درگراف کامل $K_p$ بین دو راس دلخواه به تعداد $[(p-2)!e]$ مسیر وجود دارد.

1 پاسخ

+5 امتیاز
پاسخ داده شده توسط erfanm
ویرایش شده توسط erfanm

در سوال باید داشته باشیم که $p \geq 3 $ چون اگر$ p=2 $ فقط $1$ مسیر داریم اما حاصل جز صحیح برابر $2$ می شود.

ابتدا تعداد مسیرهای موجود به طول $k$ برابر است با اینکه ما غیر از دوراس دلخواه انتخاب شده $ k-1 $ راس دیگر را در بین رئوس باقیمانده انتخاب کنیم و به هر ترتیبی که این رئوس را بین دو راس اولیه قرار دهیم یک مسیر بین دو راس اولیه بدست می آید لذا تعداد حالات برابر است با ${p-2 \choose{k-1} }(k-1)! $

پس تعداد کل مسیرها با طولهای دلخواه بین دو راس دلخواه اولیه برابر است با: $ \sum_{k=1}^{p-1} {p-2 \choose{k-1} }(k-1)! $ یا با لغزاندن اندیس ها داریم $ \sum_{k=0}^{p-2} {p-2 \choose{k} }(k)! $ که داریم:

$$ \sum_{k=0}^{p-2} {p-2 \choose{k} }(k)! =\sum_{k=0}^{p-2} \frac{(p-2)!}{(p-2-k)!} =(p-2)! \sum_{k=0}^{p-2} \frac{1}{(p-2-k)!} =(p-2)! \sum_{j=0}^{p-2} \frac{1}{j!}$$

دقت کنید $(p-2)! \sum_{j=0}^{p-2} \frac{1}{j!}$ همان $\sum_{k=0}^{p-2} {p-2 \choose{k} }(k)! $ است پس یکعدد صحیح است(بعدا که با جز صحیح کار داریم از این نکته استفاده می شود)

توجه کنید $ e^{x} = \sum_{j=0}^ \infty \frac{ x^{k} }{j!} $پس اگر قرار دهیم $x=1$ آنگاه $ e = \sum_{j=0}^ \infty \frac{ 1 }{j!} $

پس $$(p-2)!e= (p-2)! \sum_{j=0}^{p-2} \frac{1}{j!}+(p-2)! \sum_{j=p-1}^ \infty \frac{ 1 }{j!} $$ که اگر نشان دهیم $(p-2)! \sum_{j=p-1}^ \infty \frac{ 1 }{j!} < 1 $ آنگاه $[(p-2)!e]=(p-2)! \sum_{j=0}^{p-2} \frac{1}{j!}$ و حکم ثابت می شود

$(p-2)! \sum_{j=p-1}^ \infty \frac{ 1 }{j!} < \frac{1}{p-1} + \frac{1}{(p-1)p} + \frac{1}{(p-1)p(p+1)}+... < \frac{1}{p-1} + \frac{1}{(p-1)p} + \frac{1}{(p-1)p^2} +... $ که آخری دنباله ای هندسی با جمله اول $ \frac{1}{p-1} $ و قدر نسبت $\frac{1}{p}$ است که حد مجموع آن برابر است با $$ \frac{ \frac{1}{p-1}}{1- \frac{1}{p}} = \frac{p}{ (p-1)^{2} } $$ که برای $p \geq 3 $ عبارت کمتر از $1$ است.(به کمک معادله و تعیین علامت)

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...