Pinatali

ΑΡΙΘΜΟΣ Bell

Από Βικιπαίδεια , η δωρεάν εγκυκλοπαίδεια

Στα συνδυαστικά μαθηματικά , οι αριθμοί Bell μετρούν τον αριθμό των χωρισμάτων ενός συνόλου. Αυτοί οι αριθμοί έχουν μελετηθεί από τους μαθηματικούς από τον 19ο αιώνα , και οι ρίζες τους επιστρέφουν στην Μεσαιωνική Ιαπωνία . αλλά ονομάστηκαν από τον Eric Temple Bell , ο οποίος έγραψε για αυτούς στην δεκαετία του 30' .

Ξεκινώντας με Β0 = Β1 = 1 , οι πρώτοι αριθμοί Bell είναι :

1 , 1 , 2 , 5 , 15 , 52 , 203 , 877 , 4140 , 21147 , 115975 , ....... ( ακολουθία Α000110 σε OEIS ).

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

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

       Περιεχόμενα 

1 Τι μετρούν αυτοί οι αριθμοί

 1.1 Καθορισμένα χωρίσματα
 1.2 Παραγοντοποιήσεις
 1.3 Συστήματα έμμετρου λόγου 
 1.4 Μεταθέσεις

2 Σχήμα τριγώνου για τους υπολογισμούς 3 Ιδιότητες

 3.1 Τύποι άθροισης 
 3.2 Παραγωγική λειτουργία
 3.3 Φάσεις της κατανομής πιθανότητας
 3.4 Αρθρωτή αριθμητική
 3.5 Ολοκληρωτική αναπαράσταση
 3.6 Σύνδεση - Κοιλότητα

4 Ρυθμός ανάπτυξης 5 Πρώτοι Bell 6 Ιστορία 7 Δείτε επίσης 8 Σημειώσεις 9 Αναφορές 10 Εξωτερικές συνδέσεις

Πίνακας περιεχομένων [Απόκρυψη] 1 Τι μετρούν αυτοί οι αριθμοί 1.1 Καθορισμένα χωρίσματα 1.2 Παραγοντοποιήσεις 1.3 Συστήματα έμμετρου λόγου 1.4 Μεταθέσεις 2 Σχήμα τριγώνου για τους υπολογισμούς 3 Ιδιότητες 3.1 Τύποι άθροισης 3.2 Παραγωγική Λειτουργία Τι μετρούν αυτοί οι αριθμοί[Επεξεργασία | επεξεργασία κώδικα] Καθορισμένα χωρίσματα[Επεξεργασία | επεξεργασία κώδικα]

     Κύριο άρθρο: χώρισμα ενός συνόλου

Γενικά , ο Bn είναι ο αριθμός των χωρισμάτων ενός συνόλου με μέγεθος n. Ένα χώρισμα ενός συνόλου S ορίζεται ως ένα σύνολο μη κενό , κατά ζεύγη ανεξάρτητων υποσυνόλων του S των οποίων η ένωση είναι S. Για παράδειγμα , Β3 = 5 , διότι το σύνολο 3 στοιχείων { α , β , γ } μπορεί να χωριστεί με 5 ευδιάκριτους τρόπους:

    { {α} , {β} , {γ} }
    { {α} , {β,γ} }
    { {β} , {α,γ} }
    { {γ} , {α,β} }
    { {α,β,γ } }

Ο Β0 ειναι 1 επειδή υπάρχει ακριβώς ένα χώρισμα του κενού συνόλου. Κάθε μέλος του κενού συνόλου είναι ένα μη κενό σύνολο ( αυτό είναι vacuously true ) , και η ένωσή τους είναι το κενό σύνολο. Επομένως , το κενό σύνολο είναι το μόνο χώρισμα του εαυτού του. Όπως προτείνεται από την καθορισμένη σημείωση παραπάνω , δεν εξετάζουμε ούτε την σειρά των χωρισμάτων ούτε την σειρά των στοιχείων σε κάθε χώρισμα. Αυτό σημαίνει ότι οι ακόλουθοι χωρισμοί θεωρούνται όλοι πανομοιότυποι.

    { {β}, {α, γ} }
    { {α, γ}, {β} }
    { {β}, {γ, α} }
    { {γ, α}, {β} }

