Bell nummer

I kombinatoriske matematik, Bell numre tælle antallet af partitioner af et sæt. Disse numre er blevet undersøgt af matematikere siden det 19. århundrede, og deres rødder går tilbage til middelalderens Japan, men de er opkaldt efter Eric Temple Bell, der skrev om dem i 1930'erne.

Startende med B0 = B1 = 1, de første par Bell numre er:

Den n'te af disse numre, Bn, tæller antallet af forskellige måder at partitionere et sæt, der har præcis n elementer, eller ækvivalent, at antallet af ækvivalens relationer på det. Uden for matematik, det samme antal tæller også antallet af forskellige rim ordninger for n-line digte.

Samt optræder i tælle problemer, disse numre har en anden fortolkning, som øjeblikke af sandsynlighedsfordelinger. Især Bn er den n'te øjeblik en Poisson-fordeling med middelværdi 1.

Hvad disse tal tæller

Set skillevægge

Generelt Bn er antallet af partitioner af et sæt størrelse n. En opdeling af et sæt S er defineret som et sæt af ikke tom, parvise disjunkte delmængder af S, hvis union S. For eksempel B3 = 5, fordi 3-element sæt {a, b, c} kan partitioneres på 5 forskellige måder :

B0 er 1, fordi der er præcis én partition på den tomme mængde. Hvert medlem af den tomme sæt er en ikke tom sæt, og deres forening er den tomme mængde. Derfor den tomme mængde er den eneste partition for sig selv. Som foreslået af den indstillede notation ovenstående, mener vi hverken rækkefølgen af ​​skillevægge eller rækkefølgen af ​​elementer inden for hver partition. Dette betyder, at følgende skillevægge alle være identiske:

Hvis man i stedet forskellige orderings af sættene anses for at være forskellige skillevægge, så antallet af disse bestilte partitioner er givet ved de bestilte Bell numre.

Factorizations

Hvis et nummer N er et squarefree nummer, så Bn giver antallet af forskellige multiplikative skillevægge af N. Disse er factorizations N til tal større end én, behandle to factorizations som det samme, hvis de har de samme faktorer i en anden rækkefølge. For eksempel, 30 er produktet af de tre primtal 2, 3 og 5, og har fem factorizations:

Rhyme ordninger

Bell tal tæller også rim ordninger af en n-line digt eller strofe. En rim ordning beskriver, hvilke linier rimer med hinanden, og så kan fortolkes som en partition af sættet af linjer i rhyming delmængder. Rhyme ordninger er som regel skrevet som sekvens af latinske bogstaver, én pr linje, med rimede linjer får samme brev som hinanden, og med de første linjer i hvert rhyming sæt mærket i alfabetisk rækkefølge. Således er de 15 mulige fire linjer rim ordninger er AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC og ABCD.

Permutationer

Bell tal kommer op i et kort blander problem, der nævnes i tillægget til Gardner. Hvis et spil n kort blandes ved gentagne gange at fjerne det øverste kort og genindsætte den overalt i bunken, med præcis n gentagelser af denne operation, så er der n forskellige blander, der kan udføres. Af disse, det nummer, der vender tilbage dækket til sin oprindelige sorteret orden er præcis Bn. Således er sandsynligheden for at dækket er i sin oprindelige rækkefølge efter blander det på denne måde er Bn / n, hvilket er betydeligt større end 1 / n! sandsynlighed for, at ville beskrive en ensartet tilfældig permutation af dækket.

Relateret til kortet blander er flere andre problemer med at tælle særlige former for permutationer, der også besvaret af Bell numre. For eksempel den n'te Bell antal lig antallet af permutationer på n elementer, hvor der ikke tre værdier, der er i sorteret orden har de sidste to af disse tre på hinanden følgende. I en notation for generaliserede permutation mønstre, hvor værdier, der skal være fortløbende er skrevet ved siden af ​​hinanden, og værdier, der kan vises ikke-fortløbende er adskilt af en streg, kan disse permutationer beskrives som de permutationer, som undgår mønstret 1-23. De permutationer, der undgår de generaliserede mønstre 12-3, 32-1, 3-21, 1-32, 3-12, 21-3, og 23-1 også tælles af Bell numre. De permutationer, hvor hver 321 mønster kan udvides til en 3241 mønster også tælles af Bell numre. Imidlertid vokser, Bell numre for hurtigt at tælle permutationer, der undgår et mønster, der ikke er generaliseret på denne måde: ved Stanley-Wilf formodninger, antallet af sådanne permutationer er enkeltvis eksponentiel, og Bell numre har en højere asymptotiske vækst sats end det.

