Faktorial

Anggota terpilih dari faktorial urutan (barisan A000142 pada OEIS); nilai yang ditentukan dalam notasi ilmiah dibulatkan ke presisi yang ditampilkan
$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40.320
9	362.880
10	3.628.800
11	39.916.800
12	479.001.600
13	6.227.020.800
14	87.178.291.200
15	1.307.674.368.000
16	20.922.789.888.000
17	355.687.428.096.000
18	6.402.373.705.728.000
19	121.645.100.408.832.000
20	2.432.902.008.176.640.000
25	1,551121004×10²⁵
50	3,041409320×10⁶⁴
70	1,197857167×10¹⁰⁰
100	9,332621544×10¹⁵⁷
450	1.733368733×10¹⁰⁰⁰
1000	4.023872601×10²⁵⁶⁷
3249	6,412337688×10^10.000
10000	2,846259681×10^35.659
25206	1,205703438×10^100.000
100000	2,824229408×10^456.573
205023	2,503898932×10^1.000.004
1000000	8,263931688×10^5.565.708
10¹⁰⁰	10^{10^101,9981097754820}

Dalam matematika, Faktorial dari bilangan bulat positif dari $n$ yang dilambangkan dengan $n!$ , adalah produk dari semua bilangan bulat positif yang kurang dari atau sama dengan $n$ :

n!=n\times (n-1)\times (n-2)\times (n-3)\times \cdots \times 3\times 2\times 1\,.

Sebagai contoh,

5!=5\times 4\times 3\times 2\times 1=120\,.

Nilai 0! adalah 1, menurut konvensi untuk produk kosong.^[1]

Operasi faktorial digunakan sebagai bidang matematika, terutama di kombinatorik, aljabar, dan analisis matematika. Penggunaannya yang paling dasar menghitung kemungkinan urutan dan permutasi dari $n$ yang berada di objekk yang berbeda.

Faktorial pada fungsi juga dapat berupa nilai ke argumen non-bilangan bulat sambil mempertahankan properti terpentingnya dengan cara mendefinisikan $x! = Γ(x + 1)$ , dimana $Γ$ adalah fungsi gamma; ini tidak ditentukan saat $x$ adalah bilangan bulat negatif.

Sejarah

Faktorial digunakan untuk menghitung permutasi setidaknya sejak abad ke-12, oleh para sarjana India.^[2] Pada tahun 1677, Fabian Stedman mendeskripsikan faktorial yang diterapkan pada mengubah dering, seni musik yang melibatkan dering dari banyak lonceng yang disetel.^[3] Setelah menggambarkan pendekatan rekursif, Stedman memberikan pernyataan faktorial (menggunakan bahasa aslinya):

Sekarang sifat dari metode ini adalah sedemikian rupa, sehingga perubahan pada satu angka mencakup [termasuk] perubahan pada semua angka yang lebih kecil ... sedemikian rupa sehingga Peal yang lengkap dari perubahan pada satu nomor tampaknya dibentuk dengan menyatukan Peal yang lengkap pada semua nomor yang lebih kecil menjadi satu keseluruhan tubuh..^[4]

notasi dari $n!$ diperkenalkan oleh matematikawan asal Prancis bernama Christian Kramp pada tahun 1808.^[5]

Pengertian

Fungsi faktorial didefinisikan sebagai:

n!=\prod _{k=1}^{n}k\qquad {\mbox{untuk semua }}n\geq 1.

Selain definisi tersebut, terdapat juga definisi secara rekursif, yang didefinisikan untuk $n\geq 0$

n!={\begin{cases}n\cdot (n-1)!,&{\mbox{untuk }}n\geq 1\\1,&{\mbox{untuk }}n=0.\end{cases}}

Untuk n yang sangat besar, akan terlalu melelahkan untuk menghitung n! menggunakan kedua definisi tersebut. Jika presisi tidak terlalu penting, pendekatan dari n! bisa dihitung menggunakan rumus Stirling:

n!\approx {\sqrt {2\pi n}}\,{\frac {n^{n}}{e^{n}}}.

Juga terdapat definisi analitik untuk faktorial, yaitu menggunakan fungsi gamma:

\Gamma (z)=\int _{0}^{\infty }t^{z-1}e^{-t}\,\mathrm {d} t

n!=\Gamma (n+1)

Definisi

Fungsi faktorial ditentukan oleh produk, yaitu:

n!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\cdot n,

diatas merupakan bilangan bulat dari $n \geq 1$ . Ini dapat ditulis dalam notasi perkalian pi sebagai:

n!=\prod _{i=1}^{n}i.

Hal tersebut mengarah menuju relasi pengulangan:

n!=n\cdot (n-1)!.

Sebagai contoh,

{\begin{aligned}5!&=5\cdot 4!\\6!&=6\cdot 5!\\50!&=50\cdot 49!\end{aligned}}

dan seterusnya.

Faktorial nol

Faktorial dari $0$ adalah $1$ , atau dalam simbol, $0! = 1$ .

Ada beberapa motivasi untuk definisi ini:

Untuk nilai $n = 0$ , definisi dari $n!$ sebagai perkalian melibatkan hasil kali tanpa bilangan sama sekali, dan begitu juga contoh dari konvensi yang lebih luas bahwa produk dari tidak ada faktor yang sama dengan identitas perkalian (lihat Produk kosong).
Hanya ada satu permutasi dari nol objek (tanpa ada yang diubah, satu-satunya penataan ulang adalah tidak melakukan apa-apa).
Karena membuat banyak identitas di kombinatorik berlaku untuk semua ukuran yang berlaku. Banyaknya cara untuk memilih 0 elemen dari himpunan kosong diberikan oleh koefisien binomial

{\binom {0}{0}}={\frac {0!}{0!0!}}=1.

Secara lebih umum, jumlah cara untuk memilih semua elemen

n

di antara himpunan

n

adalah

{\binom {n}{n}}={\frac {n!}{n!0!}}=1.

Hal ini memungkinkan untuk ekspresi ringkas dari banyak rumus, seperti fungsi eksponensial, sebagai deret pangkat:

e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}.

Hal ini dapat memperluas hubungan pengulangan ke 0.

Aplikasi

Meskipun fungsi faktorial berakar pada kombinatorik, rumus yang melibatkan faktorial terjadi di banyak bidang matematika.

Terdapat nilai $n!$ dengan cara yang berbeda untuk menyusun $n$ objek yang berbeda menjadi sebuah urutan, permutasi dari objek tersebut.^[6]^[7]
Seringkali faktorial muncul di penyebut rumus untuk menjelaskan fakta bahwa pengurutan harus diabaikan. Contoh klasik menghitung nilai $k$ kombinasi (himpunan bagian dari elemen nilai $k$ ) dari himpunan dengan elemen $n$ . Seseorang bisa mendapatkan kombinasi seperti itu dengan memilih $k$ sebagai permutasi: secara berturut-turut memilih dan menghapus satu elemen himpunan, $k$ kali, dengan total

(n-0)(n-1)(n-2)\cdots \left(n-(k-1)\right)={\frac {n!}{(n-k)!}}=n^{\underline {k}}

Namun, hal ini menghasilkan kombinasi

k

dalam urutan tertentu yang ingin dinyalakan; karena setiap

k

- kombinasi diperoleh dengan

k!

cara yang berbeda, jumlah yang benar dari

k

kombinasi adalah

{\frac {n(n-1)(n-2)\cdots (n-k+1)}{k(k-1)(k-2)\cdots 1}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(n-k)!k!}}={\binom {n}{k}}.

Nomor ini diketahui^[8] sebagai koefisien binomial, karena ia juga merupakan koefisien dari

x k

pada

(1 + x) n

. Syarat

n^{\underline {k}}

sering disebut faktorial jatuh (dilafalkan "n menjadi penurunan k").

