Dobińskis formel

I kombinatorisk matematik anger Dobińskis formel att det n -te Bell-talet B _n (dvs antalet partitioner i en uppsättning av storlek n ) är lika med

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

där $e$ anger Eulers tal . Formeln är uppkallad efter G. Dobiński, som publicerade den 1877.

Probabilistiskt innehåll

I inställningen av sannolikhetsteori representerar Dobińskis formel det n: te momentet av Poissonfördelningen med medelvärde 1. Ibland anges Dobińskis formel som att antalet partitioner av en uppsättning av storlek n är lika med det n :te momentet av den fördelningen.

Reducerad formel

Beräkningen av summan av Dobińskis serier kan reduceras till en ändlig summa av $n+o(n)$ termer, med hänsyn tagen till informationen som $B_{n}$ är ett heltal. Exakt en har, för vilket heltal som helst $K>1$

$B_{n}=\left\lceil {1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}\right \rceil$

förutsatt ${\frac {K^{n}}{K!}}\leq 1$ (ett villkor som naturligtvis innebär $K>n$ , men som uppfylls av vissa ${ \displaystyle K}$ av storlek $n+o(n)$ ). Faktum är att eftersom $K>n$ har man

${\Big (}{\frac {K+j}{K}}{\Big )}^{n}\leq {\Big (}{\frac {K+j}{K}}{\ Big )}^{K}={\Big (}1+{\frac {j}{K}}{\Big )}^{K}\leq {\Big (}1+{\frac {j}{ 1}}{\Big )}{\Big (}1+{\frac {j}{2}}{\Big )}\dots {\Big (}1+{\frac {j}{K}}{ \Big )}={\frac {1+j}{1}}{\frac {2+j}{2}}\dots {\frac {K+j}{K}}={\frac {(K +j)!}{K!j!}}.$

Därför ${\frac {(K+j)^{n}}{(K+j)!}}\leq {\frac {K^{n}}{K!}}{\frac {1}{ j!}}\leq {\frac {1}{j!}}$ för alla $j\geq 0$ så att svansen $\sum _{k\geq K}{\frac {k^{n}}{k!}}=\sum _{j\geq 0}{\frac {(K+j)^{n} }{(K+j)!}}$ domineras av serien ${\displaystyle \sum _{j\geq 0}{\frac {1}{j!}}=e} ,$ vilket innebär $0<B_{n}-{\frac {1}{e}}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!} }<1$ , varifrån den reducerade formeln.

Generalisering

Dobińskis formel kan ses som ett speciellt fall, för ${\displaystyle x=0} ,$ av den mer allmänna relationen:

${1 \over e}\sum _{k=x}^{\infty }{\frac {k^{n}}{(kx)!}}=\summa _{k=0}^{ n}{\binom {n}{k}}B_{k}x^{nk}.$

Bevis

Ett bevis förlitar sig på en formel för genereringsfunktionen för klocknummer ,

$e^{e^{x}-1}=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}.$

Potensserien för exponentialen ger

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

så

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

Koefficienten för $x^{n}$ i denna potensserie måste vara $B_{n}/n!$ , alltså

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

En annan typ av bevis gavs av Rota . Kom ihåg att om x och n är icke-negativa heltal så är antalet en-till-en-funktioner som mappar en storlek- n -mängd till en storlek- x -mängd den fallande faktorialen

$(x)_{n}=x(x-1)(x-2)\cdots (x) -n+1)$

Låt ƒ vara vilken funktion som helst från en storlek- n -mängd A till en storlek- x - mängd B. För vilken b ∈ B som helst , låt ƒ ⁻¹ ( b ) = { a ∈ A : ƒ ( a ) = b }. Då är { ƒ ⁻¹ ( b ): b∈B av } en partition A. Rota kallar denna partition för " kärnan " för funktionen ƒ . Vilken funktion som helst från A till B påverkar

• en funktion som mappar en medlem av A till elementet i kärnan som den tillhör, och
• en annan funktion, som nödvändigtvis är en-till-en, som mappar kärnan till B .

Den första av dessa två faktorer bestäms helt av partitionen π som är kärnan. Antalet en-till-en-funktioner från π till B är ( x ) _{| π |} , där | π | är antalet delar i partitionen π . Sålunda är det totala antalet funktioner från en storlek- n uppsättning A till en storlek- x uppsättning B

$\sum _{\pi}(x)_{|\pi |},$

indexet π som löper genom uppsättningen av alla partitioner av A . Å andra sidan är antalet funktioner från A till B tydligt x ⁿ . Därför har vi

$x^{n}=\summa _{\pi}(x)_{|\pi |}.$

Rota fortsätter beviset med linjär algebra, men det är upplysande att introducera en Poisson-fördelad stokastisk variabel X med medelvärde 1. Ekvationen ovan antyder att det n: te momentet av denna stokastiska variabel är

$E(X^{n})=\summa _{\pi }E((X)_{|\pi |})$

där E står för förväntat värde . Men vi ska visa att alla kvantiteterna E (( X ) _k ) är lika med 1. Det följer att

$E(X^{n})=\summa _{\pi }1,$

och detta är bara antalet partitioner i uppsättningen A .

Storheten E (( X ) _k ) kallas det k: te faktormomentet för stokastisk variabel X . För att visa att detta är lika med 1 för alla k när X är en Poisson-fördelad slumpvariabel med medelvärde 1, kom ihåg att denna slumpvariabel antar varje värde heltalsvärde $j\geq 0$ med sannolikhet $1/(ej!)$ . Således

$E((X)_{k})=\sum _{j=0}^{\infty }{\frac {(j)_{k}}{ej!}}={\ frac {1}{e}}\summa _{j=0}^{\infty }{\frac {j(j-1)\cdots (j-k+1)}{j(j-1)\cdots 1}}={\frac {1}{e}}\sum _{j=i}^{\infty }{\frac {1}{(ji)!}}=1.$