محاسبه فاکتوریل

راهنمای استفاده از محاسبه فاکتوریل

1. عدد صحیح نامنفی (تا ۵۰۰۰) را وارد کنید.
2. نتیجهٔ کامل، تعداد ارقام و صفرهای انتهایی نمایش داده می‌شود.
3. برای اعداد بزرگ، نتیجه را کپی کنید.

محاسبه فاکتوریل؛ تعریف و نماد

فاکتوریل یک عدد صحیح مثبت، حاصل‌ضرب همهٔ عددهای صحیح از ۱ تا همان عدد است. نماد آن علامت تعجب پس از عدد است: ۵! که پنج فاکتوریل خوانده می‌شود، برابر ۱ ضرب در ۲ ضرب در ۳ ضرب در ۴ ضرب در ۵، یعنی ۱۲۰ است. فاکتوریل را می‌شود به شکل بازگشتی هم تعریف کرد: هر فاکتوریل، خود عدد ضرب در فاکتوریل عدد قبلی است. ۶! برابر ۶ ضرب در ۵!، یعنی ۷۲۰ است. این رابطه، هم برای محاسبهٔ دستی و هم برای برنامه‌نویسی، پایهٔ کار با فاکتوریل است.

فاکتوریل‌ها با سرعتی سرسام‌آور بزرگ می‌شوند. ۱۰! حدود ۳٫۶ میلیون است، ۱۳! از ۶ میلیارد می‌گذرد و ۲۰! عددی ۱۹ رقمی است. ۷۰! نخستین فاکتوریلی است که از یک گوگول، یعنی ۱ با صد صفر، بزرگ‌تر است. رشد فاکتوریل از رشد توانی، مثل ۲ به توان n، هم سریع‌تر است و همین رشد سریع، دلیل اصلی اهمیت آن در علوم کامپیوتر است: الگوریتمی که زمان اجرایش با فاکتوریل رشد کند، برای ورودی‌های کمی بزرگ عملا اجرا نمی‌شود.

چرا فاکتوریل صفر یک است؟

بسیاری از دانش‌آموزان انتظار دارند ۰! صفر باشد، اما برابر یک است. ساده‌ترین توضیح، معنای شمارشی فاکتوریل است: n! تعداد راه‌های چیدن n شیء متفاوت در یک ردیف است. سه کتاب را به ۶ روش می‌شود چید، که همان ۳! است. صفر کتاب را به چند روش می‌شود چید؟ دقیقا یک روش: قفسهٔ خالی. توضیح دوم، رابطهٔ بازگشتی است: ۱! برابر ۱ ضرب در ۰! است و چون ۱! یک است، ۰! هم باید یک باشد. این تعریف، فرمول‌های جایگشت و ترکیب را هم در حالت‌های مرزی درست نگه می‌دارد.

ابزار عددهای بزرگ را چطور دقیق حساب می‌کند؟

ماشین حساب‌های معمولی، از جمله ماشین حساب آنلاین همین سایت، عددها را به شکل اعشاری با حدود پانزده تا هفده رقم معنادار ذخیره می‌کنند. با این روش، بزرگ‌ترین فاکتوریل قابل نمایش ۱۷۰! است که حدود ۷٫۲۶ ضرب در ده به توان ۳۰۶ است. ۱۷۱! از بزرگ‌ترین عدد این روش بیشتر است و بی‌نهایت نمایش داده می‌شود. حتی پیش از آن، از ۲۱! به بعد، ماشین حساب معمولی رقم‌های آخر را گرد می‌کند و نمی‌تواند همهٔ رقم‌ها را دقیق نشان دهد.

این ابزار به جای آن، با عددهای صحیح بزرگ کار می‌کند؛ روشی که در آن، عدد هر قدر هم بزرگ باشد، همهٔ رقم‌هایش نگه داشته می‌شوند. برای همین، ۱۰۰! را با همهٔ ۱۵۸ رقمش و ۵۰۰۰! را با همهٔ ۱۶٬۳۲۶ رقمش دقیق نشان می‌دهد. سقف ۵۰۰۰ برای این است که مرورگر شما کند نشود؛ حاصل‌های بزرگ‌تر، صفحه را با ده‌ها هزار رقم پر می‌کنند که کاربرد عملی کمی دارند. محاسبه کاملا در مرورگر شما انجام می‌شود.

شمردن صفرهای انتهایی بدون ضرب کردن

