Αριθμοί Μπελ

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση

Στη συνδυαστική, οι Αριθμοί Μπελ (αγγλικά: Bell numbers) μετρούν το πλήθος των Διαμερισμών ενός συνόλου. Αυτοί οι αριθμοί έχουν μελετηθεί από μαθηματικούς ήδη από το 19ο αιώνα , και οι ρίζες τους εντοπίζονται πίσω στη μεσαιωνική Ιαπωνία, αλλά έχουν πάρει το όνομά τους από τον Έρικ Τεμπλ Μπελ, που έγραψε γι' αυτούς περί το 1930.

Ξεκινώντας με B0 = B1 = 1, οι πρώτοι αριθμοί Μπελ είναι:

1, 1,2 , 5, 15, 52, 203, 877, 4140, 21147, 115975, …

Ο νιοστός από τους αριθμούς αυτούς, Bν, μετρά τον αριθμό των διαφορετικών τρόπων διαμέρισης ενός συνόλου που έχει ακριβώς n στοιχεία, ή ισοδύναμα, των αριθμό των σχέσεων ισοδυναμίαςσε αυτό. Πέραν των μαθηματικών, ο ίδιος αριθμός μετρά επίσης τις ομοιοκαταληξίες για ν-γραμμα ποιήματα.[1]

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

Τι μετρούν οι αριθμοί αυτοί[Επεξεργασία | επεξεργασία κώδικα]

Διαμερισμοί συνόλων[Επεξεργασία | επεξεργασία κώδικα]

Οι 52 διαμερίσεις ενός συνόλου 5 στοιχείων.

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

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

Το B0 είναι 1 επειδή υπάρχει ακριβώς μία διαμέριση στα κενά σύνολα. Κάθε μέλος ενός κενού συνόλου είναι ένα μη κενό σύνολο , και η ένωσή τους αποτελεί ένα κενό σύνολο. Επομένως, το κενό σύνολο είναι η μόνη διαμέριση του εαυτού του. Όπως υποδηλώνεται από το σύνολο σημάνσεων παραπάνω, δε μας απασχολέι ούτε η σειρά των διαμερίσεων ούτε η σειρά των στοιχείων σε κάθε διαμέριση . Αυτό σημαίνει πως οι ακόλουθες διαμερίσεις θεωρούνται όλες ταυτόσημες:

{ {β}, {α, γ} }
{ {α, γ}, {β} }
{ {β}, {γ, α} }
{ {γ, α}, {β} }
Αν, αντίθετα, οι διαφορετικές διατάξεις των συνόλων θεωρούνται διαφορετικά διαμερίσματα, τότε ο αριθμός τέτοιων διατεταγμένων διαμερίσεων δίνεται από τους διατεταγμένους αριθμούς Μπελ.

Παραγοντοποιήσεις[Επεξεργασία | επεξεργασία κώδικα]

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

Ομοιοκαταληξία[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ υπολογίζουν επίσης τα σχήματα ομοιοκαταληξίας ενός n-στιχου ποιήματος ή στροφής. Μία ομοιοκαταληξία περιγράφει ποιοι στίχοι ομοιοκαταληκτούν με ποιούς , και επομένως μπορεί να ερμηνευθεί ως μία διαμέριση ενός συνόλου στίχων σε ομοιοκατάληκτα υποσύνολα.Οι ομοιοκαταληξίες σημειώνονται συνήθως ως ακολουθίες ρωμαϊκών γραμμάτων, ενός ανά στίχο, με τους ομοιοκατάλληκτους στίχους να παίρνουν το ίδιο γράμμα, και τους πρώτους στίχους κάθε ομοιοκατάληκτου συνόλου να λαμβάνουν ετικέτα αλφαβητικής σειράς. Επομένως, οι 15 πιθανές ομοιοκαταληξίες ενός 4-στιχου ποιήματος είναι AAAA, AAAB, AABA, AABB, AABΓ, ABAA, ABAB, ABAΓ, ABBA, ABBB, ABBΓ, ABΓA, ABΓB, ABΓΓ, και ABΓΔ.[1]

Μεταθέσεις[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ εμφανίζονται σε ένα χαρτοπαικτικό πρόβλημα ανακατέματος που αναφέρει σε παράρτημά του ο Gardner (1978). Αν μία στίβα από n κάρτες ανακατεύεται με επαναλαμβανόμενη μετακίνηση της πάνω κάρτας και επανατοποθέτησης της οπουδήποτε στη στοίβα (συμπεριλαμβανομένης και της αρχικής της θέσης στην κορυφή της

στοίβας), με ακριβώς n επαναλήψεις αυτής της διαδικασίας, τότε υπάρχουν nn διαφορετικοί τρόποι ανακατέματος που μπορούν να πραγματοποιηθούν. Από αυτούς, ο αριθμός αυτών που επιστρέφει την τράπουλα στην αρχική της σειρά είναι ακριβώς Bn. Επομένως, η πιθανότητα η τράπουλα να επιστρέψει μετά το ανακάτεμα κατ'αυτόν τον τρόπο στην αρχική της σειρά είναι Bn/nn, που είναι σημαντικά μεγαλύτερη από την 1/n! πιθανότητα που θα περιέγραφε μία τυχαία μετάθεση της στοίβας.

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

Τριγωνικές διατάξεις για υπολογισμό[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ μπορούν εύκολα να υπολογισθούν με τη δημιουργία του λεγόμενου Τριγώνου Μπελ , το οποίο καλείται επίσης διάταξη του Aitken ή τρίγωνο του Pierce , από τους Αλεξάντερ Άιτκεν and Τσαρλς Σάντερς Περς.[5]

Παρακάτω βρίσκονται οι πέντε πρώτες σειρές του τριγώνου που κατασκευάζεται με τους παραπάνω κανόνες:

1. Ξεκίνα με το νούμερο ένα. Βάλτο σε μια σειρά από μόνο του.

    2. Ξεκίνα μια νέα σειρά με το δεξιότερο στοιχείο από την προηγούμενη σειρά σαν το πιο αριστερό στοιχείο.

    3. Καθορίστε τους αριθμούς όχι στην αριστερή στήλη με την λήψη του αριθμού στα αριστερά και ο αριθμός πάνω από τον αριθμό στα αριστερά ( ο αριθμός πάνω διαγώνια και αριστερά του αριθμού που υπολογίζουμε ).

    4. Επαναλάβετε το τρίτο βήμα έως ότου υπάρχει μια νέα σειρά με ένα αριθμό περισσότερο από την προηγούμενη σειρά.

    5. Ο αριθμός στην αριστερή πλευρά κάθε σειράς είναι ο αριθμός Μπελ για αυτή τη σειρά.

Παρακάτω βρίσκονται οι πέντε πρώτες σειρές του τριγώνου που κατασκευάζεται με τους παραπάνω κανόνες:

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

Οι αριθμοί Μπελ εμφανίζονται τόσο στις δεξιές όσο και στις αριστερές πλευρές του τριγώνου.

Ιδιότητες[Επεξεργασία | επεξεργασία κώδικα]

Τύποι άθροισης[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ ικανοποιούν μια επαναληπτική σχέση που περιλαμβάνει διωνυμικούς συντελεστές [5]

Μπορεί να εξηγηθεί παρατηρώντας ότι , από μια αυθέραιτη διαμέριση n + 1 αντικειμένων, αφαιρώντας το σύνολο που περιέχει το πρώτο αντικείμενο αφήνει μια διαμέριση από ένα μικρότερο σύνολο k αντικειμένων για κάποιον αριθμό k που λαμβάνει τιμές απο 0 έως n . Υπάρχουν επιλογές για τα k αντικείμενα που απομένουν μετά από όταν έχει αφαιρεθεί ένα σύνολο, και Bk επιλογές για το πως να τα διαμερίσουμε.

Έας διαφορετικός τύπος άθροισης αναπαριστά κάθε αριθμό Μπελ σαν άθροισμα αριθμών Στίρλινγκ δεύτερου είδους [:en:Stirling_numbers_of_the_second_kind]

Ο αριθμός Stirling είναι ο αριθμός των τρόπων διαμέρισης ενός συνόλου πληθικότητας n σε ακριβώς k μη-κενά υποσύνολα. Έτσι στην εξίσωση που συσχετίζει τους αριθμούς Μπελ με τους αριθμούς Stirling , κάθε διαμέριση μετριέται στο αριστερό μέλος της εξίσωσης μετριέται σε ακριβώς κάθε έναν από τους όρους του αθροίσματος στο δεξί μέλος, στο οποίο το k είναι ο αριθμός των συνόλων στη διαμέριση.

[6]
Ο Spivey (2008) έχει δώσει έναν τύπο που συνδιάζει και τις δύο αθροίσεις :

Γεννήτρια συνάρτηση[Επεξεργασία | επεξεργασία κώδικα]

Η εκθετική γεννήτρια συνάρτηση των αριθμών Μπελ είναι :

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

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

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

περιγράφει την συνολική διαμέριση ενός συνόλου αυτών των τεφροδόχων. Η εκθετική γεννήτρια συνάρτηση μπορe;i να διαβαστεί μεταφράζοντας τον τελεστή μέσα στην εκθετική συνάρτηση και την μη κενό περιορισμό ≥1 μέσα στην αφαίρεση από μία.[7]

Μια εναλλακτική μέθοδος για να παράγουμε την ίδια γεννήτρια συνάρτηση χρησιμοποιεί την επαναληπτική σχέση για τους αριθμούς Μπελ σε όρους από διωνυμικούς συντελεστές για να δείξουμε ότι η εκθετική συνάρτηση ικανοποιεί την διαφορική εξίσωση . Η συνάρτηση αυτή καθ'αυτή μπορεί να βρεθεί λύνοντας την εξίσωση [8] .

Στιγμές κατανομής πιθανότητας[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ ικανοποιούν τον τύπο του Ντομπίνσκι

Ο τύπος μπορεί να παραχθεί αναπτύσσοντας την εκθετική γεννήτρια συνάρτηση χρησιμοποιώντας σειρές Τέιλορ για την εκθετική συνάρτηση, και μετά μαζεύοντας τους όρους με τον ίδιο εκθέτη.[7]

Αφήνει το Bn να μπορεί να εκφραστεί σαν την n-οστή στιγμή μιας κατανομής Πουασσόν με προσδοκώμενη τιμή 1 .

Ο n-στός αριθμός Μπελ είναι επίσης το άθροισμα των συντελεστών στο n-στό πλήρες πολυώνυμο Μπελ , που εκφράζει την n-στή στιγμή από οποιαδήποτε κατανομή πιθανότητας σαν μια συνάρτηση από τους πρώτους n συσσωρεύσεις.

Αριθμητική με mod[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ υπακούν στην αναλογία του Touchard : Εάν p είναι ένας οποιοσδήποτε πρώτος αριθμός τότε

[9]

or, generalizing [10]

Λόγω της αναλογίας του Touchard, οι αριθμοί Μπελ είναι περιοδικοί modulo p , για κάθε πρώτο αριθμό p : για παράδειγμα , για p=2, οι αριθμοί Μπελ επαναλαμβάνουν το μοτίβο περιττός-περιττός-άρτιος με περίοδο τρία . Η περίοδος αυτής της επανάληψης, για έναν αυθαίρετο πρώτο αριθμό p , πρέπει να είναι διαιρέτης του

και για όλα τα p μέχρι το 101 είναι ακριβώς αυτός ο άνθρωπος .[11]

Αναπαράσταση σε ολοκλήρωμα[Επεξεργασία | επεξεργασία κώδικα]

Μια εφαρμογή του τύπου ολοκλήρωση του Κοσί στην εκθετική γεννήτρια συνάρτηση αποδίδει την αναπαράσταση σε μιγαδικό ολοκλήρωμα

Κάποιες ασυμπτωτικές αναπαραστάσεις μπορούν να παραχθούν από μια τυπική εφαρμογή της μεθόδου steepest descent [12]

Λογαριθμική κοιλότητα[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ σχηματίζουν μια λογαριθμική κυρτή ακολουθία . Διαιρώντας με τα παραγοντικά Bn/n! , δίνει μια λογαριθμική κοίλη ακολουθία [13]

Ρυθμός μεταβολής[Επεξεργασία | επεξεργασία κώδικα]

Αρκετοί ασυμπτωτικοί τύποι για τους αριθμούς Μπελ είναι γνωστοί. Στο Berend & Tassa (2010) τα ακόλουθα φράγματα εδραιώθηκαν :

επίσης , αν τότε για όλα τα

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

[14]

Οι Moser & Wyman (1955) εδραίωσαν το ανάπτυγμα
ανεπίσημα για όταν , όπου και κάθε και είναι γνωστές εκφράσεις στην .[15]
Η ασυμπτωτική έκφραση

εδραιώθηκε από τον de Bruijn (1981)

Πρώτοι αριθμοί Μπελ[Επεξεργασία | επεξεργασία κώδικα]

Ο Γκάρντνερ (1978) αναρωτήθηκε εάν υπάρχουν άπειροι αριθμοί Μπελ είναι επίσης πρώτοι αριθμοί . Οι πρώτοι αριθμοί Μπελ που είναι πρώτοι είναι οι :

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 .

που αντιστοιχούν στους δείκτες 2,3,7,13,42 και 55 .

Ο επόμενος Μπελ πρώτος είναι ο B2841 , που είναι περίπου 9.30740105 × 106538 [16]

Ο Phil Carmody έδειξε ότι είναι πιθανός πρώτος το 2002. Μετά από 17 μήνες υπολογισμών με το πρόγραμμα ECPP Primo του Marcel Martin, ο Ignacio Larrosa Cañestro απέδειξε ότι ήταν πρώτος το 2004. Απέκλεισε ότι υπάρχουν άλλοι πρώτοι κάτω από τον B6000 , που αργότερα επεκτάθηκε στον B30447 από τον Eric Weisstein .

Ιστορία[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί Μπελ έχουν πάρει το όνομα τους από τον Έρικ Τεμπλ Μπελ,ο οποίος έγραψε γι' αυτούς το 1938, μετά από ένα έγγραφο που δημοσιεύτηκε το 1934, στο οποίο μελέτησε τα πολυώνυμα Μπελ. Ο Μπελ δεν ισχυρίστηκε ότι είχε ανακαλύψει αυτούς τους αριθμούς: σε μια εργασία του το 1938 αλλά έγραψε ότι οι αριθμοί Μπελ ''είχαν συχνά διερευνηθεί'' και ''εκ νέου ανακαλυφθεί πολλές φορές''. Ο Μπελ επισημαίνει πολλές προηγούμενες δημοσιεύσεις πάνω σε αυτούς τους αριθμούς,ξεκινώντας με το Ντομπίνσκι (1877) τo οποίο έδωσε την φόρμουλα Ντομπίνσκι για τους αριθμούς Μπελ.Ο Μπελ ονόμασε αυτούς τους αριθμούς ''εκθετικούς αριθμούς'' ενώ η ονομασία ''Αριθμοί Μπελ'' και o συμβολισμός Bn για αυτούς τους αριθμούς δόθηκε από τους Μπέκερ & Ράιορνταν (1948).

Η πρώτη εξαντλητική απαρίθμηση των διαμερίσεων φαίνεται να έχει προκληθεί στην Μεσαιωνική Ιαπωνία, όπου(εμπνεόμενοι από την απήχηση του βιβλίου The Tale Of Genji) ένα παιχνίδι συναναστροφής με ονομασία gengi-ko, ξεπήδησε,στο οποίο οι παίκτες λάμβαναν πέντε πακέτα από θυμίαμα να μυρίσουν και καλούνταν να μαντέψουν ποιο ήταν ίδιο και ποιο διαφορετικό με το καθένα.Οι 52 πιθανές απαντήσεις,υπολογισμένες από τον αριθμό Μπελ B5, έχουν αναπαρασταθεί από 52 διαφορετικά διαγράμματα ,τα οποία τυπώθηκαν πάνω από τους τίτλους των κεφαλαίων σε μερικές εκδόσεις του The Tale of Genji.

Στο δεύτερο σημειωματάριο του Σρινιβάσα Ραμάνουτζαν,ανακάλυψε όχι μόνο τα πολυώνυμα Μπελ αλλά και τους αριθμούς Μπελ. Προηγούμενες αναφορές στο τρίγωνο του Μπελ, το οποίο είχε τους αριθμούς Μπελ και στις δύο πλευρές του είχαν συμπεριλάβει οι Περς(1880) και Άιτκεν(1933).

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. 1,0 1,1 Gardner (1978).
  2. Williams (1945) credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
  3. Claesson (2001).
  4. Callan (2006).
  5. Wilf (1994), p. 23.
  6. Conway & Guy (1996).
  7. 7,0 7,1 Flajolet & Sedgewick (2009).
  8. Rota (1964); Wilf (1994), pp. 20–23; Bender & Williamson (2006).
  9. Becker & Riordan (1948).
  10. Hurst & Schultz (2009).
  11. Williams (1945); Wagstaff (1996).
  12. Simon, Barry (2010). «Example 15.4.6 (Asymptotics of Bell Numbers)». Complex Analysis, σελ. 772–774. http://www.math.caltech.edu/~2010-11/2term/ma111b/CA-Sec15-4_march2.pdf. 
  13. Engel (1994); Canfield (1995); Asai, Kubo & Kuo (2000).
  14. Lovász (1993).
  15. Canfield, Rod (July 1994). «The Moser-Wyman expansion of the Bell numbers» (PDF). Ανακτήθηκε στις 2013-10-24. 
  16. «93074010508593618333...(6499 other digits)...83885253703080601131». 5000 Largest Known Primes, The Prime Database. Ανακτήθηκε στις 2013-10-24.