Trekant ordning for beregninger

Bell tal kan nemt beregnes ved at skabe den såkaldte Bell trekant, også kaldet Aitken s matrix eller Peirce trekanten efter Alexander Aitken og Charles Sanders Peirce.

  • Start med nummer et. Sætte dette på en række af sig selv.
  • Start en ny række med længst til højre element fra den foregående række som yderst til venstre nummer
  • Bestem tallene ikke på den venstre kolonne ved at tage summen af ​​antallet til venstre og antallet ovenfor nummeret til venstre
  • Gentag trin tre indtil der er en ny række med endnu et tal end den foregående række
  • Tallet på venstre side af en given række er Bell nummer for den pågældende række.

Her er de første fem rækker af trekanten bygget af disse regler:

Bell-numre vises på både venstre og højre side af trekanten.

Egenskaber

Additionsformlen

Bell tal tilfredsstille en gentagelse relation involverer binomialkoefficienter:

Det kan forklares ved at bemærke, at ud fra en vilkårlig partition af n + 1 elementer, fjerner sættet indeholder den første vare forlader en partition af et mindre sæt af k varer et bestemt antal k, der kan ligge i området fra 0 til n. Der er valg til k elementer, der er tilbage efter et sæt er fjernet, og Bk valg af, hvordan man kan opdele dem.

En anden summation formel repræsenterer hver Bell nummer som en sum af Stirling antal af anden art

Stirling nummer er antallet af måder at partitionere et sæt af kardinalitet n ind præcis k nonempty delmængder. Således i ligning, der forbinder Bell numre til Stirling tal, er hver partition tælles på venstre side af ligningen talt i præcis én af betingelserne i summen på højre side, det, som k er antallet af apparater i skillevæggen.

Spivey har givet en formel, der kombinerer begge disse summationer:

Frembringende funktion

Den eksponentielle frembringende funktion af klokken numre

I denne formel summation i midten er den generelle form, der anvendes til at definere den eksponentielle frembringende funktion for enhver sekvens af tal, og formlen til højre er resultatet af summeringen udføres i det specifikke tilfælde af klokken numre.

En måde at udlede dette resultat anvender analytiske kombinatorik, en form for matematisk begrundelse som fastsætter af matematiske objekter er beskrevet af formlerne forklarer deres konstruktion af enklere genstande, og derefter disse formler er manipuleret til at udlede de kombinatoriske egenskaber for objekterne. På det sprog, analytiske kombinatorik, kan et sæt partition kan beskrives som et sæt nonempty urner i hvilke elementer mærket fra 1 til n er blevet fordelt, og det kombinatoriske klasse alle partitioner kan udtrykkes ved notationen

Her er et kombinatorisk klasse med kun et enkelt medlem af størrelse en, et element, der kan placeres i en urne. Den indre operatør beskriver et sæt eller urne, der indeholder en eller flere mærkede elementer, og den ydre beskrives den overordnede partition som et sæt af disse urner. Den eksponentielle frembringende funktion kan derefter aflæses fra denne notation ved at oversætte operatøren i den eksponentielle funktion og nonemptiness tvang ≥1 ind subtraktion efter én.

En alternativ metode til at udlede den samme frembringende funktion bruger gentagelse forhold til Bell numre i form af binomialkoefficienter at vise, at den eksponentielle frembringende funktion tilfredsstiller differentialligningen. Selve funktionen kan findes ved at løse denne ligning.

Øjeblikke af sandsynlighedsfordelinger

Bell numre tilfredsstille Dobinski formel

