Belltal

Belltal är uppkallade efter Eric Temple Bell och är inom matematik en följd av tal, som beskriver hur många partitioner en mängd har, eller med en ekvivalent formulering, hur många ekvivalensrelationer det finns på mängden. De första Belltalen är:

B₀, B₁... = 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …

Tolkning

Det n:te Belltalet B_n är antalet sätt att partitionera en mängd med n element, det vill säga på hur många sätt man kan dela upp mängden i delmängder sådana, att ett element från mängden finns i en och endast en av delmängderna och att ingen av delmängderna är tom.

En annan tolkning är, antalet sätt att lägga n särskiljbara kulor i n icke särskiljbara lådor. Om man exempelvis har tre kulor, a, b och c, och därmed tre lådor, så kan man lägga kulorna i lådorna på fem olika sätt, nämligen:

Observera här att lådorna alltså är icke särskiljbara. Det medför att, om exempelvis alla kulor hamnar i en och samma låda så räknas det, som samma partition, som om alla kulor hade hamnat tillsammans i någon av de andra lådorna.

Egenskaper

Belltal uppfyller rekursionformeln

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}}$ där ${\displaystyle n\geq 0,B_{0}=1}$. ^[1]

Belltal kan också uttryckas som summor av Stirlingtal av andra slaget:

${\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}}$

där ett Stirlingtal av andra slaget är antalet sätt att partitionera en mängd med n element i k icke-tomma delmängder. En generalisering av Spivey (2008) är

${\displaystyle B_{n+m}=\sum _{k=0}^{n}\sum _{j=0}^{m}\left\{{m \atop j}\right\}{n \choose k}j^{n-k}B_{k}.}$

Belltalen kan även skrivas som

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}\,.}$

Genererande funktioner

Belltalens genererande funktion är

${\displaystyle \sum _{n=0}^{\infty }B_{n}\,x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!\,(1-kx)}}\,}$

De har den exponentiella genererande funktionen

${\displaystyle \sum _{k=0}^{\infty }{\frac {B_{k}}{k!}}z^{k}=e^{e^{z}-1}}$.

Modulär aritmetik

Belltalen satisfierar Touchards kongruens: om p är ett primtal är

${\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}{\pmod {p}}.}$

En generalisering är

${\displaystyle B_{p^{m}+n}\equiv mB_{n}+B_{n+1}{\pmod {p}}.}$

Av Touchards kongruens följer att Belltalen är periodiska modulo p för alla primtal p.

Logaritmisk konkavitet

Belltalen bildar en logaritmiskt konvex följd. Följden B_n/n! är logaritmiskt konkav.

Beräkning

Direkt beräkning

Den mest direkta metoden att beräkna belltal är att räkna ut på hur många olika sätt man kan lägga till ytterligare ett element till de möjliga partitionerna av en mängd som består av ett element mindre (vi ökar antalet element från ${\displaystyle n}$ till ${\displaystyle n+1}$). Man finner då att man antingen kan lägga till elementet som en egen delmängd eller lägga till det i en existerande delmängd i en partition. I det första fallet kan man lägga till det som egen delmängd i varje partition, d.v.s. på ${\displaystyle B_{n}}$ sätt vilket ger ${\displaystyle B_{n}}$ unika partitioner. I det andra fallet kan man lägga till det till varje delmängd i de ${\displaystyle B_{n}}$ partitionerna.

Om antalet partitioner av en mängd med ${\displaystyle n}$ element vilka består av ${\displaystyle d}$ delmängder betecknas med ${\displaystyle B_{n,d}}$, även kallat stirlingtalet av andra slaget ${\displaystyle \left\{{\begin{matrix}n\\d\end{matrix}}\right\}}$ , fås att antalet unika partitioner som kan skapas på detta sätt blir ${\displaystyle \sum _{d=1}^{n}dB_{n,d}}$ (vi kan ju stoppa in vårt "nya" element i de ${\displaystyle d}$ olika delmängderna i varje partition). Vi får alltså att ${\displaystyle B_{n+1}=B_{n}+\sum _{d=1}^{n}dB_{n,d}=\sum _{d=1}^{n}(d+1)B_{n,d}}$.

Det sista steget erhålls eftersom det är trivialt att ${\displaystyle B_{n}=\sum _{d=1}^{n}B_{n,d}(=\sum _{d=1}^{n}\left\{{\begin{matrix}n\\d\end{matrix}}\right\})}$, det vill säga att antalet sätt att partitionera mängden är lika med summan av antalet partitioner för varje antal delmängder.

