In: Advanced Math
so bell number of a number of was in which that number can be partitioned. above result is true for N.2
let S(p,k) be the number in which p numbers can be put into k sets.
S(p+1,k)=kS(p,k)+S(p,k-1)
so this is because there are two positibilities for upcoming number first Add as a singleton set (in this the partition of p numbers in k-1 set gives away a new posibility for p+1 numbers into k set).
another it goes into a previously defined set (going into a set give rise to S(n,k) posibilities, as there are k sets so kS(p,k) poibilities. now B(n)=
now use induction for n=1 B(3)=5 <3!
suppose it is true for p=n
we will prove for p=n+1
B(n+1)=
rewriting above as S(n,n+1)=0 and S(n,-1)=0
as hypothesis B(n)<n! then (n+1)B(n) is atleast n+1 less than (n+1)! so above is true.