Denne formel kan udledes ved at udvide den eksponentielle frembringende funktion ved hjælp af Taylor serie for eksponentialfunktionen, og derefter indsamle vilkår med samme eksponent. Det gør det muligt Bn fortolkes som den n'te øjeblik af en Poisson-fordeling med middelværdi 1.

Den n'te Bell nummer er også summen af ​​koefficienterne i n'te komplette Bell polynomium, som udtrykker den n'te øjeblik given sandsynlighedsfordeling som en funktion af de første n kumulanter.

Modulær aritmetik

Bell numre adlyder Touchard s kongruens: Hvis p er nogen primtal derefter

eller, generalisere

På grund af Touchard s kongruens, Bell numre er periodiske modulo p, for hver primtal p; for eksempel, for p = 2, gentage Bell numre mønstret ulige-ulige-selv med perioden tre. Perioden for denne gentagelse, for et vilkårligt primtal p, skal være en divisor af

for alle p op til 101 er det netop dette nummer.

Integral repræsentation

En anvendelse af Cauchys integreret formel til den eksponentielle frembringende funktion giver den komplekse integreret repræsentation

Nogle asymptotiske repræsentationer kan derefter udledes ved en standard anvendelse af metoden til stejleste nedkørsel.

Log-konkavitet

Bell tal danner en logaritmisk konveks sekvens. Dividere dem af fakulteterne, Bn / n !, giver en logaritmisk konkav sekvens.

Vækstrate

Adskillige asymptotiske formler for Bell antal er ukendt. I Berend & amp; Tassa følgende grænser blev fastlagt:

Desuden, hvis derefter for alle,

hvor og The Bell numre kan også tilnærmes ved hjælp af Lambert W-funktion, en funktion med samme vækstrate som logaritmen, som

Moser & amp; Wyman etableret udvidelsen

ensartet så, hvor og hver og er kendt udtryk i.

Den asymptotiske ekspression

blev etableret af de Bruijn.

Bell primtal

Gardner rejst spørgsmålet om, hvorvidt uendeligt mange Bell numre er også primtal. De første par Bell tal, der er primtal er:

svarende til indeksene 2, 3, 7, 13, 42 og 55.

Den næste Bell prime er B2841, hvilket er ca. 9,30740105 × 10. Fra 2006, det er den største kendte primtal Bell nummer. Phil Carmody viste det var en sandsynlig premierminister i 2002. Efter 17 måneders beregning med Marcel Martins ECPP program Primo, Ignacio Larrosa Canestro bevist, at det er prime i 2004. Han udelukket andre mulige primtal under B6000, senere udvidet til B30447 af Eric Weisstein.

Historie

Bell numre er opkaldt efter Eric Temple Bell, der skrev om dem i 1938, efter et 1934 papir, hvor han studerede Bell polynomier. Bell har ikke krav på at have opdaget disse tal; i hans 1938 papir, skrev han, at Bell-numre "er blevet hyppigt undersøgt" og "er blevet genopdaget mange gange". Bell citerer flere tidligere publikationer om disse tal, der begynder med Dobiński som giver Dobinski formel for Bell numre. Bell kaldte disse numre "eksponentielle tal"; navnet "Bell-numre" og notationen Bn for disse numre blev givet til dem af Becker & amp; Riordan.

Den første udtømmende opregning af sæt partitioner synes at have fundet sted i middelalderens Japan, hvor en selskabsleg kaldet Genji-ko sprang op, hvor gæsterne fik fem pakker af røgelse at lugte, og blev bedt om at gætte, hvilke der var de samme som hinanden og som var anderledes. De 52 mulige løsninger, optalt af Bell nummer B5, blev registreret med 52 forskellige diagrammer, der blev trykt over kapiteloverskrifterne i nogle udgaver af The Tale of Genji.

I Srinivasa Ramanujan anden notesbog, undersøgte han både Bell polynomier og Bell numre. Tidlige referencer for Bell trekant, som har de Bell numre på begge sine sider, omfatter Peirce og Aitken.

  0   0
Forrige artikel 19. Unge i Film Awards
Næste artikel Amy Oliver

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha