چنانچه محفل ریاضی را سودمند یافتید، لطفا برای حمایت از ما به کانال تلگرامی محفل ریاضی بپیوندید!
به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
1,086 بازدید
سوال شده در دبیرستان و دانشگاه توسط 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$ است.(به کمک معادله و تعیین علامت)

لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
62 نفر آنلاین
0 عضو و 62 مهمان در سایت حاضرند
بازدید امروز: 3251
بازدید دیروز: 6817
بازدید کل: 4712392
...