Belltal

Från Wikipedia
Hoppa till: navigering, sök

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:

B0, B1... = 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …

Tolkning[redigera | redigera wikitext]

Det n:te Belltalet Bn ä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:

Nr Låda Låda Låda
1 a, b, c
2 a, b c
3 a, c b
4 b, c a
5 a b c

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[redigera | redigera wikitext]

Belltal uppfyller rekursionformeln

B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k där n\ge0,  B_0 = 1.

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

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

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

B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}\,.

Genererande funktioner[redigera | redigera wikitext]

Belltalens genererande funktion är

\sum_{n=0}^\infty B_n\,x^n = \frac{1}{e} \sum_{k=0}^\infty \frac{1}{k!\,(1 - k x)}\,

De har den exponentiella genererande funktionen

\sum_{k=0}^\infty \frac{B_k}{k!} z^k = e^{e^z - 1}.


Modulär aritmetik[redigera | redigera wikitext]

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

B_{p+n}\equiv B_n+B_{n+1} \pmod{p}.

En generalisering är

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[redigera | redigera wikitext]

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

Beräkning[redigera | redigera wikitext]

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

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

1
2 1
5 3 2
15 10 7 5
52 37 27 20 15
203 151 114 87 67 52

där talet Bn, k på rad n och kolonn k uppfyller

B_{n, k} = B_{n-1, k} + B_{n, k+1} \quad \textrm{och} \quad B_{n, n} = B_{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.

Tillväxt[redigera | redigera wikitext]

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

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

Om  \varepsilon>0 gäller för alla  n > n_0(\varepsilon)

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

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

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[redigera | redigera wikitext]

Noter[redigera | redigera wikitext]

  1. ^ C.S. Pierce (1880). ”On The Algebra of Logic” (på engelska). American Journal of Mathematics 3 (1): sid. 15-57 (48).