Υπολογιστής Παραγοντικού

Παραγοντικό του n (γράφεται ως n!) είναι το γινόμενο όλων των θετικών ακεραίων μέχρι το n. Για παράδειγμα, 5! = 5×4×3×2×1 = 120.

Τα παραγοντικά είναι θεμελιώδη στη συνδυαστική μέτρηση και τις πιθανότητες.

Οι μεταθέσεις μετρούν διευθετήσεις όπου η σειρά έχει σημασία (nPr). Οι συνδυασμοί μετρούν επιλογές όπου η σειρά δεν έχει σημασία (nCr).

Χρησιμοποιήστε τις μεταθέσεις για κατατάξεις και τους συνδυασμούς για ομάδες.

Για να υπολογίσετε ένα παραγοντικό n!, πολλαπλασιάστε όλους τους θετικούς ακέραιους από το 1 έως το n. Για παράδειγμα, 5! = 5 × 4 × 3 × 2 × 1 = 120, και 6! = 6 × 120 = 720.

Η ταχύτερη μέθοδος με το χέρι χρησιμοποιεί τον αναδρομικό κανόνα n! = n × (n−1)!, επομένως κάθε νέο παραγοντικό είναι απλώς το προηγούμενο αποτέλεσμα επί τον επόμενο ακέραιο. Αυτός ο υπολογιστής εφαρμόζει αυτή την αναδρομή εσωτερικά και στη συνέχεια εμφανίζει κάθε πολλαπλασιασμό ως βήμα.

Όπως σημειώνει το Wolfram MathWorld, το παραγοντικό ορίζεται για όλους τους μη αρνητικούς ακέραιους, και το 0! ορίζεται ως 1 για να διατηρείται η αναδρομή συνεπής.

Ο τύπος του παραγοντικού είναι n! = n × (n−1) × (n−2) × … × 2 × 1, με βασική περίπτωση 0! = 1. Ισοδύναμα, τα παραγοντικά ικανοποιούν την αναδρομική σχέση n! = n × (n−1)!, η οποία σας επιτρέπει να κατασκευάσετε κάθε τιμή από την προηγούμενη.

Η Ψηφιακή Βιβλιοθήκη Μαθηματικών Συναρτήσεων του NIST (NIST Digital Library of Mathematical Functions) επεκτείνει αυτή την ιδέα πέρα από τους ακέραιους μέσω της συνάρτησης γάμμα, όπου n! = Γ(n+1).

Για τη συνδυαστική χρησιμοποιούνται επίσης δύο παράγωγοι τύποι:

• μεταθέσεις nPr = n!/(n−r)!
• συνδυασμοί nCr = n!/[r!(n−r)!]

Αυτές οι τρεις εκφράσεις καλύπτουν τα περισσότερα προβλήματα μέτρησης που θα συναντήσετε στις πιθανότητες και τα διακριτά μαθηματικά.

Το 0! ισούται με 1 εξ ορισμού, και δεν πρόκειται για αυθαίρετη επιλογή. Υπάρχει ακριβώς ένας τρόπος να διατάξετε ένα κενό σύνολο αντικειμένων — να μην κάνετε τίποτα — οπότε το πλήθος των διατάξεων είναι ένα.

Ο ορισμός 0! = 1 διατηρεί επίσης έγκυρη την αναδρομή n! = n × (n−1)!, καθώς το 1! = 1 × 0! ισχύει μόνο αν 0! = 1. Επιπλέον, κάνει τύπους όπως ο nCr = n!/[r!(n−r)!] να επιστρέφουν το σωστό αποτέλεσμα όταν r = 0 ή r = n.

Το Khan Academy και η Encyclopaedia Britannica παρουσιάζουν και τα δύο το 0! = 1 ως την τυπική σύμβαση που διέπει τη συνδυαστική και το διωνυμικό θεώρημα.

Τα παραγοντικά αυξάνονται ταχύτερα από οποιαδήποτε εκθετική συνάρτηση, γι' αυτό και ο υπολογισμός με το χέρι γίνεται γρήγορα ανέφικτος. Για παράδειγμα:

• 5! = 120
• 10! = 3.628.800
• 20! = 2.432.902.008.176.640.000 — ήδη πάνω από 2,4 εξάκις εκατομμύρια

Στο 170! η τιμή είναι περίπου 7,26 × 10^306, κοντά στο όριο της τυπικής κινητής υποδιαστολής διπλής ακρίβειας, γι' αυτό και πολλά εργαλεία περιορίζουν την εισαγωγή στο 170.

Αυτή η υπερ-εκθετική αύξηση (τυπικά το n! αυξάνεται σύμφωνα με την προσέγγιση του Stirling √(2πn)(n/e)^n, όπως περιγράφεται στο NIST DLMF) εξηγεί γιατί τα παραγοντικά εμφανίζονται στους παρανομαστές των σειρών Taylor, όπου συρρικνώνουν τους όρους αρκετά γρήγορα ώστε η σειρά να συγκλίνει.

Ένα διπλό παραγοντικό n!! πολλαπλασιάζει κάθε δεύτερο ακέραιο ξεκινώντας από το n προς τα κάτω, σταματώντας στο 1 (περιττός n) ή στο 2 (άρτιος n). Για περιττούς αριθμούς, 7!! = 7 × 5 × 3 × 1 = 105· για άρτιους αριθμούς, 8!! = 8 × 6 × 4 × 2 = 384.

Δεν είναι το ίδιο με την εφαρμογή του παραγοντικού δύο φορές — το (n!)! θα ήταν τεράστιο συγκριτικά. Τα διπλά παραγοντικά εμφανίζονται σε ολοκληρώματα δυνάμεων ημιτόνου και συνημιτόνου και σε τύπους για τον όγκο σφαιρών πολλών διαστάσεων.