Faktorial terjadi di aljabar karena berbagai alasan, seperti melalui koefisien yang telah disebutkan dari rumus binomial, atau melalui rata-rata lebih dari permutasi untuk simetri operasi tertentu.
Faktorial juga muncul di kalkulus; misalnya, mereka muncul di penyebut suku-suku rumus Taylor,^[9] di mana mereka digunakan sebagai persyaratan kompensasi karena $n$ turunan dari $x n$ setara dengan $n!$ .
Faktorial juga digunakan secara ekstensif di teori probabilitas^[10] dan teori bilangan (lihat di bawah).
Faktorial dapat berguna untuk memfasilitasi manipulasi ekspresi. Misalnya jumlah $k$ permutasi dari $n$ dapat ditulis sebagai

n^{\underline {k}}={\frac {n!}{(n-k)!}}\,;

meskipun ini tidak efisien sebagai cara untuk menghitung bilangan itu, ini dapat berfungsi untuk membuktikan sifat simetri^[7]^[8] dari koefisien binomial:

{\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(n-k)!k!}}={\frac {n^{\underline {n-k}}}{(n-k)!}}={\binom {n}{n-k}}\,.

Fungsi faktorial dapat ditampilkan, menggunakan aturan pangkat, sebagai

n!=D^{n}\,x^{n}={\frac {d^{n}}{dx^{n}}}\,x^{n}

where

D n x n

is Notasi Euler untuk

n

turunan dari

x n

.^[11]

Tingkat pertumbuhan dan perkiraan untuk yang besar $n$

Plot dari logaritma natural faktorial

Seiring bertambahnya $n$ , faktorial $n!$ Meningkat lebih cepat daripada semua polinomial dan fungsi eksponensial (tetapi lebih lambat dari $n^{n}$ dan fungsi eksponensial ganda) masuk $n$ .

Sebagian besar perkiraan untuk n! didasarkan pada perkiraan logaritma natural

\ln n!=\sum _{x=1}^{n}\ln x\,.

Grafik fungsi $f (n) = ln n!$ ditunjukkan pada gambar di sebelah kanan. Ini terlihat kira-kira linear untuk semua nilai wajar dari $n$ , tetapi intuisi ini salah. Kami mendapatkan salah satu perkiraan paling sederhana untuk $ln n!$ dengan membatasi jumlah dengan integral dari atas dan bawah sebagai berikut:

\int _{1}^{n}\ln x\,dx\leq \sum _{x=1}^{n}\ln x\leq \int _{0}^{n}\ln(x+1)\,dx

yang memberi kami perkiraan

n\ln \left({\frac {n}{e}}\right)+1\leq \ln n!\leq (n+1)\ln \left({\frac {n+1}{e}}\right)+1\,.

Karenanya $ln n! \sim n ln n$ (lihat Notasi Big $O$ ). Hasil ini memainkan peran kunci dalam analisis kompleksitas komputasi dari algoritma pengurutan (lihat jenis perbandingan). Dari batas $ln n!$ disimpulkan di atas kita mendapatkan

\left({\frac {n}{e}}\right)^{n}e\leq n!\leq \left({\frac {n+1}{e}}\right)^{n+1}e\,.

Terkadang praktis untuk menggunakan perkiraan yang lebih lemah tetapi lebih sederhana. Menggunakan rumus di atas, dengan mudah ditunjukkan bahwa untuk semua $n$ kita punya $(n 3) n < n!$ , dan untuk semua $n \geq 6$ kita punya $n! < (n 2) n$ .

Perbandingan pendekatan Stirling dengan faktorial

Untuk $n$ besar kita mendapatkan perkiraan yang lebih baik untuk bilangan $n!$ Menggunakan pendekatan Stirling:

n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.

Ini sebenarnya berasal dari deret asimtotik untuk logaritma, dan faktorial $n$ terletak di antara pendekatan ini dan pendekatan berikutnya:

{\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}<n!<{\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}e^{1/(12n)}\,.

Perkiraan lain untuk $ln n!$ Diberikan oleh Srinivasa Ramanujan (Ramanujan 1988)

{\begin{aligned}\ln n!&\approx n\ln n-n+{\frac {\ln {\Bigl (}n{\bigl (}1+4n(1+2n){\bigr )}{\Bigr )}}{6}}+{\frac {\ln \pi }{2}}\\[6px]\Longrightarrow \;n!&\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{2n}}+{\frac {1}{8n^{2}}}\right)^{1/6}\,.\end{aligned}}

