Παραγοντικό

Στα μαθηματικά τo παραγοντικό ενός φυσικού αριθμού ${\displaystyle \nu }$ συμβολίζεται με ${\displaystyle \nu$ !} , διαβάζεται νυ παραγοντικό, και είναι το γινόμενο όλων των θετικών ακεραίων μικρότερων ή ίσων με ${\displaystyle \nu }$:

${\displaystyle \nu$ !=1\cdot 2\cdot 3\cdot \ldots \cdot \nu } .

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

Για παράδειγμα,

${\displaystyle 2!=1\cdot 2=2}$,

${\displaystyle 3!=1\cdot 2\cdot 3=6}$,

${\displaystyle 4!=1\cdot 2\cdot 3\cdot 4=24}$,

${\displaystyle 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120}$,

${\displaystyle 8!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8=40.320}$.

Το παραγοντικό ενός αριθμού ${\displaystyle \nu }$ ισούται με το πλήθος των δυνατών μεταθέσεων των ${\displaystyle \nu }$ στοιχείων ενός συνόλου, δηλαδή το πλήθος των διαφορετικών τρόπων με τους οποίους μπορούμε να βάλουμε σε μια σειρά τα ${\displaystyle \nu }$ στοιχεία ενός συνόλου. Για παράδειγμα, για το σύνολο ${\displaystyle \Sigma =\{\alpha ,\beta ,\gamma \}}$, υπάρχουν συνολικά ${\displaystyle 3!=1\cdot 2\cdot 3=6}$ δυνατές μεταθέσεις, οι οποίες είναι οι εξής: ${\displaystyle \alpha \beta \gamma }$, ${\displaystyle \alpha \gamma \beta }$, ${\displaystyle \beta \alpha \gamma }$, ${\displaystyle \beta \gamma \alpha }$, ${\displaystyle \gamma \alpha \beta }$, ${\displaystyle \gamma \beta \alpha }$.

Ορισμός

Το ${\displaystyle \nu$ !} ορίζεται αναδρομικά ως εξής για τον φυσικό αριθμό ${\displaystyle \nu }$:

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

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

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

Η σύμβαση 0! = 1

Παρατηρήστε ότι και στους δύο παραπάνω ορισμούς η σύμβαση είναι ότι ${\displaystyle 0!=1}$. Αυτό βοηθάει σε διάφορους ορισμούς που προκύπτουν από αυτόν του παραγοντικού, όπως είναι οι διωνυμικοί συντελεστές ${\displaystyle {\tbinom {\nu }{\kappa }}}$, οι οποίοι για ${\displaystyle 0\leq \kappa \leq \nu }$ δίνονται από τον τύπο

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

Ο ορισμός του ${\displaystyle 0!=1}$, επιτρέπει στον ορισμό να δουλεύει για ${\displaystyle \kappa =0}$, καθώς και για ${\displaystyle \nu =\kappa }$ χωρίς αλλαγές.

Πλήθος μεταθέσεων

Όπως αναφέρθηκε στην εισαγωγή, το πλήθος των δυνατών μεταθέσεων ενός συνόλου με ${\displaystyle \nu }$ στοιχεία είναι ${\displaystyle \nu$ !} . Αυτό προκύπτει επαγωγικά. Για ${\displaystyle \nu =1}$, υπάρχει μία δυνατή μετάθεση για αυτό το στοιχείο.

Για ${\displaystyle \nu \geq 2}$, υπάρχουν ${\displaystyle \nu }$ τρόποι να διαλέξουμε το πρώτο στοιχείο της μετάθεσης (διαλέγοντας οποιοδήποτε από τα ${\displaystyle \nu }$ στοιχεία) και έπειτα υπάρχουν ${\displaystyle \nu -1}$ στοιχεία για τις υπόλοιπες θέσεις. Από την επαγωγική υπόθεση υπάρχουν ${\displaystyle (\nu -1)!}$ τρόποι να διατάξουμε αυτά τα στοιχεία και επομένως συνολικά ${\displaystyle \nu \cdot (\nu -1)!=\nu$ !} τρόποι να διατάξουμε τα ${\displaystyle \nu }$ στοιχεία.

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

Αναδρομική κατασκευή μεταθέσεων με τρία στοιχεία, χρησιμοποιώντας τις μεταθέσεις δύο στοιχείων.

Γενική αναδρομική κατασκευή μεταθέσεων με ${\displaystyle \nu }$ στοιχεία, έχοντας τις μεταθέσεις για τα ${\displaystyle \nu -1}$ στοιχεία.

Ασυμπτωτική συμπεριφορά

Σε αρκετές εφαρμογές είναι πιο βολικό να δουλεύουμε με προσεγγίσεις του ${\displaystyle \nu$ !} , αντί με τον κλειστό τύπο.

