maxima-worksheet.wxm

/* [wxMaxima batch file version 1] [ DO NOT EDIT BY HAND! ]*/
/* [ Created with wxMaxima version 12.04.0 ] */

/* [wxMaxima: title   start ]
Design and Analysis of Algorithms
   [wxMaxima: title   end   ] */

/* [wxMaxima: section start ]
On quicksort average number of swaps
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
expr:(1/(n*(n-1)))* ((n*(n+1)^2)/2 - n*(n+1)*(2*n+1)/6 -n^2);
ratsimp(expr);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
generalTerm:(2*k-3)/(6*k*(k-1));
pf:partfrac(generalTerm,k);
integrate(pf , k);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
On combinatorics
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
f(z):=sqrt(1+z);
taylor(f(z), z, 0, 6);
mapBinomial(x):=binomial (1/2, x)$
map (mapBinomial, [0, 1, 2, 3, 4, 5, 6]);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
f(z):=1/sqrt(1+z);
taylor(f(z), z, 0, 6);
mapBinomial(x):=binomial (-(1/2), x)$
map (mapBinomial, [0, 1, 2, 3, 4, 5, 6]);
byDef(k):=(((-1)^k)/(4^k))*binomial(2*k,k);
map (byDef, [0, 1, 2, 3, 4, 5, 6]);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
Generating Function Basics
   [wxMaxima: section end   ] */

