#Maple Code for Lecture 11 of Combinatorics , Math 454, taught by Dr. Z. Help11:=proc(): print(` SPk(n,k), SP(n) , Snk(n,k), Bell1(n), Bell2(n), Bell3(n) `): print(`SeqBell0(N),SeqBell1(N),SeqBell2(N),SeqBell3(N)`): end: #SPk(n,k): The set of Set-Partiitions of {1,...,n} into k parts. In other words the set of #sets {S1,S2,..., Sk} such that the Si are pairwise disjoint and their union is {1, ..., n} #For example, SPk(3,2) is { {{1},{2,3}}, {{2},{1,3}}, {{3},{2,3}}} #NOTE THAT THE OUTPUT IS A SET OF SETS OF SETS (since a set-partion is already a set-of-sets so #the set of all set-partiotions satisfying whatever coniditions is the set of sets of sets SPk:=proc(n,k) local SSP,SSP1,i,ssp1: option remember: #THIS IS THE INITIAL CONDITION if n=1 then if k=1 then RETURN({{{1}}}): else RETURN({}): fi: fi: #We now construct all the set-partitions of {1, ...,n} by looking at the "social life" of n #If it is all-alone, then removing {n} is a typical set partition of {1,..,n-1} INTO k-1 subsets #Otherwise n may belong to one of the k members of the set-partition and removing it leads #to a set partition of {1,.., n-1} with k subsets, and going back we can stick n into each of #these #Let's call the final output SSP, we will dynamically enlarge it starting with the emtpy set SSP:={}: #We start with the case that n is in its own component we recursively call this procedure with (n-1,k-1) SSP1:=SPk(n-1,k-1): SSP:={seq( ssp1 union {{n}}, ssp1 in SSP1)}: #This takes care of the first case #We now do the case where removing n does not change the number of components SSP1:=SPk(n-1,k): for ssp1 in SSP1 do #We look at all the members of SPk(n-1,k) for i from 1 to k do SSP:=SSP union {{op(1..i-1,ssp1), ssp1[i] union {n}, op(i+1..k,ssp1)}}: od: od: SSP: end: #SP(n): The set of ALL set-partitions of {1,...,n} regardless of the number of constituents SP:=proc(n) local k:{seq(op(SPk(n,k)),k=1..n)}:end: #Snk(n,k): The Stirling numbers of the second-kind, aka the NUMBER of set-partitions of an n-element set Snk:=proc(n,k) option remember: if n=1 then if k=1 then RETURN(1): else RETURN(0): fi: fi: Snk(n-1,k-1)+k*Snk(n-1,k): end: #Bell1(n): The number of set partitions (i.e. nops(SP(n)) done the FIRST way, adding-up Snk(n,k) from k=1 to k=n Bell1:=proc(n) local k: add(Snk(n,k),k=1..n): end: #Bell2(n): The number of set partitions (i.e. nops(SP(n)) done the SECOND way, using the recurrence proved in the lecture Bell2:=proc(n) local k: option remember: if n=0 then 1: else add(binomial(n-1,k)*Bell2(n-1-k),k=0..n-1): fi: end: #Bell3(n): The number of set partitions (i.e. nops(SP(n)) done the THIRD way, using the EXPONENTIAL GENERATING FUNCTION FOR #The Bell Numbers exp(exp(x)-1) Bell3:=proc(n) local x: n!*coeff(taylor(exp(exp(x)-1),x=0,n+1),x,n): end: #SeqBell0(N): The LIST of the first N terms of the sequence of Bell numbers done the stupid way SeqBell0:=proc(N) local n: [seq(nops(SP(n)),n=1..N)]: end: #SeqBell1(N): The LIST of the first N terms of the sequence of Bell numbers done via Bell1(n) SeqBell1:=proc(N) local n: [seq(Bell1(n),n=1..N)]: end: #SeqBell2(N): The LIST of the first N terms of the sequence of Bell numbers done via Bell2(n) SeqBell2:=proc(N) local n: [seq(Bell2(n),n=1..N)]: end: #SeqBell3(N): The LIST of the first N terms of the sequence of Bell numbers done via the Exponential generatining function SeqBell3:=proc(N) local f,x,i: f:=taylor(exp(exp(x)-1),x=0,N+1): [seq(i!*coeff(f,x,i),i=1..N)]: end: