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

Σχετικά με αυτόν τον υπολογιστή

Το υποπαραγοντικό !n, που ονομάζεται και πλήθος των διαταράξεων n στοιχείων, μετρά τις μεταθέσεις n αντικειμένων στις οποίες κανένα αντικείμενο δεν καταλήγει στην αρχική του θέση. Ορίζεται από τη σχέση !n = n! · Σ(k=0 έως n) (−1)^k/k! και για μεγάλο n προσεγγίζει πολύ το n!/e — μάλιστα το !n είναι ο πλησιέστερος ακέραιος στο n!/e. Για παράδειγμα, !4 = 9: από τις 24 μεταθέσεις 4 στοιχείων, μόνο οι 9 αφήνουν κάθε στοιχείο εκτός θέσης.

Το κλασικό παράδειγμα είναι το «πρόβλημα του ελέγχου καπέλων» (ή «πρόβλημα των λάθος διευθυνσιοδοτημένων επιστολών»): αν n άνθρωποι αφήνουν τα καπέλα τους και αυτά επιστρέφονται τυχαία, το !n είναι ο αριθμός των τρόπων με τους οποίους ο καθένας παίρνει πίσω λάθος καπέλο. Φοιτητές συνδυαστικής, μαθήματα πιθανοτήτων και λάτρεις των γρίφων χρησιμοποιούν υπολογισμούς υποπαραγοντικού για να λύνουν προβλήματα διαταράξεων, ενώ η έννοια επεκτείνεται στην κρυπτογραφία και στη θεωρία κωδίκων, όπου έχουν σημασία οι μεταθέσεις στις οποίες «τίποτα δεν μένει στην αρχική του θέση».