−فهرست مندرجات

فاکتوریل
نظرات

فاکتوریل

در این صفحه با نماد فاکتوریل آشنا می‌شوید. این نماد، کاربردهای بسیاری در ترکیبیات، به ویژه در ترکیبیات شمارشی دارد.

تعریف

فرض کنید $n$ یک عدد طبیعی باشد. عدد $n!$ ( $n$ فاکتوریل) به صورت زیر تعریف می‌شود: $n! = n \times (n-1) \times (n-2) \times ... \times 1$

برای مثال: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

برای $n=0$ نیز این نماد تعریف می‌شود و به طور قراردادی، $0!=1$ در نظر گرفته می‌شود. این قرارداد شاید در ابتدا عجیب و بیهوده به نظر بیاید، اما انگیزه‌های بسیاری برای تعریف آن وجود دارد که می‌توانید در یک پله بالاتر ببینید.

نماد فاکتوریل تنها به اعداد صحیح نامنفی محدود نمی‌شود و برای دیگر اعداد حقیقی و حتی اعداد غیر حقیقی تعریف می‌شود که می‌توانید در یک پله بالاتر با آن‌ها آشنا شوید.

در جدول زیر می‌توانید چند فاکتوریل ابتدایی را ببینید.

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
11	39916800
12	479001600
13	6227020800
14	87178291200
15	1307674368000

همان طور که مشاهده می‌کنید، با بزرگ شدن $n$ ، $n!$ رشد بسیاری بالایی دارد.

مثال: درستی یا نادرستی هر یک از موارد زیر را مشخص کنید:

$(m+n)!=m!+n!$
$(mn)!=m! \times n!$

پاسخ

به ازای $m=n=2$ ، هر دو عبارت داده شده، نادرست می‌شود. پس هر دو عبارت نادرست هستند.

مثال: عبارات زیر را با نماد فاکتوریل، ساده‌تر بنویسید:

$(n+1) \times (n+2) \times ... \times (2n)$
$2 \times 4 \times ... \times (2n)$
$1 \times 3 \times ... \times (2n-1)$

پاسخ

عبارت بالا را در

$\frac{n!}{n!}$ ضرب می‌کنیم. پس: $(n+1) \times (n+2) \times ... \times (2n)!$ $=(n+1) \times (n+2) \times ... \times (2n)! \times \frac{n!}{n!}$ $=\frac{1 \times 2 \times ... \times (2n)}{n!}$ $=\frac{(2n)!}{n!}$

کافی است به جای هر $2i$ ، $2 \times i$ بنویسیم.

$2 \times 4 \times ... \times (2n)$ $=(2 \times 1)(2 \times 2)...(2 \times n)$ $=2^n \times n!$

عبارت قسمت ۲ را $S$ می‌نامیم. عبارت داده شده را در $\frac{S}{S}$ ضرب می‌کنیم. داریم:

$1 \times 3 \times ... \times (2n-1)$ $=1 \times 3 \times ... \times (2n-1) \times \frac{2 \times 4 \times ... \times (2n)}{2 \times 4 \times ... \times (2n)}$ $=\frac{(2n)!}{2^n \times n!}$

فاکتوریل به صورت بازگشتی

با استفاده از تعریف فاکتوریل، نتیجه می‌شود: $n! = n \times (n-1)!$

عبارت بالا، یک رابطه‌ی بازگشتی برای $n!$ است. روابط بازگشتی دیگری نیز می‌توان برای $n!$ نوشت.

مثال: ثابت کنید: $n! = (n-1)\big((n-1)! + (n-2)!\big)$

پاسخ

$(n-1)\big((n-1)! + (n-2)!\big)$ $=(n-1) \times (n-1)! + (n-1) \times (n-2)!$ $=(n-1) \times (n-1)! + (n-1)!$ $=(n-1)! \times (n-1 + 1)$ $=n\times (n-1)!$ $=n!$

چند مثال

مثال: فرض کنید $n, r$ اعدادی طبیعی باشند که $r < n$ . ثابت کنید: . ثابت کنید: $\frac{n!}{r! \times (n-r)!} = \frac{(n-1)!}{r! \times (n-r-1)!} + \frac{(n-1)!}{(r-1)! \times (n-r)!}$

پاسخ

$\frac{(n-1)!}{r! \times (n-r-1)!} + \frac{(n-1)!}{(r-1)! \times (n-r)!}$ $=\frac{(n-1)! \times \big(n-r + r \big)}{r! \times (n-r)!}$ $=\frac{n!}{r! \times (n-r)!}$