Εάν , αντιθέτως , οι διαφορετικές διατάξεις των συνόλων θεωρούνται διαφορετικά χωρίσματα , τότε ο αριθμός αυτών των διαταγμένων χωρισμάτων δίνεται από τους διαταγμένουν αριθμούς Bell.

Παραγοντοποιήσεις[Επεξεργασία | επεξεργασία κώδικα] Εάν ένας αριθμός Ν είναι ένας αριθμός squarefree ( που σημαίνει ότι είναι το προϊόν κάποιου αριθμού Ν ευδιάκριτων πρωταρχικών αριθμών ) , έπειτα ο Βn δίνει τον αριθμό των διαφορετικών πολλαπλασιαστικών χωρισμάτων του Ν. Αυτές είναι παραγοντοποιήσεις του Ν σε αριθμούς μεγαλύτερους του ένα , θεωρώντας δύο παραγοντοποιήσεις ως ίδια εάν έχουν τους ίδιους παράγοντες με διαφορετική σειρά. Για παράδειγμα , 30 είναι το προϊόν των τριών πρώτων αριθμών 2 , 3 και 5 και έχει πέντε παραγοντοποιήσεις :

    30 Χ 1 = 2 Χ 15 = 3 Χ 10 = 5 Χ 6 = 2 Χ 3 Χ 5

Συστήματα έμμετρου λόγου[Επεξεργασία | επεξεργασία κώδικα] Οι αριθμοί Bell μετρούν επίσης τα συστήματα έμμετρου λόγου ενός ποιήματος ή στροφής ν στίχων. Ένα σύστημα έμμετρου λόγου περιγράφει ποιοι στίχοι ομοιοκαταληκτούν ο ένας με τον άλλον , και μπορεί να ερμηνευτεί ως ένα χώρισμα του συνόλου των στίχων στα υποσύνολα ομοιοκαταληξίας. Τα συστήματα έμμετρου λόγου συνήθως γράφονται ως ακολουθία Ρωμαϊκών επιστολών , μία ανά γραμμή , με τις ομοιοκαταληκτώντες γραμμές να δίνονται από το ίδιο γράμμα όπως κάθε άλλη , και με τις πρώτες γραμμές σε κάθε έμμετρο σύνολο επισημαίνονται με αλφαβητική σειρά. Έτσι , τα 15 πιθανά συστήματα έμμετρου λόγου τεσσάρων γραμμών είναι : ΑΑΑΑ , ΑΑΑΒ , ΑΑΒΑ , ΑΑΒΒ , ΑΑΒΓ , ΑΒΑΑ , ΑΒΑΒ , ΑΒΑΓ , ΑΒΒΑ , ΑΒΒΒ , ΑΒΒΓ , ΑΒΓΑ , ΑΒΓΒ , ΑΒΓΓ και ΑΒΓΔ.

Μεταθέσεις[Επεξεργασία | επεξεργασία κώδικα] Οι αριθμοί Bell εμφανίζονται σε ένα πρόβλημα μετάθεσης καρτών που αναφέρεται στην προσθήκη σε Gardner (1978). Αν μια τράπουλα ν καρτών ανακατεύονται με επαναλαμβανόμενη αφαίρεση της επάνω κάρτας και επανατοποθετηθεί ξανά οπουδήποτε στην τράπουλα ( συμπεριλαμβανομένης της αρχικής θέσης στην κορυφή της τράπουλας ) , με ακριβώς ν επαναλήψεις αυτής της λειτουργίας , τότε υπάρχουν νν ανακατέματα που μπορούν να εκτελεστούν. Από αυτούς , ο αριθμός που επιστρέφει απο την τράπουλα στην αρχική ταξινομημένη σειρά του είναι ακριβώς Βn. Έτσι , η πιθανότητα η τράπουλα να είναι στην αρχική της σειρά μετά το ανακάτεμα με αυτόν τον τρόπο είναι Bn / nn , το οποίο είναι σημαντικά μεγαλύτερο από το 1 / n πιθανότητα που θα περιέγραφε ένα ομοιόμορφο τυχαίο ανακάτεμα της τράπουλας.

