Παραγοντικό

$ν にゅー$	$ν にゅー!$
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
16	20922789888000
17	355687428096000
18	6402373705728000
19	121645100408832000
20	2432902008176640000
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¹⁰⁰⁰⁰
10000	2.846259681×10³⁵⁶⁵⁹
25206	1.205703438×10¹⁰⁰⁰⁰⁰
100000	2.824229408×10⁴⁵⁶⁵⁷³
205023	2.503898932×10^1000004
1000000	8.263931688×10^5565708
10¹⁰⁰	10^{10^{101.9981097754820}}

Σしぐまτたうαあるふぁ μαθηματικά τたうo παραγοντικό ενός φυσικού αριθμού $\nu$ συμβολίζεται μみゅーεいぷしろん $\nu !$ , διαβάζεται νにゅーιいおた παραγοντικό, κかっぱαあるふぁιいおた είναι τたうοおみくろん γινόμενο όλων τたうωおめがνにゅー θετικών ακεραίων μικρότερων ή ίσων μみゅーεいぷしろん $\nu$ :

\nu !=1\cdot 2\cdot 3\cdot \ldots \cdot \nu

.

Γがんまιいおたαあるふぁ παράδειγμα,

2!=1\cdot 2=2

,

3!=1\cdot 2\cdot 3=6

,

4!=1\cdot 2\cdot 3\cdot 4=24

,

5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120

,

8!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8=40.320

.

Τたうοおみくろん παραγοντικό ενός αριθμού $\nu$ ισούται μみゅーεいぷしろん τたうοおみくろん πλήθος τたうωおめがνにゅー δυνατών μεταθέσεων τたうωおめがνにゅー $\nu$ στοιχείων ενός συνόλου, δηλαδή τたうοおみくろん πλήθος τたうωおめがνにゅー διαφορετικών τρόπων μみゅーεいぷしろん τους οποίους μπορούμε νにゅーαあるふぁ βάλουμε σしぐまεいぷしろん μみゅーιいおたαあるふぁ σειρά τたうαあるふぁ $\nu$ στοιχεία ενός συνόλου. Γがんまιいおたαあるふぁ παράδειγμα, γがんまιいおたαあるふぁ τたうοおみくろん σύνολο $\Sigma =\{\alpha ,\beta ,\gamma \}$ , υπάρχουν συνολικά $3!=1\cdot 2\cdot 3=6$ δυνατές μεταθέσεις, οおみくろんιいおた οποίες είναι οおみくろんιいおた εξής: $\alpha \beta \gamma$ , $\alpha \gamma \beta$ , $\beta \alpha \gamma$ , $\beta \gamma \alpha$ , $\gamma \alpha \beta$ , $\gamma \beta \alpha$ .

Ορισμός[Επεξεργασία | επεξεργασία κώδικα]

Τたうοおみくろん $\nu !$ ορίζεται αναδρομικά ως εξής γがんまιいおたαあるふぁ τたうοおみくろんνにゅー φυσικό αριθμό $\nu$ :

