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

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

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 هرچه باشد پرانتز بالا متناهی است ولی بسط تیلور نامتناهی و طبعا باید مقداری اختلاف با جواب واقعی وجود داشته باشد چرا این مقدار همیشه از یک کمتر است بطوریکه استفاده از جزء صحیح ما را به جواب دقیق می رساند؟این که مقدار خطا کوچیکه به صورت شهودی قابل درکه ولی اصلا چرا همیشه از مقدار واقعی بیشتره که جزء صحیح مارو به جواب می رسونه چرا کمتر از جواب واقعی نیست؟ و دیگه این که آیا با اطمینان کامل میشه گفت روش هایی از این قبیل درست هستند یا نه؟

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

1 پاسخ

+1 امتیاز
پاسخ داده شده توسط

همونطوری که @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!} $$
به محفل ریاضی ایرانیان خوش آمدید!
کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
حمایت مالی
...