Σχετικά με το ανακάτεμα της τράπουλας υπάρχουν διάφορα άλλα προβλήματα της καταμέτρησης των ειδικών ειδών των μεταθέσεων που απαντώνται από τους αριθμούς Bell. Για παράδειγμα , ο νιοστός αριθμός Bell είναι ίσος με τον αριθμό των μεταθέσεων ν στοιχείων στα οποία καμία από τις τρεις τιμές που βρίσκονται σε ταξινομημένη σειρά και έχουν τα δύο από αυτά τα τρία συνεχόμενα. Σε μια σημείωση για τα γενικευμένα σχέδια μετάθεσης όπου οι τιμές που πρέπει να είναι συνεχόμενες γράφονται η μία δίπλα στην άλλη , και οι τιμές που μπορούν να εμφανιστούν μη διαδοχικά χωρίζονται με μια παύλα , αυτές οι μεταθέσεις μπορούν να περιγραφούν ως μεταθέσεις που αποφεύγουν το σχέδιο 1-23. Οι μεταθέσεις που αποφεύγουν τα γενικευμένα σχέδια 12-3 , 32-1 , 3-21 , 1-32 , 3-12 , 21-3 , 23-1 και μετριούνται επίσης απο τους αριθμούς Bell. Οι μεταθέσεις στις οποίες κάθε σχέδιο 321 ( χωρίς περιορισμό στις διαδοχικές τιμές ) μπορεί να επεκταθεί σε ένα σχέδιο 3241 μετριούνται επίσης απο τους αριθμούς Bell. Ωστόσο οι αριθμοί Bell αυξάνονται πάρα πολύ γρήγορα για να μετρήσουν τις μεταθέσεις που αποφεύγουν ένα σχέδιο που δεν έχει γενικευθεί με αυτόν τον τρόπο: από την ( αποδεδειγμένα πλέον ) υπόθεση Stanley–Wilf , ο αριθμός των μεταθέσεων είναι μεμονωμένα εκθετικός , και οι αριθμοί Bell έχουν ένα υψηλότερο ασυμπτωτικό ρυθμό αύξησης απο αυτό.

Σχήμα τριγώνου για τους υπολογισμούς[Επεξεργασία | επεξεργασία κώδικα]

           Κύριο άρθρο : τρίγωνο Bell

Οι αριθμοί Bell μπορούν εύκολα να υπολογιστούν με τη δημιουργία του λεγόμενου τριγώνου Bell , ονομαζόμενο ακόμη ως σειρά Aitken ή τρίγωνο Peirce μετά από τον Alexander Aitken και τον Charles Sanders Peirce.

   1. Ξεκίνα με το νούμερο ένα. Βάλτο σε μια σειρά από μόνο του.
   2. Ξεκίνα μια νέα σειρά με το δεξιότερο στοιχείο από την προηγούμενη σειρά σαν το πιο αριστερό στοιχείο.
   3. Καθορίστε τους αριθμούς όχι στην αριστερή στήλη με την λήψη του αριθμού στα αριστερά και ο αριθμός πάνω από τον αριθμό στα αριστερά ( ο αριθμός πάνω διαγώνια και αριστερά του αριθμού που υπολογίζουμε ).
   4. Επαναλάβετε το τρίτο βήμα έως ότου υπάρχει μια νέα σειρά με ένα αριθμό περισσότερο από την προηγούμενη σειρά.
   5. Ο αριθμός στην αριστερή πλευρά μιας δεδομένης σειράς είναι ο αριθμός Bell για αυτή τη σειρά.

