Παραγοντικό

ν	ν!
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×1025
50	3.041409320×1064
70	1.197857167×10100
100	9.332621544×10157
450	1.733368733×101000
1000	4.023872601×102567
3249	6.412337688×1010000
10000	2.846259681×1035659
25206	1.205703438×10100000
100000	2.824229408×10456573
205023	2.503898932×101000004
1000000	8.263931688×105565708
10100	1010101.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$:

$\nu !={\begin{cases}1&{\text{για }}\nu =0,\\\nu \cdot (\nu -1)!&{\text{για }}\nu \geq 1,\end{cases}}$

ή μη-αναδρομικά, κάνοντας χρήση του συμβόλου $\prod$ για τον πολλαπλασιασμό, ως εξής:

$\nu !={\begin{cases}1&{\text{για }}\nu =0,\\\prod _{i=1}^{\nu }i&{\text{για }}\nu \geq 1.\end{cases}}$

Η σύμβαση 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 !$ (και της συνεχής επέκτασής του με την συνάρτησης γάμμα) με τον τύπο του Στίρλινγκ.

Ο τύπος του Στίρλινγκ δίνει ότι

$\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.$

Φράγματα

Σε κάποιες εφαρμογές (ειδικά στον χώρο της θεωρητικής πληροφορικής), τα παρακάτω φράγματα δίνουν αρκετά ικανοποιητικά αποτελέσματα:

$\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 == 0) 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\%$.

Ομοίως, για το $3!=6$, το αντιπαραγοντικό του $!3$ είναι ίσο με $1/3!=1/6$, δηλαδή περίπου $16,6\%$.

Δείτε επίσης

• Συνάρτηση γάμμα

Εξωτερικοί σύνδεσμοι

• (Αγγλικά) Weisstein, Eric W., «Factorial», από MathWorld. Ανακτήθηκε 2020-07-22.