Τύπος Στίρλινγκ

Η προσέγγιση του ${\displaystyle \nu$ !} (και της συνεχής επέκτασής του με την συνάρτησης γάμμα) με τον τύπο του Στίρλινγκ.

Κύριο λήμμα: Τύπος Στίρλινγκ

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

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

ή ισοδύναμα

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

Φράγματα

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

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

Εφαρμογές

Κυκλικές μεταθέσεις

Έστω ότι θέλουμε να μετρήσουμε το πλήθος των δυνατών κυκλικών μεταθέσεων. Για παράδειγμα, μπορεί να θέλουμε να τοποθετήσουμε ${\displaystyle \nu =4}$ άτομα σε ένα κυκλικό τραπέζι με ${\displaystyle \nu }$ θέσεις, τότε υπάρχουν οι εξής ${\displaystyle 6}$ δυνατές μεταθέσεις. Παρατηρήστε ότι οι διατάξεις ${\displaystyle \alpha \beta \gamma \delta }$, ${\displaystyle \delta \alpha \beta \gamma }$, ${\displaystyle \gamma \delta \alpha \beta }$ και ${\displaystyle \beta \gamma \delta \alpha }$ είναι ισοδύναμες.

Κυκλικές μεταθέσεις για ένα σύνολο τεσσάρων στοιχείων

Οι έξι δυνατές κυκλικές μεταθέσεις για τα στοιχεία ${\displaystyle \{\alpha ,\beta ,\gamma ,\delta \}}$.

Οι ισοδύναμες κυκλικές μεταθέσεις για τα τέσσερα στοιχεία.

Στην γενική περίπτωση κάθε διάταξη είναι ισοδύναμη με τις ${\displaystyle \nu }$ κυκλικές διατάξεις της. Επομένως, από τις ${\displaystyle \nu$ !} δυνατές μεταθέσεις, ακριβώς οι ${\displaystyle \nu$ !/\nu =(\nu -1)!} αντιστοιχούν σε διαφορετικές μεταθέσεις σε έναν κύκλο.

Διατάξεις

Ορισμός μαθηματικής σταθεράς ${\displaystyle e}$

Το παραγοντικό εμφανίζεται και στον εξής ορισμό της μαθηματικής σταθεράς e,

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

Δυναμοσειρές τριγωνομετρικών συναρτήσεων

Η συνάρτηση του ημιτόνου μπορεί να οριστεί ως εξής:

${\displaystyle \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}.}$

Επίσης, η συνάρτηση του συνημιτόνου μπορεί να οριστεί ως εξής:

${\displaystyle \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}.}$

Σειρά Τέιλορ

Η σειρά Τέιλορ μίας πραγματικής συνάρτησης ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$ στο σημείο ${\displaystyle a\in \mathbb {R} }$ είναι η δυναμοσειρά

${\displaystyle 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}.}$

Υπολογισμός

Παρακάτω δίνονται οι δύο κλασσικές υλοποιήσεις για τον υπολογισμό του παραγοντικού: η αναδρομική και η γραμμική υλοποίηση. Σε γλώσσες προγραμματισμού με ακεραίους πεπερασμένου μεγέθους ο παρακάτω κώδικας θα οδηγήσει σε υπερχείλιση όταν το ${\displaystyle \nu }$ είναι μεγάλο. Και οι δύο αλγόριθμοι χρησιμοποιούν ${\displaystyle \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;
}

Αντιπαραγοντικό

Το αντιπαραγοντικό ενός φυσικού αριθμού ${\displaystyle \nu }$ συμβολίζεται με ${\displaystyle$ !\nu } , διαβάζεται νι αντιπαραγοντικό, και είναι το πηλίκο όλων των θετικών ακέραιων μικρότερων ή ίσων με ${\displaystyle \nu }$, δηλαδή

${\displaystyle$ !\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}},}

και συμβατικά ${\displaystyle !0=1}$.

Το αντιπαραγοντικό ${\displaystyle$ !\nu } μας δίνει η πιθανότητα εντοπισμού μίας συγκεκριμένης μετάθεσης από το σύνολο των ${\displaystyle \nu$ !} μεταθέσεων. Για παράδειγμα, το σύνολο ${\displaystyle 2!=2}$, μας δίνει τις μεταθέσεις: ${\displaystyle 1,2}$ και ${\displaystyle 2,1}$. Η πιθανότητα εύρεσης της επιθυμητής μετάθεσης (${\displaystyle 1,2}$ ή ${\displaystyle 2,1}$), δίνεται από το αντιπαραγοντικό του ${\displaystyle 2}$ δηλαδή ${\displaystyle !2=1/2!=1/2=0.5}$, συνεπώς ${\displaystyle 50\%}$.

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

Δείτε επίσης

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

Παραπομπές

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.

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

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

Commons logo

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