صفرهای انتهای یک عدد، از ضرب ۱۰ می‌آیند و هر ۱۰ از یک ۲ و یک ۵. در حاصل‌ضرب ۱ تا n، عامل ۲ همیشه بیشتر از عامل ۵ است؛ پس تعداد صفرهای انتهایی، همان تعداد عامل‌های ۵ است. برای شمردن آن، n را بر ۵ تقسیم می‌کنیم، که تعداد مضرب‌های ۵ را می‌دهد. اما مضرب‌های ۲۵ دو عامل ۵ دارند؛ پس n را بر ۲۵ هم تقسیم می‌کنیم و اضافه می‌کنیم. همین را برای ۱۲۵، ۶۲۵ و توان‌های بعدی ۵ ادامه می‌دهیم. به این روش، فرمول لژاندر می‌گویند.

برای ۱۰۰!، ۱۰۰ تقسیم بر ۵ برابر ۲۰ و ۱۰۰ تقسیم بر ۲۵ برابر ۴ است؛ ۱۲۵ از ۱۰۰ بزرگ‌تر است و ادامه نمی‌دهیم. پس ۱۰۰! دقیقا ۲۴ صفر در انتها دارد. برای ۱۰۰۰!، ۲۰۰ به علاوهٔ ۴۰ به علاوهٔ ۸ به علاوهٔ ۱، یعنی ۲۴۹ صفر. ابزار همین عدد را در کاشی صفرهای انتهایی نشان می‌دهد و می‌توانید آن را با شمردن صفرهای آخر حاصل کامل، بررسی کنید. این سؤال یکی از سؤال‌های محبوب مسابقه‌های ریاضی و مصاحبه‌های برنامه‌نویسی است.

جایگشت؛ وقتی ترتیب مهم است

فاکتوریل در شمارش، جایی که بپرسیم چند حالت وجود دارد، بیشترین کاربرد را دارد. تعداد راه‌های چیدن n شیء متفاوت در یک ردیف، n! است. پنج کتاب متفاوت را به ۱۲۰ روش می‌شود در قفسه چید. ده نفر را به ۳٬۶۲۸٬۸۰۰ روش می‌شود در صف ایستاند. یک دسته ورق ۵۲ تایی را به ۵۲! روش می‌شود بر زد؛ عددی ۶۸ رقمی، آن‌قدر بزرگ که تقریبا مطمئنیم هیچ دو بار بر زدن خوبی در تاریخ، یک ترتیب نداشته‌اند.

اگر فقط k شیء از n شیء را بچینیم، تعداد حالت‌ها n! تقسیم بر (n − k)! است که به آن جایگشت k از n می‌گویند. برای تعیین نفرهای اول تا سوم یک مسابقهٔ ده‌نفره، ۱۰! تقسیم بر ۷!، یعنی ۱۰ ضرب در ۹ ضرب در ۸ که ۷۲۰ حالت است. در این محاسبه‌ها، لازم نیست هر دو فاکتوریل را کامل حساب کنید؛ بیشتر جمله‌ها خط می‌خورند.

ترکیب؛ وقتی ترتیب مهم نیست

اگر ترتیب مهم نباشد، مثل انتخاب سه نفر از ده نفر برای یک گروه، هر گروه سه‌نفره در جایگشت‌ها ۳! بار، یعنی ۶ بار، شمرده شده است. پس تعداد ترکیب‌ها، ۷۲۰ تقسیم بر ۶، یعنی ۱۲۰ است. فرمول کلی ترکیب، n! تقسیم بر حاصل‌ضرب k! و (n − k)! است. ترکیب پایهٔ محاسبهٔ احتمال در بسیاری از مسئله‌هاست؛ مثلا تعداد راه‌های انتخاب ۶ عدد از ۴۹ عدد، ۱۳٬۹۸۳٬۸۱۶ است و احتمال درست حدس زدن هر شش عدد، یک در همین تعداد.

قاعدهٔ ساده برای انتخاب میان این دو: اگر جابه‌جا کردن انتخاب‌ها حالت تازه‌ای بسازد، جایگشت؛ اگر نه، ترکیب. رمز سه‌رقمی، جایگشت است، چون ۱۲۳ با ۳۲۱ فرق دارد. انتخاب سه درس از ده درس اختیاری، ترکیب است. در کنکور، بیشتر سؤال‌های شمارش با تشخیص درست همین دو حالت حل می‌شوند.

فاکتوریل در احتمال و آمار