{\displaystyle \nu !={\begin{cases}1&{\text{

ή μみゅーηいーた-αναδρομικά, κάνοντας χρήση τたうοおみくろんυうぷしろん συμβόλου $\prod$ γがんまιいおたαあるふぁ τたうοおみくろんνにゅー πολλαπλασιασμό, ως εξής:

{\displaystyle \nu !={\begin{cases}1&{\text{

Ηいーた σύμβαση 0! = 1[Επεξεργασία | επεξεργασία κώδικα]

Παρατηρήστε ότι κかっぱαあるふぁιいおた στους δύο παραπάνω ορισμούς ηいーた σύμβαση είναι ότι $0!=1$ . Αυτό βοηθάει σしぐまεいぷしろん διάφορους ορισμούς πぱいοおみくろんυうぷしろん προκύπτουν από αυτόν τたうοおみくろんυうぷしろん παραγοντικού, όπως είναι οおみくろんιいおた διωνυμικοί συντελεστές ${\tbinom {\nu }{\kappa }}$ , οおみくろんιいおた οποίοι γがんまιいおたαあるふぁ $0\leq \kappa \leq \nu$ δίνονται από τたうοおみくろんνにゅー τύπο

{\binom {\nu }{\kappa }}={\frac {\nu !}{(\nu -\kappa )!\kappa !}}.

Οおみくろん ορισμός τたうοおみくろんυうぷしろん $0!=1$ , επιτρέπει σしぐまτたうοおみくろんνにゅー ορισμό νにゅーαあるふぁ δουλεύει γがんまιいおたαあるふぁ $\kappa =0$ , καθώς κかっぱαあるふぁιいおた γがんまιいおたαあるふぁ $\nu =\kappa$ χωρίς αλλαγές.

Πλήθος μεταθέσεων[Επεξεργασία | επεξεργασία κώδικα]

Όπως αναφέρθηκε σしぐまτたうηいーたνにゅー εισαγωγή, τたうοおみくろん πλήθος τたうωおめがνにゅー δυνατών μεταθέσεων ενός συνόλου μみゅーεいぷしろん $\nu$ στοιχεία είναι $\nu !$ . Αυτό προκύπτει επαγωγικά. Γがんまιいおたαあるふぁ $\nu =1$ , υπάρχει μία δυνατή μετάθεση γがんまιいおたαあるふぁ αυτό τたうοおみくろん στοιχείο.

Γがんまιいおたαあるふぁ $\nu \geq 2$ , υπάρχουν $\nu$ τρόποι νにゅーαあるふぁ διαλέξουμε τたうοおみくろん πρώτο στοιχείο της μετάθεσης (διαλέγοντας οποιοδήποτε από τたうαあるふぁ $\nu$ στοιχεία) κかっぱαあるふぁιいおた έπειτα υπάρχουν $\nu -1$ στοιχεία γがんまιいおたαあるふぁ τις υπόλοιπες θέσεις. Από τたうηいーたνにゅー επαγωγική υπόθεση υπάρχουν $(\nu -1)!$ τρόποι νにゅーαあるふぁ διατάξουμε αυτά τたうαあるふぁ στοιχεία κかっぱαあるふぁιいおた επομένως συνολικά $\nu \cdot (\nu -1)!=\nu !$ τρόποι νにゅーαあるふぁ διατάξουμε τたうαあるふぁ $\nu$ στοιχεία.

Αναδρομική κατασκευή μεταθέσεων

Αναδρομική κατασκευή μεταθέσεων μみゅーεいぷしろん τρία στοιχεία, χρησιμοποιώντας τις μεταθέσεις δύο στοιχείων.

Γενική αναδρομική κατασκευή μεταθέσεων μみゅーεいぷしろん

\nu

στοιχεία, έχοντας τις μεταθέσεις γがんまιいおたαあるふぁ τたうαあるふぁ

\nu -1

στοιχεία.

Ασυμπτωτική συμπεριφορά[Επεξεργασία | επεξεργασία κώδικα]

Σしぐまεいぷしろん αρκετές εφαρμογές είναι πぱいιいおたοおみくろん βολικό νにゅーαあるふぁ δουλεύουμε μみゅーεいぷしろん προσεγγίσεις τたうοおみくろんυうぷしろん $\nu !$ , αντί μみゅーεいぷしろん τたうοおみくろんνにゅー κλειστό τύπο.

Τύπος Στίρλινγκ[Επεξεργασία | επεξεργασία κώδικα]

Οおみくろん τύπος τたうοおみくろんυうぷしろん Στίρλινγκ δίνει ότι

\nu !\sim {\sqrt {2\pi }}\cdot \nu ^{\nu +1/2}\cdot e^{-\nu },

ή ισοδύναμα

\lim _{\nu \to \infty }{\frac {\nu !}{{\sqrt {2\pi }}\cdot \nu ^{\nu +1/2}\cdot e^{-\nu }}}=1.

Φράγματα[Επεξεργασία | επεξεργασία κώδικα]

Σしぐまεいぷしろん κάποιες εφαρμογές (ειδικά σしぐまτたうοおみくろんνにゅー χώρο της θεωρητικής πληροφορικής), τたうαあるふぁ παρακάτω φράγματα^[1] δίνουν αρκετά ικανοποιητικά αποτελέσματα:

\left({\frac {\nu }{e}}\right)^{\nu }\leq \nu !\leq e\cdot {\sqrt {\nu }}\cdot \left({\frac {\nu }{e}}\right)^{\nu }.

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

Κυκλικές μεταθέσεις[Επεξεργασία | επεξεργασία κώδικα]

Έστω ότι θέλουμε νにゅーαあるふぁ μετρήσουμε τたうοおみくろん πλήθος τたうωおめがνにゅー δυνατών κυκλικών μεταθέσεων. Γがんまιいおたαあるふぁ παράδειγμα, μπορεί νにゅーαあるふぁ θέλουμε νにゅーαあるふぁ τοποθετήσουμε $\nu =4$ άτομα σしぐまεいぷしろん ένα κυκλικό τραπέζι μみゅーεいぷしろん $\nu$ θέσεις, τότε υπάρχουν οおみくろんιいおた εξής $6$ δυνατές μεταθέσεις. Παρατηρήστε ότι οおみくろんιいおた διατάξεις $\alpha \beta \gamma \delta$ , $\delta \alpha \beta \gamma$ , $\gamma \delta \alpha \beta$ κかっぱαあるふぁιいおた $\beta \gamma \delta \alpha$ είναι ισοδύναμες.

Κυκλικές μεταθέσεις γがんまιいおたαあるふぁ ένα σύνολο τεσσάρων στοιχείων

Οおみくろんιいおた έξι δυνατές κυκλικές μεταθέσεις γがんまιいおたαあるふぁ τたうαあるふぁ στοιχεία

\{\alpha ,\beta ,\gamma ,\delta \}

.

Οおみくろんιいおた ισοδύναμες κυκλικές μεταθέσεις γがんまιいおたαあるふぁ τたうαあるふぁ τέσσερα στοιχεία.

Σしぐまτたうηいーたνにゅー γενική περίπτωση κάθε διάταξη είναι ισοδύναμη μみゅーεいぷしろん τις $\nu$ κυκλικές διατάξεις της. Επομένως, από τις $\nu !$ δυνατές μεταθέσεις, ακριβώς οおみくろんιいおた $\nu !/\nu =(\nu -1)!$ αντιστοιχούν σしぐまεいぷしろん διαφορετικές μεταθέσεις σしぐまεいぷしろん έναν κύκλο.

Διατάξεις[Επεξεργασία | επεξεργασία κώδικα]

Ορισμός μαθηματικής σταθεράς $e$ [Επεξεργασία | επεξεργασία κώδικα]

Τたうοおみくろん παραγοντικό εμφανίζεται κかっぱαあるふぁιいおた σしぐまτたうοおみくろんνにゅー εξής ορισμό της μαθηματικής σταθεράς e,

e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+{\frac {1}{3!}}+\ldots =\sum _{i=0}^{\infty }{\frac {1}{i!}}.

Δυναμοσειρές τριγωνομετρικών συναρτήσεων[Επεξεργασία | επεξεργασία κώδικα]

Ηいーた συνάρτηση τたうοおみくろんυうぷしろん ημιτόνου μπορεί νにゅーαあるふぁ οριστεί ως εξής:

\sin(x)=x-{\frac {x^{3}}{3!}}+{\frac {x^{5}}{5!}}-\ldots =\sum _{i=0}^{\infty }{\frac {(-1)^{i}}{(2i+1)!}}\cdot x^{2i+1}.

Επίσης, ηいーた συνάρτηση τたうοおみくろんυうぷしろん συνημιτόνου μπορεί νにゅーαあるふぁ οριστεί ως εξής:

\cos(x)=1-{\frac {x^{2}}{2!}}+{\frac {x^{4}}{4!}}-{\frac {x^{6}}{6!}}+\ldots =\sum _{i=0}^{\infty }{\frac {(-1)^{i}}{(2i)!}}\cdot x^{2i}.

Σειρά Τέιλορ[Επεξεργασία | επεξεργασία κώδικα]

Ηいーた σειρά Τέιλορ μίας πραγματικής συνάρτησης $f:\mathbb {R} \to \mathbb {R}$ σしぐまτたうοおみくろん σημείο $a\in \mathbb {R}$ είναι ηいーた δυναμοσειρά

f(a)+{\frac {f'(a)}{1!}}\cdot (x-a)+{\frac {f''(a)}{2!}}\cdot (x-a)^{2}+\ldots =\sum _{i=0}^{\infty }{\frac {f^{(i)}(a)}{i!}}\cdot (x-a)^{i}.

Υπολογισμός[Επεξεργασία | επεξεργασία κώδικα]

Παρακάτω δίνονται οおみくろんιいおた δύο κλασσικές υλοποιήσεις γがんまιいおたαあるふぁ τたうοおみくろんνにゅー υπολογισμό τたうοおみくろんυうぷしろん παραγοντικού: ηいーた αναδρομική κかっぱαあるふぁιいおた ηいーた γραμμική υλοποίηση. Σしぐまεいぷしろん γλώσσες προγραμματισμού μみゅーεいぷしろん ακεραίους πεπερασμένου μεγέθους οおみくろん παρακάτω κώδικας θしーたαあるふぁ οδηγήσει σしぐまεいぷしろん υπερχείλιση όταν τたうοおみくろん $\nu$ είναι μεγάλο. Κかっぱαあるふぁιいおた οおみくろんιいおた δύο αλγόριθμοι χρησιμοποιούν $\nu -1$ πολλαπλασιασμούς.

Αναδρομικός υπολογισμός[Επεξεργασία | επεξεργασία κώδικα]

int factorial(int n) {
   if (n == 1) return 1;
   return n * factorial(n - 1);
}

Γραμμικός υπολογισμός[Επεξεργασία | επεξεργασία κώδικα]

int factorial(int n) {
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
      ans *= i;
   }
   return ans;
}

Αντιπαραγοντικό[Επεξεργασία | επεξεργασία κώδικα]

Τたうοおみくろん αντιπαραγοντικό ενός φυσικού αριθμού $\nu$ συμβολίζεται μみゅーεいぷしろん $!\nu$ , διαβάζεται νにゅーιいおた αντιπαραγοντικό, κかっぱαあるふぁιいおた είναι τたうοおみくろん πηλίκο όλων τたうωおめがνにゅー θετικών ακέραιων μικρότερων ή ίσων μみゅーεいぷしろん $\nu$ , δηλαδή

!\nu ={\frac {1}{\nu !}}={\frac {1}{\nu }}\cdot !(\nu -1)={\frac {1}{\nu }}\cdot {\frac {1}{\nu -1}}\cdot \ldots \cdot {\frac {1}{2}}\cdot {\frac {1}{1}},

κかっぱαあるふぁιいおた συμβατικά $!0=1$ .

Τたうοおみくろん αντιπαραγοντικό $!\nu$ μας δίνει ηいーた πιθανότητα εντοπισμού μίας συγκεκριμένης μετάθεσης από τたうοおみくろん σύνολο τたうωおめがνにゅー $\nu !$ μεταθέσεων. Γがんまιいおたαあるふぁ παράδειγμα, τたうοおみくろん σύνολο $2!=2$ , μας δίνει τις μεταθέσεις: $1,2$ κかっぱαあるふぁιいおた $2,1$ . Ηいーた πιθανότητα εύρεσης της επιθυμητής μετάθεσης ( $1,2$ ή $2,1$ ), δίνεται από τたうοおみくろん αντιπαραγοντικό τたうοおみくろんυうぷしろん $2$ δηλαδή $!2=1/2!=1/2=0.5$ , συνεπώς $50\%$ .