För vidare beräkningar måste vi också beräkna ${\displaystyle B_{n+1,d}}$, vilket blir lika med summan av de partitioner som innehöll ${\displaystyle d-1}$ delmängder och där vi lade till det nya elementet som en egen delmängd och det antal sätt som vi kunde lägga till det nya elementet i de tidigare existerande partitionerna med ${\displaystyle d}$ element (inga ytterligare delmängder skapades ju i dessa fall), det vill säga på ${\displaystyle dB_{n,d}}$ sätt. Sålunda får vi ${\displaystyle B_{n+1,d}=B_{n,d-1}+dB_{n,d}}$ (här är såklart ${\displaystyle B_{n,0}=0}$ för ${\displaystyle n>0}$).

Exempel: Vi börjar med en mängd som består av ett element kallat 1, vilken endast kan delas upp på ett sätt: {1}. Ett andra element, 2, kan antingen läggas till som en egen delmängd så att vi får partitionen {1}{2} eller läggas till den tidigare vilket ger {1,2}. Vi har nu två partitioner, en som består av en delmängd och en som består av två. Ett tredje element, 3, kan läggas till som en ny delmängd i de båda partitionerna, vilket ger {1}{2}{3} och {1,2}{3}, eller läggas till i de olika delmängderna i de båda partitionerna. Lägger vi till det till {1,2} får vi en partition {1,2,3}, medan vi får två olika partitioner om vi lägger till det till {1}{2}: {1,3}{2} och {1}{2,3}. Vi får sålunda fem olika partitioner med tre element: en bestående av en delmängd, tre bestående av två delmängder och en bestående av tre delmängder.

Peirces metod

Charles Peirce presenterade följande metod att beräkna Belltal 1880.^[2]

Belltalen kan räknas ut som den vertikala kolonnen längst till vänster i följande triangel:

där talet P_{n, k} på rad n och i kolonn k uppfyller

${\displaystyle P_{n,k}=P_{n-1,k}+P_{n,k+1}\quad {\textrm {och}}\quad P_{n,n}=P_{n-1,1}~~{\textrm {om}}~~n>1}$.

Det vill säga att när man har fyllt en rad tar man talet längst till vänster och sätter längst till höger på nästa rad. För att fylla det ej ifyllda elementet längst till höger på en påbörjad rad, addera talet till höger och talet ovanför, fortsätt tills raden är full och upprepa hela proceduren.

"Härledning"

Låt ${\displaystyle P_{n,k}}$ beteckna antalet partitioner av en mängd med ${\displaystyle n}$ element som innehåller en delmängd med ${\displaystyle k}$ som lägsta element och skriv dem på en rad för varje ${\displaystyle n}$ med början på ${\displaystyle k=1}$. Då anger det tal som står längst till vänster, i första kolonnen, det antal partitioner som innehåller en delmängd som har 1 (det lägsta elementet i mängden) som lägsta element. Eftersom alla partitioner innehåller en delmängd med det lägsta elementet som lägsta element så är talet i den första kolonnen, ${\displaystyle P_{n,1}}$, lika med antalet partitioner, det vill säga ${\displaystyle B_{n}}$.

Talet längst till höger, ${\displaystyle P_{n,n}}$ anger hur många partitioner som har ${\displaystyle n}$ som lägsta element i en delmängd, det vill säga att denna delmängd endast består av det högsta elementet ${\displaystyle n}$. De övriga ${\displaystyle n-1}$ elementen kan partitioneras på ${\displaystyle B_{n-1}}$ sätt, ett tal som alltså är lika med ${\displaystyle P_{n-1,1}}$: talet som står längst till vänster i raden ovanför - vi flyttar alltså ner detta tal till kolonn ${\displaystyle n}$ i vår "nya" rad.

Talet näst längst till höger, ${\displaystyle P_{n,n-1}}$, anger hur många partitioner som har en delmängd med ${\displaystyle n-1}$ som lägsta element. Denna delmängd kan se ut på två olika sätt: antingen innehåller den ${\displaystyle n-1}$ som enda element (de återstående ${\displaystyle n-1}$ elementen kan partitioneras på ${\displaystyle B_{n-1}}$ olika sätt) eller så innehåller det också elementet ${\displaystyle n}$ (och de återstående ${\displaystyle n-2}$ elementen kan partitioneras på ${\displaystyle B_{n-2}}$ olika sätt). Men, eftersom ${\displaystyle B_{n-1}=P_{n-1,1}=P_{n,n}}$ och ${\displaystyle B_{n-2}=P_{n-2,1}=P_{n-1,n-1}}$ så får vi att ${\displaystyle P_{n,n-1}=P_{n,n}+P_{n-1,n-1}}$, det vill säga summan av talet rakt åt höger och talet rakt uppåt.

