به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
0 امتیاز
1,994 بازدید
در دبیرستان و دانشگاه توسط amirabbas (1,345 امتیاز)

مسئله زیر را درنظر بگیرید:

n نفر به چند حالت قادر هستند ماشین های خود را با هم عوض کنند به صورتی که ماشین هیچ کس دست خودش نباشد؟

پس از استفاده از اصل شمول و عدم شمول پاسخ زیر حاصل می شود:

$$ n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! + ... + \binom{n}{n} $$

با بسط دادن عبارت بالا و فاکتور گیری از $n!$ خواهیم داشت:

$$ n!(1 - \frac{1}{1!} + \frac{1}{2!} + ... + \frac{1}{n!}) $$

با توجه به بسط مک لورن $e^x$ در برخی کتب مقدار بالا را با مقدار زیر جایگزین می کنند:

$$ [n!e^{-1}] = [\frac{n!}{e}] $$

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

جالب اینه که به دلیلی که نمی دونم درست میشه.مشکل اینجاست که n هرچه باشد پرانتز بالا متناهی است ولی بسط تیلور نامتناهی و طبعا باید مقداری اختلاف با جواب واقعی وجود داشته باشد چرا این مقدار همیشه از یک کمتر است بطوریکه استفاده از جزء صحیح ما را به جواب دقیق می رساند؟این که مقدار خطا کوچیکه به صورت شهودی قابل درکه ولی اصلا چرا همیشه از مقدار واقعی بیشتره که جزء صحیح مارو به جواب می رسونه چرا کمتر از جواب واقعی نیست؟ و دیگه این که آیا با اطمینان کامل میشه گفت روش هایی از این قبیل درست هستند یا نه؟

توسط Under sky (595 امتیاز)
مرجع این مثالی که مطرح کردین کدوم کتاب هست؟
توسط amirabbas (1,345 امتیاز)
ویرایش شده توسط amirabbas
+1
@Under sky
مسئله توزیع اشیا در کتاب ریاضیات گسسته و ترکیبیاتی گریمالدی انتشارات فاطمی جلد دوم فصل شمول و عدم شمول با روشی شبیه این حل شده و فرمول مسیر های گراف هم در اکثر کتاب های گسسته پیش دانشگاهی به عنوان نکته ذکر میشه.در کتاب گریمالدی گفته اینکار تقریب خوبیه (برای مسئله اول) اما فرمول دوم رو به ما به عنوان جواب گفتن و نه تقریب و البته بعضی موارد جواب درست نیست و لی اگه عدد e رو با ارقام اعشار بیشتری جایگزین کنیم جواب درست میشه.
توسط fardina (17,622 امتیاز)
+3
اینجا رو ببینید: http://math.irancircle.com/3600
توسط amirabbas (1,345 امتیاز)
خیلی ممنون متوجه شدم.

1 پاسخ

+1 امتیاز
توسط amirabbas (1,345 امتیاز)

همونطوری که @erfanm درhttp://math.irancircle.com/3600 مسئله ی تعداد مسیر های گراف رو حل کردن، میتونیم ثابت کنیم که در مسئله توزیع ماشین ها مقدار اختلاف سری $e^x$ با جواب واقعی کمتر از یک است پس می توانیم با استفاده از جزء صحیح جواب را بدست آوریم.

$$ n!e^{-1} = n!\sum_{i=0}^n \frac{(-1)^i}{i!} + n!\sum_{j=n+1}^\infty \frac{(-1)^j}{j!} $$

میدانیم اولین عبارت عددی صحیح است. پس ثابت می کنیم عبارت دوم کمتر از یک است:

$$ n!\sum_{j=n+1}^\infty \frac{(-1)^j}{j!} = \frac{1}{n+1} - \frac{1}{(n+1)(n+2)} + ... < \frac{1}{n} + \frac{1}{n^2} + ... $$

حد مجموع دنباله هندسی بدست آمده برابر با $S_\infty = \frac{1}{n-1}$ است که واضح است به ازای $n > 2$ کوچک تر از واحد است.

پس:

$$ [n!e^{-1}] = n!\sum_{i=0}^n \frac{(-1)^i}{i!} $$
بزرگترین ریاضیدانان، همچون ارشمیدس، نیوتن و گاوس، همواره نظریه و کاربردها را در اندازه ی یکسان در هم می آمیزند.
...