Το Wolfram MathWorld ταξινομεί το διπλό παραγοντικό ως ξεχωριστή συνάρτηση, ενώ η OEIS παραθέτει τα περιττά διπλά παραγοντικά 1, 3, 15, 105, 945 ως ακολουθία A001147.

Ένα υποπαραγοντικό !n μετρά τις απορρυθμίσεις (derangements) — μεταθέσεις στις οποίες κανένα στοιχείο δεν παραμένει στην αρχική του θέση. Για τρία αντικείμενα {1, 2, 3}, μόνο τα {2, 3, 1} και {3, 1, 2} πληρούν την προϋπόθεση, οπότε !3 = 2· παρόμοια, !4 = 9 και !5 = 44.

Το υποπαραγοντικό ακολουθεί τον τύπο !n = n! × Σ (−1)^k / k! για k = 0 έως n, και συνδέεται στενά με γρίφους πιθανοτήτων όπως το πρόβλημα του «ιματιοφυλακίου», όπου η πιθανότητα να μην πάρει κανείς το δικό του καπέλο πλησιάζει το 1/e ≈ 0,3679 καθώς το n μεγαλώνει.

Η OEIS καταγράφει τους αριθμούς απορρύθμισης 1, 0, 1, 2, 9, 44, 265 ως ακολουθία A000166.

Τα παραγοντικά βρίσκονται στη βάση κάθε προβλήματος που μετρά διατάξεις ή επιλογές.

• Στις πιθανότητες, ο αριθμός των διαφορετικών συνδυασμών 5 καρτών πόκερ από μια τράπουλα 52 καρτών είναι ο συνδυασμός 52C5 = 2.598.960.
• Στον προγραμματισμό και τη λογιστική (logistics), το n! δίνει το πλήθος των αλληλουχιών για n εργασίες ή στάσεις.
• Στον απειροστικό λογισμό, τα παραγοντικά βρίσκονται στους παρανομαστές των σειρών Taylor και Maclaurin, ελέγχοντας πόσο γρήγορα συρρικνόνονται οι όροι ώστε να μπορούν να προσεγγιστούν συναρτήσεις όπως η e^x και η sin x.

Εμφανίζονται επίσης στο διωνυμικό θεώρημα, σε στατιστικές κατανομές όπως η Poisson και η διωνυμική, καθώς και στη κρυπτογραφία. Το Khan Academy χρησιμοποιεί αυτούς τους συνδυαστικούς υπολογισμούς ως βάση του προγράμματος σπουδών του στις πιθανότητες.

Ορισμένα λάθη μπερδεύουν συχνά όσους εργάζονται με παραγοντικά:

• Το πιο συχνό λάθος είναι η παράβλεψη ότι 0! = 1, γεγονός που αχρηστεύει τους τύπους συνδυασμών και μεταθέσεων στα όριά τους.
• Ένα άλλο είναι η σύγχυση του διπλού παραγοντικού n!! (κάθε δεύτερος ακέραιος) με την εφαρμογή του παραγοντικού δύο φορές — 5!! = 15, αλλά το (5!)! είναι αστρονομικά μεγαλύτερο.
• Οι μαθητές μπερδεύουν επίσης τις μεταθέσεις και τους συνδυασμούς: χρησιμοποιήστε nPr όταν η σειρά έχει σημασία και nCr όταν δεν έχει, οπότε 5P2 = 20 αλλά 5C2 = 10.
• Προσοχή στις αρνητικές ή μη ακέραιες τιμές εισαγωγής, καθώς το στοιχειώδες παραγοντικό δεν ορίζεται εκεί (μόνο η συνάρτηση γάμμα το επεκτείνει).
• Τέλος, θυμηθείτε ότι τα παραγοντικά υπερχειλίζουν γρήγορα — πέρα από περίπου το 170!, οι περισσότεροι υπολογιστές χάνουν την ακρίβεια, όπως καθιστά σαφές η ανάλυση αύξησης του Wolfram MathWorld.

Τόσο οι μεταθέσεις όσο και οι συνδυασμοί βασίζονται απευθείας στα παραγοντικά.

Μια μετάθεση (διάταξη) nPr = n!/(n−r)! μετρά τις διατεταγμένες διευθετήσεις, οπότε η επιλογή και η διάταξη 2 από 5 αντικείμενα δίνει 5P2 = 5!/3! = 120/6 = 20.

Ένας συνδυασμός nCr = n!/[r!(n−r)!] μετρά μη διατεταγμένες επιλογές, οπότε 5C2 = 5!/(2!·3!) = 120/(2×6) = 10 — ακριβώς το μισό του 5P2, επειδή κάθε ζεύγος μπορεί να διαταχθεί με δύο τρόπους. Οι συνδυασμοί ονομάζονται επίσης διωνυμικοί συντελεστές και δημιουργούν το τρίγωνο του Πασκάλ. Επειδή ο τύπος nC2 = n(n−1)/2 είναι δευτεροβάθμιος ως προς n, η αντιστροφή της ερώτησης — η εύρεση του πόσα αντικείμενα παράγουν ένα δεδομένο αριθμό ζευγών, όπως στο κλασικό πρόβλημα με τις χειραψίες — αναγάγεται σε επίλυση δευτεροβάθμιας εξίσωσης.

Η Encyclopaedia Britannica περιγράφει αυτές τις πράξεις ως τις βασικές λειτουργίες της συνδυαστικής, και αυτός ο υπολογιστής υπολογίζει τα nPr και nCr εμφανίζοντας πλήρως τα βήματα.