Baik pendekatan ini maupun perkiraan Stirling memberikan kesalahan relatif pada urutan $1 n 3$ , tapi Ramanujan sekitar empat kali lebih akurat. Namun, jika kita menggunakan istilah koreksi dua dalam pendekatan tipe Stirling, seperti dengan pendekatan Ramanujan, kesalahan relatifnya akan teratur. $1 n 5$ :^[12]

n!\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({{\frac {1}{12n}}-{\frac {1}{360n^{3}}}}\right)\,.

Teori bilangan

Faktorial memiliki banyak penerapan dalam teori bilangan. Secara khusus, $n!$ Harus habis dibagi semua bilangan prima hingga dan termasuk $n$ . Sebagai konsekuensi, $n > 5$ adalah bilangan komposit jika dan hanya jika

(n-1)!\equiv 0{\pmod {n}}.

Hasil yang lebih kuat adalah Teorema Wilson, yang menyatakan bahwa

(p-1)!\equiv -1{\pmod {p}}

if and only if $p$ is prime.^[13]^[14]

Rumus Legendre memberikan kelipatan bilangan prima $p$ yang terjadi dalam faktorisasi prima dari $n!$ Sebagai

\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor

or, equivalently,

{\frac {n-s_{p}(n)}{p-1}},

dimana $s p (n)$ menunjukkan jumlah dari basis standar $p$ digit $n$ .

Menambahkan 1 ke faktorial $n!$ Menghasilkan bilangan yang hanya habis dibagi oleh bilangan prima yang lebih besar dari $n$ . Fakta ini dapat digunakan untuk membuktikan Teorema Euklides bahwa bilangan prima tidak terbatas.^[15] Bentuk prima $n! \pm 1$ disebut prima faktorial.

Serangkaian timbal balik

kebalikan dari faktorial menghasilkan deret konvergen yang jumlahnya basis eksponensial $e$ :

\sum _{n=0}^{\infty }{\frac {1}{n!}}={\frac {1}{1}}+{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{6}}+{\frac {1}{24}}+{\frac {1}{120}}+\cdots =e\,.

Meskipun jumlah deret ini adalah bilangan irasional, kita bisa mengalikan faktorial dengan bilangan bulat positif untuk menghasilkan deret konvergen dengan jumlah yang rasional:

\sum _{n=0}^{\infty }{\frac {1}{(n+2)n!}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{30}}+{\frac {1}{144}}+\cdots =1\,.

Konvergensi deret ini ke 1 dapat dilihat dari fakta bahwa jumlah parsial adalah ${\frac {k!-1}{k!}}$ . Oleh karena itu, faktorial tidak membentuk urutan irasionalitas.^[16]

Lihat pula

Referensi