/* [wxMaxima: subsect start ]
First examples before properties
   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
makelist(naturals(n),n,0, 6);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
load("ggf");
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
ggf(makelist(n,n,0, 6));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
niceindicespref;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
sequence:makelist(n,n,0, 6);
taylor(ggf(sequence), n, 0, 8);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
onlyEvenTerms(n):=if is(mod (n,2)=0) then 1 else 0$
sequence:makelist(onlyEvenTerms(n),n,0, 6);
ggfOnlyEvenTerms:ggf(sequence);
taylor(ggfOnlyEvenTerms, x, 0, 12);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
onlyFirstThreeTerms(n):=if is(n <= 2) then 1 else 0$
sequence:makelist(onlyFirstThreeTerms(n),n,0, 6);
ggfOnlyFirstThreeTerms:ggf(sequence);
taylor(ggfOnlyFirstThreeTerms, x, 0, 100);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: subsect start ]
Convolution of G operator
   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
makeSequence(t,j):=sum (j[i]*t^i, i, 0, inf);
as:taylor(makeSequence(t,a), t, 0, 3);
bs:taylor(makeSequence(t,b), t, 0, 3);
as*bs;
sum ((sum(a[k]*b[n-k],k,0,n))*t^n, n, 0, inf);
taylor(sum((sum(a[k]*b[n-k],k,0,n))*t^n,n,0,inf), t, 0, 3);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: subsect start ]
Translation of G operator
   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
makeSequence(t,j,offset):=if is(offset >= 0) then sum (j[i+offset]*t^i, i, 0, inf) else sum (j[i]*t^(i-offset), i, 0, inf)$
as:taylor(makeSequence(t,a,0), t, 0, 4);
bs:taylor(makeSequence(t,a,1), t, 0, 3);
(as-a[0])/t;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
load("simplify_sum")$
sequence:makeSequence(t,a,0);
translated:makeSequence(t,a,s)$
(sequence - sum(a[i]*t^i,i,0,s-1))/t^s;
(taylor(sequence, t, 0, 55) - sum(a[i]*t^i,i,0,49))/t^50;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
p:5$
cs:taylor(makeSequence(t,a,-p), t, 0, 10);
ds:taylor((t^p)*makeSequence(t,a,0), t, 0, 10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: subsect start ]
Inverse of formal power series
   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
makeSequence(t,j):=sum (j[i]*t^i, i, 0, inf)$
makeSum(n):=sum (a[i]*b[n-i], i, 0, n)$
as:taylor(makeSequence(t,a), t, 0, 4);
bs:taylor(makeSequence(t,b), t, 0, 4);
prod:as*bs;
sol:solve([makeSum(0)=1, makeSum(1)=0, makeSum(2)=0, makeSum(3)=0, makeSum(4)=0],[b[0],b[1],b[2],b[3],b[4]]);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
as:[1,-1,0,0,0];
ev(sol[1],a[0]=as[1],a[1]=as[2],a[2]=as[3],a[3]=as[4],a[4]=as[5]);
b(t):=1/(1-t);
taylor(b(t),t,0,8);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: subsect start ]
Derivation for G operator
   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
makeSum(n):=sum (a[i]*t^i, i, 0, n)$
makeDerSum(n):=sum (i*a[i]*t^i, i, 0, n)$
an(n):=taylor(makeSum(n),t,0,6)$
deran(n):=taylor(makeDerSum(n),t,0,6)$
an(6);
deran(6);
t*diff(an, t);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: subsect start ]
Some examples of properties application
   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
b(t):=1/(1-c*t)$
taylor(b(t),t,0,8);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=1/(1-t)$
fg(t):=t*diff(b(t),t);
fg(t);
taylor(fg(t),t,0,8);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
snder(t):=t*diff(fg(t),t)$
ratsimp(snder(t));
taylor(snder(t),t,0,8);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=1/(1-t)$
taylor(b(t^2),t,0,10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
taylor(b(t^3),t,0,10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=1/(1-2*t)$
taylor(b(t^3),t,0,15);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=log(1/(1-t))$
taylor(b(t),t,0,15);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
harmonic(n) := sum(1/k,k,1,n);
b(t):=log(1/(1-t))*(1/(1-t));
map(harmonic, makelist(n,n,1,10));
taylor(b(t),t,0,10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=t/(1-t-t^2)$
map(fib, makelist(n,n,1,10));
taylor(b(t),t,0,10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
tribonacci(n):=if is(n=0) then 0 else if is(n=1) then 1 else if is(n=2) then 1 else tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3)$
b(t):=(t/(1-t-t^2-t^3));
map(tribonacci, makelist(n,n,0,9));
taylor(b(t),t,0,9);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=p/(1+t);
integrate(b(t),t);
a(t) := (1+t)^p$
curriedBinomial(n):=binomial(p,n)$
map(ratsimp, map(curriedBinomial, makelist(n,n,0,5)));
taylor(a(t),t,0,5);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=2/(1-4*t);
integrate(b(t),t);
a(t) := 1/sqrt(1-4*t)$
curriedBinomial(n):=binomial(2*n,n)$
map(ratsimp, map(curriedBinomial, makelist(n,n,0,5)));
taylor(a(t),t,0,5);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
b(t):=(1-sqrt(1-4*t))/(2*t)$
catalan(n):=binomial(2*n,n)/(n+1)$
map(catalan, makelist(n,n,0,10));
taylor(b(t),t,0,10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: subsect start ]
QS average checks/swaps generating function

   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
c(t):=(2/(1-t)^2)*log(1/(1-t))$
taylor(c(t),t,0,8);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
s(t):=(1/(3*(1-t)^2))*log(1/(1-t)) + (t^3-3*t^2-6*t)/(18*(1-t)^2)$
taylor(s(t),t,0,8);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: subsect start ]
Inverse operator of G
   [wxMaxima: subsect end   ] */