توضیح: این رابطه در مباحث بعدی، بیش‌تر بررسی خواهد شد.

مثال: ثابت کنید توان عامل $k$ در تجریه‌ی $n!$ به عوامل اول، $\Big\lfloor \frac{n}{k} \Big\rfloor + \Big\lfloor \frac{n}{k^2} \Big\rfloor + \Big\lfloor \frac{n}{k^3} \Big\rfloor + ...$ است. سپس تعداد ارقام صفر سمت راست عدد $200!$ را به دست بیاورید.

پاسخ

هر عددی از اعداد $1, 2, ..., n$ که بر $k$ بخش‌پذیر هستند، یک عامل $k$ می‌سازد که $\Big\lfloor \frac{n}{k} \Big\rfloor$ آن‌ها را می‌شمارد. هر عددی نیز که بر $k^2$ بخش‌پذیر است، دو عامل $k$ می‌سازد که یکی از آن‌ها در $\Big\lfloor \frac{n}{k} \Big\rfloor$ شمرده شده است و دیگری در

$\Big\lfloor \frac{n}{k^2} \Big\rfloor$ شمرده می‌شود. برای دیگر توان‌های $k$ نیز، به همین ترتیب جلو می‌رویم و حکم اثبات می‌شود.

حال تعداد ارقام صفر سمت راست عدد $200!$ را محاسبه می‌کنیم. باید تعداد عامل‌های ۲ و ۵ را بشماریم. واضح است که توان عامل ۵ کم‌تر از توان عامل ۲ است. پس کافی است توان عامل ۵ را بشماریم. توان عامل ۵ برابر است با: $\Big\lfloor \frac{200}{5} \Big\rfloor + \Big\lfloor \frac{200}{25} \Big\rfloor + \Big\lfloor \frac{200}{125} \Big\rfloor$ $=40 + 8 + 1 = 49$

مثال: ثابت کنید: $1 \times 1! + 2 \times 2! + ... + n \times n! = (n+1)! - 1$

راهنمایی

ابتدا ثابت کنید: $k \times k! = (k+1)! - k!$

پاسخ

ابتدا ثابت می‌کنیم: $k \times k! = (k+1)! - k!$ داریم: $k \times k! = k \times k! + k! - k!$ $=(k+1) \times k! - k! = (k+1)! - k!$ حال حکم اصلی را ثابت می‌کنیم: $1 \times 1! + 2 \times 2! + ... + n \times n!$ $=2! - 1! + 3! - 2! + 4! - 3! + ... + (n+1)! - n!$ $=(n+1)! - 1$

مثال: ثابت کنید: $\frac{1}{(1+1)!} + \frac{2}{(2 + 1)!} + ... + \frac{n}{(n + 1)!}=1 - \frac{1}{(n+1)!}$

راهنمایی

ابتدا ثابت کنید: $\frac{k}{(k+1)!} = \frac{1}{k!} - \frac{1}{(k+1)!}$

پاسخ

ابتدا ثابت می‌کنیم: $\frac{k}{(k+1)!} = \frac{1}{k!} - \frac{1}{(k+1)!}$ داریم: $\frac{1}{k!} - \frac{1}{(k+1)!} = \frac{(k+1)-1}{(k+1)!} = \frac{k}{(k+1)!}$ حال حکم اصلی را ثابت می‌کنیم: $\frac{1}{(1+1)!} + \frac{2}{(2 + 1)!} + ... + \frac{n}{(n + 1)!}$ $=\frac{1}{1!} - \frac{1}{2!} + \frac{1}{2!} - \frac{1}{3!} + ... + \frac{1}{n!} - \frac{1}{(n+1)!}$ $=1 - \frac{1}{(n+1)!}$

یک پله بالاتر

انگیزه‌های تعریف $0!$

قراردادن مقدار ۱ برای $0!$ ، انگیزه‌ها و دلایل بسیاری داشته است که برخی از آن‌ها را به طور مختصر مشاهده می‌کنید:

تعداد جایگشت‌های خطی با ۰ عنصر، برابر با ۱ است، زیرا تنها یک حالت برای جایگشت دادن ۰ عنصر داریم (جایگشت خالی).
در فرمول ترکیب‌ $\binom{n}{r}$ ، به ازای $r=0$ و $r=n$ ، باید مقدار ۱ را ببینیم و این در حالی است که مقدار $0!$ در مخرج فرمول ظاهر می‌شود که اگر آن را برابر ۱ در نظر بگیریم، مشکل حل می‌شود.
در ریاضیات، مفهومی به نام ضرب تهی وجود دارد که با نوشتن فاکتوریل به صورت بازگشتی، ایجاب می‌کند $0!=1$ باشد.
فاکتوریل محدود به اعداد صحیح نامنفی نیست و به اعداد حقیقی و حتی اعداد مختلط، تعمیم داده می‌شود. با تعریفی که برای فاکتوریل، در این تعمیم داده می‌شود، $0!=1$ است. این تعمیم را در ادامه‌ی این صفحه خواهید دید.
در بسیاری از بسط‌های تیلور توابع، ضریب $0!$ ظاهر می‌شود. بسط‌های تیلور در صورتی درست کار می‌کنند که $0!=1$ باشد.

تعمیم به اعداد حقیقی و مختلط

به جز اعداد صحیح منفی، برای بقیه‌ی اعداد حقیقی مانند $x$ ، عدد $x!$ تعریف می‌شود. ابتدا تابع گاما را تعریف می‌کنیم. فرض کنید $x$ یک عدد حقیقی باشد. هم‌چنین فرض کنید $x$ یک عدد صحیح نامثبت نیست. در این صورت تابع $\Gamma (x)$ به صورت زیر تعریف می‌شود: $\Gamma (x) = \int_{0}^{\infty}t^{x-1}e^{-t}dt$ حال فرض کنید $x$ , یک عدد حقیقی باشد. هم‌چنین فرض کنید $x$ یک عدد صحیح منفی نیست. در این صورت $x!$ به صورت زیر تعریف می‌شود: $x! = \Gamma (x+1)$

نمودار تابع $y=x!$ را در شکل زیر مشاهده می‌کنید:

تابع گاما این خاصیت را دارد که: $\frac{\Gamma (n+1)}{\Gamma (n)} = n$ پس طبیعی است که تابع گاما برای $n=0$ تعریف نشود. وقتی برای $n=0$ تعریف نشود، برای $n=-1$ نیز تعریف نمی‌شود و به همین ترتیب برای دیگر اعداد صحیح نامثبت نیز تعریف نخواهد شد. پس نتیجه می‌شود تابع $x!$ برای اعداد صحیح منفی تعریف نشود.

با توجه به این که، تابع گاما این قابلیت را دارد که برای اعداد مختلط تعریف شود، تابع $y=x!$ می‌تواند به اعداد مختلط تعمیم داده شود. فرض کنید $z = a + bi$ ، یک عدد مختلط باشد. در این صورت داریم: $z! = \Gamma (a + bi + 1)$

کاربرد در نظریه اعداد

اعداد فاکتوریل، خاصیت‌های جالبی در نظریه اعداد دارند که دو مورد از آن‌ها به طور مختصر در زیر آمده است:

به ازای هر عدد طبیعی $n$ که $n>5$ ، عدد $n$ عددی مرکب است، اگر و تنها اگر $(n-1)! \equiv 0 \pmod{n}$ .
قضیه‌ی ویلسون: عدد طبیعی $p$ اول است، اگر و تنها اگر $(p-1)! \equiv -1 \pmod{p}$ .

چند خاصیت جالب

فاکتوریل خواص جالب دیگری نیز دارد که برخی از آن‌ها در زیر به طور مختصر آمده است:

با نوشتن بسط تیلور $e^1$ داریم: $\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+... = e$
با بردن $n$ به سمت بی‌نهایت در عبارت $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!} + ... + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$ که در بررسی شد، داریم: $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+... = 1$
$(-\frac{1}{2})! = \sqrt{\pi}$
در بحث تحلیل پیچیدگی الگوریتم‌ها و محاسبه‌ی $O$ ، $\Omega$ و $\theta$ توابع، می‌توان گفت: $lg(n!) \in \theta(n \times lg(n))$ این خاصیت در تحلیل پیچیدگی بسیاری از الگوریتم‌ها مانند الگوریتم‌های مرتب‌سازی مقایسه‌ای، کاربرد دارد.

منابع و مراجع

فاکتوریل، ویکی‌پدیا
Chen Chuan-Chong, Koh Khee-Meng (1992), Principles and Techniques in Combinatorics, Singapore, World Scientific
انگیزه‌های $0!=1$
ضرب تهی، ویکی‌پدیا

خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید:

−فهرست مندرجات

فاکتوریل

تعریف

فاکتوریل به صورت بازگشتی

چند مثال

یک پله بالاتر

انگیزه‌های تعریف 0!0!

تعمیم به اعداد حقیقی و مختلط

کاربرد در نظریه اعداد

چند خاصیت جالب

منابع و مراجع

انگیزه‌های تعریف $0!$