^ Graham, Knuth & Patashnik 1988, hlm. 111.
^ Biggs, Norman L. (May 1979). "The roots of combinatorics". Historia Mathematica. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0. ISSN 0315-0860.
^ Stedman 1677, hlm. 6–9.
^ Stedman 1677, hlm. 8.
^ Higgins 2008, hlm. 12
^ Cheng, Eugenia (2017-03-09). Beyond Infinity: An expedition to the outer limits of the mathematical universe (dalam bahasa Inggris). Profile Books. ISBN 9781782830818.
^ ^a ^b Conway, John H.; Guy, Richard (1998-03-16). The Book of Numbers (dalam bahasa Inggris). Springer Science & Business Media. ISBN 9780387979939.
^ ^a ^b Knuth, Donald E. (1997-07-04). The Art of Computer Programming: Volume 1: Fundamental Algorithms (dalam bahasa Inggris). Addison-Wesley Professional. ISBN 9780321635747.
^ "18.01 Single Variable Calculus, Lecture 37: Taylor Series". MIT OpenCourseWare. Fall 2006. Diarsipkan dari versi asli tanggal 2018-04-26. Diakses tanggal 2017-05-03.
^ Kardar, Mehran (2007-06-25). "Chapter 2: Probability". Statistical Physics of Particles (dalam bahasa English). Cambridge University Press. hlm. 35–56. ISBN 9780521873420.
^ "18.01 Single Variable Calculus, Lecture 4: Chain rule, higher derivatives". MIT OpenCourseWare. Fall 2006. Diarsipkan dari versi asli tanggal 2018-04-26. Diakses tanggal 2017-05-03.
^ Impens, Chris (2003), "Stirling's series made easy", American Mathematical Monthly, 110 (8): 730–735, doi:10.2307/3647856, hdl:1854/LU-284957  , MR 2024001 ; lihat khususnya ketimpangan di hal. 732 menunjukkan bahwa kesalahan relatif paling banyak $1/1260n^{5}$ .
^ John J. O'Connor and Edmund F. Robertson. Abu Ali al-Hasan ibn al-Haytham di MacTutor archive.
^ (Inggris) Weisstein, Eric W. [WilsonsTheorem.html "Wilson's Theorem"] Periksa nilai |url= (bantuan). MathWorld. Diakses tanggal 2017-05-17.
^ Bostock, Chandler & Rourke 2014, hlm. 168.
^ Guy 2004, hlm. 346.

Pranala luar

[FOOTNOTEGrahamKnuthPatashnik1988111-1] Graham, Knuth & Patashnik 1988, hlm. 111.

[2] Biggs, Norman L. (May 1979). "The roots of combinatorics". Historia Mathematica. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0. ISSN 0315-0860.

[FOOTNOTEStedman16776–9-3] Stedman 1677, hlm. 6–9.

[FOOTNOTEStedman16778-4] Stedman 1677, hlm. 8.

[5] Higgins 2008, hlm. 12

[6] Cheng, Eugenia (2017-03-09). Beyond Infinity: An expedition to the outer limits of the mathematical universe (dalam bahasa Inggris). Profile Books. ISBN 9781782830818.

[ConwayGuy1998-7] Conway, John H.; Guy, Richard (1998-03-16). The Book of Numbers (dalam bahasa Inggris). Springer Science & Business Media. ISBN 9780387979939.

[Knuth1997-8] Knuth, Donald E. (1997-07-04). The Art of Computer Programming: Volume 1: Fundamental Algorithms (dalam bahasa Inggris). Addison-Wesley Professional. ISBN 9780321635747.

[9] "18.01 Single Variable Calculus, Lecture 37: Taylor Series". MIT OpenCourseWare. Fall 2006. Diarsipkan dari versi asli tanggal 2018-04-26. Diakses tanggal 2017-05-03.

[10] Kardar, Mehran (2007-06-25). "Chapter 2: Probability". Statistical Physics of Particles (dalam bahasa English). Cambridge University Press. hlm. 35–56. ISBN 9780521873420.

[11] "18.01 Single Variable Calculus, Lecture 4: Chain rule, higher derivatives". MIT OpenCourseWare. Fall 2006. Diarsipkan dari versi asli tanggal 2018-04-26. Diakses tanggal 2017-05-03.

[12] Impens, Chris (2003), "Stirling's series made easy", American Mathematical Monthly, 110 (8): 730–735, doi:10.2307/3647856, hdl:1854/LU-284957  , MR 2024001 ; lihat khususnya ketimpangan di hal. 732 menunjukkan bahwa kesalahan relatif paling banyak $1/1260n^{5}$ .

[13] John J. O'Connor and Edmund F. Robertson. Abu Ali al-Hasan ibn al-Haytham di MacTutor archive.

[14] (Inggris) Weisstein, Eric W. [WilsonsTheorem.html "Wilson's Theorem"] Periksa nilai |url= (bantuan). MathWorld. Diakses tanggal 2017-05-17.

[FOOTNOTEBostockChandlerRourke2014168-15] Bostock, Chandler & Rourke 2014, hlm. 168.

[FOOTNOTEGuy2004[https://books.google.com/books?id=1AP2CEGxTkgC&pg=PA346_346]-16] Guy 2004, hlm. 346.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]