${\displaystyle P_{n,n-2}}$ anger hur många delmängder som har ${\displaystyle n-2}$ som lägsta element och det finns två element som är större än detta. Inget, ett eller båda dessa kan ingå i samma delmängd som ${\displaystyle n-2}$, vilket kan göras på ett, två respektive ett sätt (binomialfördelning!) och de återstående elementen kan partitioneras på ${\displaystyle B_{n-1}}$, ${\displaystyle B_{n-2}}$ respektive ${\displaystyle B_{n-3}}$ sätt. Vi får sålunda: ${\displaystyle P_{n,n-2}=B_{n-1}+2B_{n-2}+B_{n-3}=P_{n,n}+2P_{n-1,n-1}+P_{n-2,n-2}}$, men vi visade ju ovan att ${\displaystyle P_{n,n}+P_{n-1,n-1}=P_{n,n-1}}$ och ${\displaystyle P_{n-1,n-1}+P_{n-2,n-2}=P_{n-1,n-2}}$, vilket ger oss att ${\displaystyle P_{n,n-2}=P_{n,n-1}+P_{n-1,n-2}}$, det vill säga summan av talet rakt till höger och talet rakt ovanför.

Av resonemanget ovan framgår förhoppningsvis att ${\displaystyle P_{n,n-x}=\sum _{j=0}^{x}{\binom {x}{j}}B_{n-j-1}=\sum _{j=0}^{x}{\binom {x}{j}}P_{n-j,n-j}}$. (Notera att om vi sätter x=n-1 får vi rekursionsformeln för belltalen, vars härledning ju följer samma resonemang.)

Utgå nu från ett godtyckligt tal i tabellen, ${\displaystyle P_{n,n-x}}$ och beteckna talet ovanför detta med ${\displaystyle U}$ och talet till höger med ${\displaystyle H}$. Med vår metod att beräkna talen i tabellen är ${\displaystyle P_{n,n-x}=U+H}$. ${\displaystyle U}$ är i sin tur summan av talet ovanför och till höger, det vill säga ${\displaystyle U=UU+UH}$ och på samma sätt är ${\displaystyle H=HU+HH}$, och sålunda är ${\displaystyle P_{n,n-x}=U+H=UU+UH+HU+HH=UUU+UUH+UHU+UHH+HUU+HUH+HHU+HHH=...}$ tills vi hamnar i den högra diagonalen som består av talen ${\displaystyle P_{n,n}}$ till ${\displaystyle P_{n-x,n-x}}$. Vi ser att vi får varje möjlig "sträng" bestående av x stycken tecken, ${\displaystyle U}$ eller ${\displaystyle H}$, en och endast en gång och att antalet ${\displaystyle U}$ (eller ${\displaystyle H}$) i strängen avgör på vilken rad vi hamnar. Vi får alltså (med hjälp av binominalfördelningen igen) ${\displaystyle P_{n,n-x}=\sum _{j=0}^{x}{\binom {x}{j}}P_{n-j,n-j}}$ igen, och vi har därigenom visat att en tabell som konstrueras på detta sätt anger hur många delmängder det finns av en mängd med n element som har n-x som minsta element.

Tillväxt

Flera resultat om Belltalens tillväxt är kända. Ett exempel är följande:

${\displaystyle B_{n}<\left({\frac {0.792n}{\ln(n+1)}}\right)^{n}~.}$

Om ${\displaystyle \varepsilon >0}$ gäller för alla ${\displaystyle n>n_{0}(\varepsilon )}$

${\displaystyle B_{n}<\left({\frac {e^{-0.6+\varepsilon }n}{\ln(n+1)}}\right)^{n}}$

där ${\displaystyle ~n_{0}(\varepsilon )=\max \left\{e^{4},d^{-1}(\varepsilon )\right\}~}$ och ${\displaystyle ~d(x):=\ln \ln(x+1)-\ln \ln x+{\frac {1+e^{-1}}{\ln x}}\,.}$ Belltalen kan även approximeras med hjälp av Lamberts W-funktion:

${\displaystyle B_{n}\sim {\frac {1}{\sqrt {n}}}\left({\frac {n}{W(n)}}\right)^{n+{\frac {1}{2}}}\exp \left({\frac {n}{W(n)}}-n-1\right).}$

Referenser

• Knuth, Donald (2011). The Art of Computer Programming, Volume 4A, Combinatorial Algorithms. ISBN 978-0-201-03804-0 

Noter