به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
0 امتیاز
374 بازدید
در دبیرستان و دانشگاه توسط amirabbas

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

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
مرجع این مثالی که مطرح کردین کدوم کتاب هست؟
توسط amirabbas
ویرایش شده توسط amirabbas
+1
@Under sky
مسئله توزیع اشیا در کتاب ریاضیات گسسته و ترکیبیاتی گریمالدی انتشارات فاطمی جلد دوم فصل شمول و عدم شمول با روشی شبیه این حل شده و فرمول مسیر های گراف هم در اکثر کتاب های گسسته پیش دانشگاهی به عنوان نکته ذکر میشه.در کتاب گریمالدی گفته اینکار تقریب خوبیه (برای مسئله اول) اما فرمول دوم رو به ما به عنوان جواب گفتن و نه تقریب و البته بعضی موارد جواب درست نیست و لی اگه عدد e رو با ارقام اعشار بیشتری جایگزین کنیم جواب درست میشه.
توسط fardina
+3
اینجا رو ببینید: http://math.irancircle.com/3600
توسط amirabbas
خیلی ممنون متوجه شدم.

1 پاسخ

+1 امتیاز
توسط amirabbas

همونطوری که @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!} $$

سال نو مبارک!


حمایت مالی


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