/* [wxMaxima: input   start ] */
eqFib:1-k-k^2=0;
solutions:solve(eqFib,k);
phi:ev(k,solutions[2]);
phiHat:ev(k,solutions[1]);
ratsimp(phi*phiHat);
ratsimp(phi+phiHat);
ratsimp(-phi*phiHat*(1-t/phi)*(1-t/phiHat));
ratsimp((1+phi*t)*(1+phiHat*t));
ABvalues:solve([A+B=0, (A/phiHat)+(B/phi)=-1],[A,B]);
parFracAB(A,B):=(A/(1-t/phi))+(B/(1-t/phiHat));
ratsimp(ev(parFracAB(A,B),ABvalues));
coef(n,A,B):=A*(1/phi)^n + B*(1/phiHat)^n;
coefCurry(n):=ratsimp(ev(coef(n,A,B),ABvalues))$
map(coefCurry, makelist(n,n,0,10));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
Generate binary trees at random
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
fpprintprec:4$
leaves(n):=(n*(n+1))/(2*(2*n-1));
combineResult(n):=[n,leaves(n)]$
map(combineResult, makelist(n,n,1,10)),numer;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
float((%o511) ), numer;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
Symbolic method
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
f(t):=(1-t^4)/(1-2*t+t^5);
taylor(f(t),t,0,10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
dick(t):=(1-sqrt(1-4*t^2))/(2*t^2);
taylor(dick(t),t,0,20);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
solutions:solve([ P(t,z,w)=t*z+t^2*w^2*E(t,z,w), 
        M(t,z,w)=t+t,
        A(t,z,w)=t+t, 
        E(t,z,w)=T(t,z,w)+A(t,z,w)*T(t,z,w), 
        T(t,z,w)=F(t,z,w)+T(t,z,w)*A(t,z,w)*F(t,z,w),
        F(t,z,w)=P(t,z,w)+F(t,z,w)*M(t,z,w)*P(t,z,w)],
    [P(t,z,w),M(t,z,w),A(t,z,w),E(t,z,w),T(t,z,w),F(t,z,w)])$
/*
    I've to understand better because there are two solutions, the result using solutions[1] does not satisfy much
*/
ev(taylor(E(t,z,w),t,0,10),solutions[2]);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
solutions:solve(t*B^2-B+1=0,B);
c:ev(B,solutions[1]);
taylor(t/(1-2*t*c),t,0,10);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
Lagrange inversion
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
a(t):=sum (a[i]*t^i, i, 0, 2);
b(t):=sum (b[i]*t^i, i, 0, 2);
term:ratsimp(a(b(t)));
coeff(term,t,0);
term:ev(term,a[0]=0);
solve([ coeff(term,t,0)=0,
        coeff(term,t,1)=1,
        coeff(term,t,2)=0,
        coeff(term,t,3)=0,
        coeff(term,t,4)=0], 
      [b[0],b[1],b[2],a[1],a[2]]);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
A(n):=n^(n-1)/n!;
map(A, makelist(k,k,1,10));
B(n):=n^n/n!;
map(B, makelist(k,k,1,10));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
length:8$
f(n,t):=(1+t)^(2*n);
tt:taylor(taylor(f(n,t),n,0,length),t,0,length)$
coeffCurry(index):=ev(coeff(tt, t, index), n=index)$
map(coeffCurry, makelist(i,i,0,length));
T(t) := 1/sqrt(1-4*t);
taylor(T(t),t,0,length);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
length:10$
alpha:1$
beta:1$
f(n,t):=(1+alpha*t+beta*t^2)^n;
tt:taylor(taylor(f(n,t),n,0,length),t,0,length)$
coeffCurry(index):=ev(coeff(tt, t, index), n=index)$
map(coeffCurry, makelist(i,i,0,length));
T(t) := 1/sqrt((alpha^2-4*beta)*t^2  -2*alpha*t +1);
taylor(T(t),t,0,length);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
length:8$
f(n,t):=sqrt(1-2*t)/(1-t)^(n+1);
tt:taylor(taylor(f(n,t),n,0,length),t,0,length)$
coeffCurry(index):=ev(coeff(tt, t, index), n=index)$
map(coeffCurry, makelist(i,i,0,length));
T(t) := (1-4*t)^(-(1/4));
taylor(T(t),t,0,length);
/* [wxMaxima: input   end   ] */

/* Maxima can't load/batch files which end with a comment! */
"Created with wxMaxima"$