====== فاکتوریل ======

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

----

===== تعریف =====

فرض کنید $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$ در نظر گرفته می‌شود. این قرارداد شاید در ابتدا عجیب و بیهوده به نظر بیاید، اما انگیزه‌های بسیاری برای تعریف آن وجود دارد که می‌توانید در 
[[آموزش:ترکیبیات:فاکتوریل#یک_پله_بالاتر|یک پله بالاتر]] ببینید.

نماد فاکتوریل تنها به اعداد صحیح نامنفی محدود نمی‌شود و برای دیگر اعداد حقیقی و حتی اعداد غیر حقیقی تعریف می‌شود که می‌توانید در 
[[آموزش:ترکیبیات:فاکتوریل#یک_پله_بالاتر|یک پله بالاتر]] با آن‌ها آشنا شوید.

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

<WRAP :en 35% center>
|  $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  |
</WRAP>

همان طور که مشاهده می‌کنید، با بزرگ شدن $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!$ در مخرج فرمول ظاهر می‌شود که اگر آن را برابر ۱ در نظر بگیریم، مشکل حل می‌شود.
  - در ریاضیات، مفهومی به نام [[http://en.wikipedia.org/wiki/Empty_product|ضرب تهی]] وجود دارد که با نوشتن فاکتوریل به صورت بازگشتی، ایجاب می‌کند $0!=1$ باشد.
  - فاکتوریل محدود به اعداد صحیح نامنفی نیست و به اعداد حقیقی و حتی اعداد مختلط، تعمیم داده می‌شود. با تعریفی که برای فاکتوریل، در این تعمیم داده می‌شود، $0!=1$ است. این تعمیم را در ادامه‌ی این صفحه خواهید دید.
  - در بسیاری از [[http://en.wikipedia.org/wiki/Taylor_series|بسط‌های تیلور]] توابع، ضریب $0!$ ظاهر می‌شود. بسط‌های تیلور در صورتی درست کار می‌کنند که $0!=1$ باشد.

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

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

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

{{ :آموزش:ترکیبیات:500px-generalized_factorial_function.svg.png |}}

تابع گاما این خاصیت را دارد که:
$$\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}$$.
  - [[http://en.wikipedia.org/wiki/Wilson%27s_theorem|قضیه‌ی ویلسون]]: عدد طبیعی $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))$$ این خاصیت در تحلیل پیچیدگی بسیاری از الگوریتم‌ها مانند [[آموزش:الگوریتم:مرتب‌سازی_مقایسه‌ای|الگوریتم‌های مرتب‌سازی مقایسه‌ای]]، کاربرد دارد.


----

===== منابع و مراجع =====
  - [[http://en.wikipedia.org/wiki/Factorial|فاکتوریل، ویکی‌پدیا]]
  - Chen Chuan-Chong, Koh Khee-Meng (1992), Principles and Techniques in Combinatorics, Singapore, World Scientific
  - [[http://statistics.about.com/od/ProbHelpandTutorials/a/Why-Does-Zero-Factorial-Equal-One.htm|انگیزه‌های $0!=1$]]
  - [[http://en.wikipedia.org/wiki/Empty_product|ضرب تهی، ویکی‌پدیا]]

----

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

~~DISCUSSION~~