Εδώ είναι οι πρώτες πέντε σειρές του τριγώνου που κατασκευάζεται από αυτούς τους κανόνες.

1 1 2 2 3 5 5 7 10 15 15 20 27 37 52

Οι αριθμοί Bell εμφανίζονται τόσο στην αριστερή όσο και στην δεξιά πλευρά του τριγώνου.

Ιδιότητες[Επεξεργασία | επεξεργασία κώδικα] Τύποι άθροισης[Επεξεργασία | επεξεργασία κώδικα] Οι αριθμοί Bell ικανοποιούν μια σχέση επανάληψης που περιλαμβάνει τους δυωνυμικούς συντελεστές:

Αυτό μπορεί να εξηγηθεί από την παρατήρηση ότι από ένα αυθαίρετο χώρισμα ν+1 στοιχεία , αφαιρώντας το σύνολο που περιέχει το πρώτο στοιχείο αφήνουν ένα χώρισμα ενός μικρότερου συνόλου στοιχείων Κ για κάποιο αριθμό Κ που μπορεί να κυμαίνεται από 0 έως ν. Υπάρχουν επιλογές για τα στοιχεία Κ που απομένουν αφού αφαιρεθεί ένα σύνολο , και Βκ επιλογές για το πώς να τους χωρίσει.

Ένας διαφορετικός τύπος αθροίσματος αντιπροσωπεύει κάθε αριθμό Bell ως άθροισμα των αριθμών Stirling του δευτέρου είδους.

Ο αριθμός Stirling είναι ο αριθμός των τρόπων να χωριστεί ένα σύνολο στοιχείων ν ακριβώς σε μη κενά υποσύνολα Κ. Κατά συνέπεια , στην εξίσωση που συσχετίζει τους αριθμούς Bell με τους αριθμούς Stirling , κάθε χώρισμα στην αριστερή πλευρά της εξίσωσης υπολογίζεται σε ακριβώς έναν από τους όρους του αθροίσματος στη δεξιά πλευρά , για την οποία το Κ είναι ο αριθμός συνόλων στο χώρισμα.

Ο Spivey (2008) έδωσε έναν τύπο που συνδυάζει και τα δύο από αυτά τα αθροίσματα:

Παραγωγική Λειτουργία[Επεξεργασία | επεξεργασία κώδικα] Η εκθετική παραγωγική λειτουργία των αριθμών Bell είναι

Σε αυτό τον τύπο , το άθροισμα στη μέση είναι η γενική μορφή που χρησιμοποιείται για να καθορίσει την εκθετική παραγωγική λειτουργία για οποιαδήποτε ακολουθία αριθμών , και ο τύπος στα δεξιά είναι το αποτέλεσμα της εκτελέσεως του αθροίσματος στη συγκεκριμένη περίπτωση των αριθμών Bell.

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

Εδώ , είναι μια συνδυαστική κατηγορία με μόνο ένα ενιαίο μέλος ενός μεγέθους , ένα στοιχείο που μπορεί να τοποθετηθεί σε ένα δοχείο. Ο εσωτερικός χειριστής περιγράφει ένα σύνολο ή ένα δοχείο που περιλαμβάνουν ένα ή περισσότερα επισημασμένα στοιχεία , και το εξωτερικό περιγράφει το γενικό χώρισμα ως σύνολο αυτών των δοχείων. Η εκθετική παραγωγική λειτουργία μπορεί έπειτα να διαβαστεί από αυτήν την παράσταση με την μετάφραση του χειριστή στην εκθετική συνάρτηση και ο μη κενός περιορισμός ≥ 1