Παραγοντικό

$ν$	$ν!$
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$ :

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

Φράγματα Επεξεργασία

Σε κάποιες εφαρμογές (ειδικά στον χώρο της θεωρητικής πληροφορικής), τα παρακάτω φράγματα^[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\%$ .

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

Δείτε επίσης Επεξεργασία

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

Παραπομπές Επεξεργασία

↑ Mitzenmacher, Michael (2017). Probability and computing : randomization and probabilistic techniques in algorithms and data analysis (2η έκδοση). Cambridge, United Kingdom. σελίδες 100,109. ISBN 978-1-107-15488-9.

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

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

Αυτό το μαθηματικό λήμμα χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το.

Τα Wikimedia Commons έχουν πολυμέσα σχετικά με το θέμα
Παραγοντικό

[1] Mitzenmacher, Michael (2017). Probability and computing : randomization and probabilistic techniques in algorithms and data analysis (2η έκδοση). Cambridge, United Kingdom. σελίδες 100,109. ISBN 978-1-107-15488-9.

[1]