در آمار و احتمال، فاکتوریل در فرمول توزیع دوجمله‌ای، توزیع پواسون و بسیاری دیگر ظاهر می‌شود. برای نمونه، احتمال اینکه از ده بار پرتاب سکهٔ سالم، دقیقا سه بار شیر بیاید، ترکیب ۳ از ۱۰ ضرب در نیم به توان ۱۰ است؛ یعنی ۱۲۰ تقسیم بر ۱۰۲۴ که حدود ۱۱٫۷ درصد است. هر جا در فرمولی، نماد ترکیب یا جایگشت دیدید، فاکتوریل پشت آن است. برای توان‌های بزرگ در این فرمول‌ها، ماشین حساب توان عددهای دقیق را نشان می‌دهد.

فرمول استرلینگ؛ تخمین فاکتوریل‌های بزرگ

برای عددهای بزرگ، فاکتوریل را می‌شود با فرمول استرلینگ تخمین زد: جذر دو پی n، ضرب در n تقسیم بر e به توان n. این فرمول برای ۱۰! حدود ۳٬۵۹۸٬۶۹۶ می‌دهد که کمتر از یک درصد با مقدار دقیق ۳٬۶۲۸٬۸۰۰ فاصله دارد و هرچه n بزرگ‌تر شود، خطای نسبی آن کمتر می‌شود. فرمول استرلینگ در فیزیک آماری و تحلیل الگوریتم‌ها، جایی که فاکتوریل‌های بسیار بزرگ ظاهر می‌شوند، ابزار اصلی است. با لگاریتم گرفتن از آن، می‌شود تعداد رقم‌های فاکتوریل را بدون محاسبهٔ کامل آن تخمین زد.

فاکتوریل عدد اعشاری و منفی

فاکتوریل به معنای حاصل‌ضرب، فقط برای عددهای صحیح نامنفی معنا دارد. اما ریاضیدانان تابعی به نام گاما ساخته‌اند که فاکتوریل را به عددهای اعشاری گسترش می‌دهد؛ گامای n به علاوهٔ یک، برای عددهای صحیح همان n! است. با این تعریف، نیم فاکتوریل حدود ۰٫۸۸۶ است که برابر جذر پی تقسیم بر دو است. تابع گاما برای عددهای صحیح منفی تعریف نمی‌شود. این ابزار فقط فاکتوریل عددهای صحیح را حساب می‌کند و برای عدد اعشاری یا منفی، پیام راهنما نشان می‌دهد.

فاکتوریل در برنامه‌نویسی

فاکتوریل یکی از نخستین مثال‌هایی است که در آموزش بازگشت و حلقه در برنامه‌نویسی به کار می‌رود. نکتهٔ مهم برای برنامه‌نویسان، سرریز است: در بسیاری از زبان‌ها، عدد صحیح ۳۲ بیتی فقط تا ۱۲! و عدد صحیح ۶۴ بیتی فقط تا ۲۰! را درست نگه می‌دارد و پس از آن، بی‌صدا عدد نادرست تولید می‌کند. اگر برنامهٔ شما فاکتوریل حساب می‌کند، خروجی آن را با این ابزار مقایسه کنید؛ اختلاف در رقم‌ها، نشانهٔ سرریز یا گرد شدن است. برای کار با عددهای بزرگ، از نوع دادهٔ عدد صحیح بزرگ که در بیشتر زبان‌ها هست استفاده کنید.

خواندن نتیجه و کپی کردن

برای فاکتوریل‌های بزرگ، حاصل کامل در کادری با شکست خط و نوار پیمایش نمایش داده می‌شود تا صفحه افقی کش نیاید و بلندی آن از اندازه بیرون نزند. دکمه‌های آماده‌ای هم زیر کادر عدد هست که ۵!، ۱۰!، ۲۰!، ۵۰!، ۱۰۰! و ۱۰۰۰! را با یک لمس حساب می‌کنند. نماد علمی، شش رقم اول و توان ده را نشان می‌دهد؛ برای ۲۵!، یعنی ۱٫۵۵۱۱۲ ضرب در ده به توان ۲۵. اگر حاصل کامل را لازم دارید، دکمهٔ کپی همهٔ ارقام را بزنید؛ برای عددهای هزاران‌رقمی، این کار از انتخاب دستی بسیار مطمئن‌تر است. رقم‌ها بدون جداکنندهٔ هزارگان نوشته می‌شوند تا در برنامه‌ها و صفحه‌گسترده‌ها مستقیم قابل استفاده باشند.

نمونه‌های شمارش از زندگی روزمره

