Bell Number

Author

Eric W. Weisstein
January 14, 2011

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/BellNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/BellNumber.html.

©2010 Wolfram Research, Inc. except for portions noted otherwise

Lists

From Robert Dickau
http://mathforum.org/advanced/robertd/bell.html

BellList[1] = {{{1}}}; (* the basic case *)

BellList[n_Integer?Positive] :=
BellList[n] = Flatten[
      Join[
        Map[ReplaceList[#,{S__}->{S,{n}}]&, BellList[n-1]],
        Map[ReplaceList[#,{b___,{S__},a___}->{b,{S,n},a}]&, BellList[n-1]]],
      1]

BellList[3]//ColumnForm

SetPartitions[3]//ColumnForm

Enumeration

v5.1

b=BellB/@Range[1000];//Timing

Take[b,10]

v6

b=BellB/@Range[1000];//Timing

BellB[Range[10]]

Prime

p=Position[b,_?PrimeQ]//Flatten

b[[p]]

PrimeQ[BellB[2841]]//Timing

BellB[2841];//Timing

Digits[BellB[2841]]

Digits

v6

Table[Digits[BellB[10^n]],{n,0,4}]//Timing

Table[Digits[BellB[10^n]],{n,0,5}]//Timing

...crashes/runs out of memory?...

Recurrence

b[0]:=1
b[n_]:=b[n]=Total[Table[b[k]Binomial[n-1,k],{k,0,n-1}]]

b/@Range[0,10]

Congruences

Touchard

(BellB[p]) mod p==2

b=BellB[Range[5000]];//Timing

Flatten[Position[MapIndexed[Mod[#1,#2[[1]]]&,b],2]]==Prime[Range[2,PrimePi[5000]]]

FunctionExpand[Mod[BellB[p],p],p∈Primes&&p>1]

Table[Mod[BellB[p],p]/.p->Prime[n],{n,20}]

Period

Table[Period[Mod[b,n]],{n,20}]

((#^#-1)/(#-1))&/@Prime[Range[5]]

Do[Print[{m,Period[#],#}&[Mod[b,m]]],{m,15}]

Bell Triangle

b[1,1]:=1
b[n_,1]:=b[n-1,n-1]
b[n_,k_]:=b[n-1,k-1]+b[n,k-1]

Table[b[n,k],{n,5},{k,n}]//ColumnForm

Derivative and Integrals

Table[BellB[n],{n,10}]

Derivative

D[BellB[x],x]

FunctionExpand[BellB[x]]

Integral

Integrate[BellB[x],x]

((2 n!)/(π e))Im((∫_0^π)exp(exp(exp(i θ))) sin(n θ)dθ)==(BellB[n])

Table[((2n!)/(π E))Im[NIntegrate[Exp[Exp[Exp[I θ]]]Sin[n θ],{θ,0,π}]],{n,10}]

Simplify[Im[Exp[Exp[Exp[I θ]]]],θ>0]

Table[((2n!)/(π E))NIntegrate[Im[Exp[Exp[Exp[I θ]]]Sin[n θ]],{θ,0,π}],{n,10}]//Chop

v5.2

Table[((2n!)/(π E))Im[Integrate[Exp[Exp[Exp[I θ]]]Sin[n θ],{θ,0,π}]],{n,2}]

v6

Table[((2n!)/(π E))Im[Integrate[Exp[Exp[Exp[I θ]]]Sin[n θ],{θ,0,π}]],{n,2}]//Timing

V7

Table[((2n!)/(π E))Im[Integrate[Exp[Exp[Exp[I θ]]]Sin[n θ],{θ,0,π}]],{n,2}]//Timing

Generating Function

GF

GeneratingFunction[BellB[n],n,x]

(1/E)Sum[(1/((1-k x)k!)),{k,0,∞}]

FullSimplify[Series[(((((-1))^(1/x)) (x Gamma[((-1+x)/x)]+Gamma[-(1/x),-1]))/(E x)),{x,0,7},Assumptions->x>0],x>0]

Normal[%]

Hypergeometric1F1[-1/x,(x-1)/x,1]/E

Product[1-l x,{l,k}]

Sum[((x^k)/((((-x))^k) Pochhammer[((-1+x)/x),k])),{k,0,∞}]

Sum[BellB[n](x^n),{n,0,∞}]//InputForm

Sum[BellB[n](x^n),{n,0,10}]

Series[(((((-1))^(1/x)) (x Gamma[((-1+x)/x)]+Gamma[-(1/x),-1]))/(E x)),{x,0,10},Assumptions->x>0]//Normal//Simplify

SeriesCoefficient[(((((-1))^(1/x)) (x Gamma[((-1+x)/x)]+Gamma[-(1/x),-1]))/(E x)),{x,0,n}]

EGF

V5

<<DiscreteMath`RSolve`

SeriesTerm[Exp[Exp[x]-1],{x,0,n}]

V7

ExponentialGeneratingFunction[BellB[n],n,x]

SeriesCoefficient[(E^(-1+(E^x))),{x,0,n}]

Sum[BellB[n]((x^n)/(n!)),{n,0,∞}]

Series[Exp[Exp[x]-1],{x,0,10}]

Table[BellB[n]/n! x^n,{n,0,10}]

Sums

BellB[Range[10]]

(∑_k^n)(StirlingS2[n, k])==(BellB[n])

V7

Sum[StirlingS2[n,k],{k,0,n}]

Sum[StirlingS2[n,k],{k,n}]

V8

Sum[StirlingS2[n,k],{k,0,n}]

Sum[StirlingS2[n,k],{k,n}]

(∑_(k=0)^(n-1))(BellB[k]) (Binomial[n-1, k])==(BellB[n])

Sum[BellB[k]Binomial[n-1,k],{k,0,n-1}]//InputForm

Table[Sum[BellB[k]Binomial[n-1,k],{k,0,n-1}],{n,5}]

BellB[Range[5]]

⌈(1/E)(∑_m^(2 n))((m^n)/(m!))⌉==(BellB[n])

Comtet

(1/E)Sum[((m^n)/(m!)),{m,2n}]

Ceiling[Table[(1/E)Sum[((m^n)/(m!)),{m,2n}],{n,0,10}]]

(1/e)(∑_(k=0)^∞)((k^n)/(k!))==(BellB[n])

Dobinski Formula

V7

(1/E)Sum[((k^n)/(k!)),{k,0,∞}]

(∑_m^n)((m^n)/(m!)) (∑_(s=0)^(n-m))((((-1))^s)/(s!))==(BellB[n])

DobinskiPitman[n_]:=Sum[m^n/m! Sum[(-1)^s/s!,{s,0,n-m}],{m,n}]

Table[DobinskiPitman[n],{n,10}]

V7

Sum[m^n/m! Sum[(-1)^s/s!,{s,0,n-m}],{m,n}]

(∑_m^n)(((m^n) Γ(-m+n+1,-1))/(e m! Γ(-m+n+1)))==(BellB[n])

Sum[m^n/m! Sum[(-1)^s/s!,{s,0,n-m}],{m,n}]

(∑_m^n)(((m^n) !n-m)/(Γ(m+1) Γ(-m+n+1)))==(BellB[n])

FullSimplify[(∑_m^n)(((m^n) Gamma[1-m+n,-1])/(E m! Gamma[1-m+n]))]

InputForm[%]

Table[%,{n,0,5}]//FullSimplify

BellB[Range[5]]

(∑_(n=0)^∞)((BellB[n+1])/(n!))==(e^e)

V8

Sum[BellB[n+1]/n!,{n,0,Infinity}]//Timing

TimeConstrained[NSum[BellB[n+1]/n!,{n,0,Infinity}],60]//Timing

Sum[BellB[n+1]/n!,{n,0,100}]//N

E^E//N

Double Sums

(∑_k^n)(∑_i^k)(((((-1))^(k-i)) (i^n))/(k!)) (Binomial[k, i])==(BellB[n])

Sum[(1/(k!))(((-1))^(k-i))Binomial[k,i](i^n),{k,n},{i,k}]

Table[Sum[(1/(k!))(((-1))^(k-i))Binomial[k,i](i^n),{k,n},{i,k}],{n,5}]

Asymptotics

Series[BellB[n],{n,0,2}]

Series[BellB[n],{n,∞,5}]

(Subscript[B, n])∼(((e^((n/(W(n)))-n-1)) ((((n/(W(n)))))^(n+(1/2))))/(Sqrt[n]))

Solve[λ Log[λ]==n,λ]

expr=Simplify[With[{λ=n/ProductLog[n]},(n^(-1/2))(λ^(n+1/2))Exp[λ-n-1]]]

N[expr/.n->1000,10]

BellB[1000]//N

(Subscript[B, n])∼(((e^(-((W(n))/2)+(e^(W(n)))-1)) n! ((W(n))^(-n-1)))/(Sqrt[2 π]))

Solve[r Exp[r]==n,r]

expr=Simplify[With[{r=ProductLog[n]},n!*(2 Pi r^2 Exp[r])^(-1/2) Exp[Exp[r]-1] / r^n
],n>0]/.Abs[ProductLog[n]]:>ProductLog[n]

N[expr/.n->1000,10]

BellB[1000]//N

Identities

((HypergeometricPFQ(ConstantArray[2,n-1],ConstantArray[1,n-1],1))/e)==(BellB[n])

Table[HypergeometricPFQ[ConstantArray[2,n-1],ConstantArray[1,n-1],1]/E,{n,10}]

Lenard's Identity

Table[Partition[Table[(Subscript[B, k]),{k,0,2n}],n+1,1],{n,0,4}]//TraditionalForm

Lenard[n_]:=Partition[Table[Bell[k],{k,0,2n}],n+1,1]

Lenard[5]

Table[{Det[Lenard[n]],Product[i!,{i,n}]},{n,6}]

Product[i!,{i,n}]

Det[With[{n=2},Partition[Table[BellB[k],{k,0,2n}],n+1,1]]]

Stirling Transform

StirlingTransform[Table[1,{10}]]

InverseStirlingTransform[%]