Παραγοντικό

Πρότυπο:Math	Πρότυπο:Math
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	Πρότυπο:Val
8	Πρότυπο:Val
9	Πρότυπο:Val
10	Πρότυπο:Val
11	Πρότυπο:Val
12	Πρότυπο:Val
13	Πρότυπο:Val
14	Πρότυπο:Val
15	Πρότυπο:Val
16	Πρότυπο:Val
17	Πρότυπο:Val
18	Πρότυπο:Val
19	Πρότυπο:Val
20	Πρότυπο:Val
25	Πρότυπο:Val
50	Πρότυπο:Val
70	Πρότυπο:Val
100	Πρότυπο:Val
450	Πρότυπο:Val
Πρότυπο:Val	Πρότυπο:Val
Πρότυπο:Val	Πρότυπο:Val
Πρότυπο:Val	Πρότυπο:Val
Πρότυπο:Val	Πρότυπο:Val
Πρότυπο:Val	Πρότυπο:Val
Πρότυπο:Val	Πρότυπο:Val
Πρότυπο:Val	Πρότυπο:Val
[[Γκούγκολ|Πρότυπο:Val]]	10Πρότυπο:Val

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

$\nu !=1\cdot 2\cdot 3\cdot \dots \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$ στοιχεία ενός συνόλου. Για παράδειγμα, για το σύνολο $\mathrm{\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{array}{cc}1& \text{για }\nu =0,\\ \nu \cdot (\nu -1)!& \text{για }\nu \ge 1,\end{array}$

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

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

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

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

$(\genfrac{}{}{0ex}{}{\nu }{\kappa })=\frac{\nu !}{(\nu -\kappa )!\kappa !}.$

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

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

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

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

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

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

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

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

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

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

ή ισοδύναμα

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

Φράγματα

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

${\left(\frac{\nu }{e}\right)}^{\nu }\le \nu !\le 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$ είναι ισοδύναμες.

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

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

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

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

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

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

$\sin (x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\dots =\sum _{i=0}^{\mathrm{\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!}+\dots =\sum _{i=0}^{\mathrm{\infty }}\frac{(-1{)}^i}{(2i)!}\cdot x^{2i}.$

Σειρά Τέιλορ

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

$f(a)+\frac{f^{\prime }(a)}{1!}\cdot (x-a)+\frac{f^{″}(a)}{2!}\cdot (x-a{)}^2+\dots =\sum _{i=0}^{\mathrm{\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 \dots \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\mathrm{\%}$.

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

Δείτε επίσης

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

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

• Πρότυπο:En Weisstein, Eric W., «Factorial», από MathWorld. Ανακτήθηκε 2020-07-22.