فاکتوریل در جاهایی ظاهر می‌شود که انتظارش را نداریم. خانواده‌ای شش‌نفره که می‌خواهند هر شب با ترتیب نشستن متفاوتی دور میز شام بنشینند، ۶! یعنی ۷۲۰ ترتیب دارند؛ نزدیک به دو سال شام بی‌تکرار. اگر میز گرد باشد و فقط جای نسبی افراد مهم باشد، تعداد ترتیب‌ها ۵!، یعنی ۱۲۰ است، چون چرخاندن همه دور میز ترتیب تازه‌ای نمی‌سازد. معلمی که می‌خواهد ترتیب ارائهٔ هشت گروه را مشخص کند، ۸! یعنی ۴۰٬۳۲۰ انتخاب دارد. فروشنده‌ای که باید به ده مشتری در ده آدرس سر بزند، ۱۰! یعنی بیش از سه و نیم میلیون مسیر ممکن دارد و برای همین، پیدا کردن کوتاه‌ترین مسیر با امتحان همهٔ حالت‌ها، حتی برای رایانه، در تعداد مشتری بیشتر عملا ناممکن می‌شود.

این نمونه‌ها نشان می‌دهند چرا فاکتوریل در طراحی الگوریتم و برنامه‌ریزی، مرز میان ممکن و ناممکن است. برای ۱۰ آدرس، رایانه همهٔ مسیرها را در کسری از ثانیه بررسی می‌کند. برای ۲۰ آدرس، تعداد مسیرها حدود ۲٫۴ میلیارد میلیارد است و بررسی همه، حتی با سریع‌ترین رایانه‌ها، سال‌ها طول می‌کشد. به همین دلیل، برای این مسئله‌ها روش‌های تقریبی به کار می‌رود.

رمزها و تعداد حالت‌ها

وقتی می‌پرسیم یک رمز چقدر امن است، در واقع تعداد حالت‌های ممکن را می‌شماریم. اگر رمز، ترتیبی از چند نویسهٔ متفاوت بدون تکرار باشد، جایگشت و فاکتوریل به کار می‌آیند. اما بیشتر رمزها تکرار نویسه را مجاز می‌دانند و آنجا تعداد حالت‌ها با توان حساب می‌شود، نه فاکتوریل؛ رمز چهاررقمی عددی ۱۰ به توان ۴، یعنی ۱۰٬۰۰۰ حالت دارد. دانستن اینکه کدام فرمول به کار می‌رود، همان تشخیص میان با تکرار و بدون تکرار است. برای ساختن رمزهای امن، ساخت رمز عبور را ببینید.

فاکتوریل‌های دوگانه و ساده‌سازی کسرها

در برخی کتاب‌ها، نماد دو علامت تعجب هم دیده می‌شود که به آن فاکتوریل دوگانه می‌گویند و فقط عددهای یک در میان را ضرب می‌کند؛ ۷!! یعنی ۷ ضرب در ۵ ضرب در ۳ ضرب در ۱ که ۱۰۵ است. این با فاکتوریلِ فاکتوریل فرق دارد و این ابزار آن را حساب نمی‌کند. نکتهٔ کاربردی‌تر، ساده کردن کسرهای فاکتوریلی پیش از محاسبه است. ۱۰۰! تقسیم بر ۹۸!، با وجود اینکه هر دو عدد بیش از ۱۵۰ رقم دارند، فقط ۱۰۰ ضرب در ۹۹، یعنی ۹۹۰۰ است. در سؤال‌های امتحانی، همیشه پیش از ضرب، فاکتوریل بزرگ‌تر را تا رسیدن به فاکتوریل کوچک‌تر باز کنید و جمله‌های مشترک را خط بزنید.

اشتباه‌های رایج

اشتباه اول، صفر دانستن ۰! است. اشتباه دوم، اعتماد به رقم‌های آخر ماشین حساب معمولی برای فاکتوریل‌های بزرگ‌تر از ۲۰. اشتباه سوم، شمردن صفرهای انتهایی فقط با n تقسیم بر ۵ و فراموش کردن ۲۵ و ۱۲۵؛ برای ۱۰۰!، این اشتباه ۲۰ به جای ۲۴ می‌دهد. اشتباه چهارم، به کار بردن جایگشت جایی که ترتیب مهم نیست، که پاسخ را k! بار بزرگ‌تر از واقع می‌کند.

ابزارهای مرتبط

برای تجزیهٔ عددها به عامل‌های اول و بررسی اول بودن، تشخیص عدد اول و برای بزرگ‌ترین مقسوم‌علیه مشترک، ب.م.م و ک.م.م را ببینید. بقیهٔ ابزارها در ابزارهای ریاضی آمده‌اند.