Παραγοντικό

Στα μαθηματικά τ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!, αντί με τον κλειστό τύπο.

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

[right|thumb|300px|Η προσέγγιση του <math>\nu!</math> (και της συνεχής επέκτασής του με την [συνάρτηση γάμμα|συνάρτησης γάμμα) με τον τύπο του Στίρλινγκ.]]

Ο τύπος του Στίρλινγκ δίνει ότι
:
\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 είναι ισοδύναμες.

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

### Διατάξεις

### Ορισμός μαθηματικής σταθεράς <math>e</math>

Το παραγοντικό εμφανίζεται και στον εξής ορισμό της μαθηματικής σταθεράς 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 : \R \to \R στο σημείο a \in \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.
</math>

== Υπολογισμός ==

Παρακάτω δίνονται οι δύο κλασσικές υλοποιήσεις για τον υπολογισμό του παραγοντικού: η [[αναδρομή|αναδρομική]] και η γραμμική υλοποίηση. Σε [[γλώσσα προγραμματισμού|γλώσσες προγραμματισμού]] με ακεραίους πεπερασμένου μεγέθους ο παρακάτω κώδικας θα οδηγήσει σε [[Αριθμητική υπερχείλιση|υπερχείλιση]] όταν το <math>\nu</math> είναι μεγάλο. Και οι δύο αλγόριθμοι χρησιμοποιούν <math>\nu - 1</math> πολλαπλασιασμούς.

=== Αναδρομικός υπολογισμός ===

<syntaxhighlight lang="c++">
int factorial(int n) {
   if (n == 1) return 1;
   return n * factorial(n - 1);
}
</syntaxhighlight>

=== Γραμμικός υπολογισμός ===

<syntaxhighlight lang="c++">
int factorial(int n) {
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
      ans *= i;
   }
   return ans;
}
</syntaxhighlight>

== Αντιπαραγοντικό ==
Το *'αντιπαραγοντικό*' ενός φυσικού αριθμού <math>\nu</math> συμβολίζεται με <math>!\nu</math>, διαβάζεται *νι αντιπαραγοντικό,* και είναι το πηλίκο όλων των θετικών ακέραιων μικρότερων ή ίσων με <math>\nu</math>, δηλαδή
:<math>
!\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},
</math>
και συμβατικά <math>!0 = 1</math>.

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

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

== Δείτε επίσης ==
* [[Συνάρτηση γάμμα]]


== Παραπομπές ==
<references />

== Εξωτερικοί σύνδεσμοι ==
*  Weisstein, Eric W., «[https://mathworld.wolfram.com/Factorial.html Factorial]», από *MathWorld''.  Ανακτήθηκε 2020-07-22.

Κατηγορία:Αναλυτική θεωρία αριθμών
Κατηγορία:Συνδυαστική