#C3.txt Jan. 31, 2019
Help:=proc(): print(` MFtoGF(M,t), GFtoMF(f,t)  , PQs(n,t) , Moms(f,t,K) , MomsAM(f,t,K)`): end:


##From C2.txt
#PQs(n,t):the prob. generating function of the running time of Quicksort
 PQs:=proc(n,t) local k:
   option remember:
  if n=0 or n=1 then
   RETURN(1):
  else:

  RETURN(expand(t^(n-1)*add(1/n*PQs(k-1,t)*PQs(n-k,t),k=1..n))):
 fi:

 end:

###end from C2.txt

#MFtoGF(M, t): inputs a prob. mass function of a finite and discrete prob. dist. given
#[  ... [outcome, Pr(outcome)], ...] and a variable name (of type symbol) and outputs
#the prob. gen. function
MFtoGF:=proc(M,t) local i:

add( t^M[i][1]*M[i][2], i=1..nops(M)):
end:

 #GFtoMF(f,t): inputs a  prob. gen. function in the variable t, and outputs the prob. mass function
 #for a finite discrete prob. dist.
 #as a list of pairs [outcome, Pr(outcome)]

GFtoMF:=proc(f,t) local i,M,c:
 if subs(t=1,f)<>1 then
    print(`Not prob. dist.`):
    RETURN(FAIL):
 fi:

  M:=[]:

  for i from ldegree(f,t) to degree(f,t) do
      c:=coeff(f,t,i):
       if c<0 then
          print(`OMG NOT a prob. `):
         RETURN(FAIL):
       elif c>0 then
         M:=[op(M),[i,c]]:
       fi:
od:
M:
end:
      
 #Moms(f,t,K): inputs a prob. gen. function and outputs the first K moments
 Moms:=proc(f,t,K) local L,i,F:
 if subs(t=1,f)<>1 then
    print(`Not prob. dist.`):
    RETURN(FAIL):
 fi:
 
 F:=f:

  L:=[]:

   for i from 1 to K do
    F:=t*diff(F,t):
    L:=[op(L),subs(t=1,F)]:
   od:
   L:

 end:

#MomsAM(f,t,K): inputs a prob. gen. function and outputs the first K moments about the mean
 MomsAM:=proc(f,t,K) local L,i,F,ave:
 if subs(t=1,f)<>1 then
    print(`Not prob. dist.`):
    RETURN(FAIL):
 fi:
 
 F:=f:

  L:=[]:

   F:=t*diff(F,t):
    ave:=subs(t=1,F):

    F:=f/t^ave:

   for i from 1 to K do
    F:=t*diff(F,t):
    L:=[op(L),subs(t=1,F)]:
   od:
   [ave,op(2..nops(L),L)]:

 end: