#Homework by Mike Murr
#OK to post
#hw10
#
with(combinat);
permute(4);

#invList(n) For each permutation of {1,…,n}, invList(n) returns the number of inversions.
# The result is a list of length n factorial.

invList := proc(n) local S,i,permi,j,k, inv;

S:=permute(n);

for i from 1 to nops(S) do
  permi:=S[i]; #one permutation
  inv[i]:=0;
  for j from 1 to n-1 do
    for k from j to n do
      if permi[j] > permi[k] then
        inv[i]:=inv[i] + 1;
      fi;
    od;
  od;
od;

#print(convert(inv,list));
return(convert(inv,list));

end proc;

permute(3);
invList(3);

permute(4);
invList(4);

invList(5);

#freqDist(n,L) Given a number n and a list containing values from 0 to n*(n-1)/2 (with duplicates),
# returns the frequency distribution.

freqDist:=proc(n,L) local j, i, value, totals;

for j from 0 to n*(n-1)/2 do
  totals[j]:=0;
od;

for i from 1 to nops(L) do
  value:=L[i];
  totals[value] :=totals[value]+1;
od;
return(convert(totals,list));
end proc;

freqDist(3,invList(3));

freqDist(4,invList(4));

freqDist(5,invList(5));

freqDist(6,invList(6));


#ExactGFinv(n,x) Inputs a positive integer n and a variable name x, and outputs the generating
# function whose coefficient of x^k is the exact number of permutations with inv=k

ExactGFinv:=proc(n,x) local totals,maxInversions,i, value, resultSum;

totals:=freqDist(n, invList(n));
print(totals);

maxInversions:= nops(totals) - 1;
print(maxInversions);
resultSum:=0;

for i from 0 to maxInversions do
  value:=totals[i+1];
  resultSum:=resultSum + value*x^i;
od;

end proc;

ExactGFinv(2,x);
ExactGFinv(3,x);
ExactGFinv(4,x);
ExactGFinv(5,x);
ExactGFinv(6,x);
ExactGFinv(7,x);

#desList(n) For each permutation of {1,…,n}, desList(n) returns the number of descents.
# The result is a list of length n factorial.

desList := proc(n) local S,i,permi,j, des;

S:=permute(n);

for i from 1 to nops(S) do
  permi:=S[i]; #one permutation
  des[i]:=0;
  for j from 1 to n-1 do
    
      if permi[j] > permi[j+1] then
        des[i]:=des[i] + 1;
      fi;
    
  od;
od;

#print(convert(des,list));
return(convert(des,list));

end proc;

permute(3);
desList(3);

permute(4);
desList(4);

desList(5);

#freqDistDes(n,L) Given a number n and a list containing values from 0 to n-1 (with duplicates),
# returns the frequency distribution.

freqDistDes:=proc(n,L) local j, i, value, totals;

for j from 0 to n-1 do
  totals[j]:=0;
od;

for i from 1 to nops(L) do
  value:=L[i];
  totals[value] :=totals[value]+1;
od;
return(convert(totals,list));
end proc;

freqDistDes(3,desList(3));

freqDistDes(4,desList(4));

freqDistDes(5,desList(5));

#ExactGFdes(n,x) Inputs a positive integer n and a variable name x, and outputs the generating
# function whose coefficient of x^k is the exact number of permutations with des=k

ExactGFdes:=proc(n,x) local totals,maxDescents,i, value, resultSum;

totals:=freqDistDes(n, desList(n));
print(totals);

maxDescents:= nops(totals) - 1;
print(maxDescents);
resultSum:=0;

for i from 0 to maxDescents do
  value:=totals[i+1];
  resultSum:=resultSum + value*x^i;
od;

end proc;

ExactGFdes(3,x);
ExactGFdes(4,x);
ExactGFdes(5,x);

#majList(n) For each permutation of {1,…,n}, majList(n) returns the sum of the major places.
# For example, maj(631425)=1+2+4=7.
# The result is a list of length n factorial.

majList := proc(n) local S,i,permi,j, maj;

S:=permute(n);

for i from 1 to nops(S) do
  permi:=S[i]; #one permutation
  maj[i]:=0;
  for j from 1 to n-1 do
    
      if permi[j] > permi[j+1] then
        maj[i]:=maj[i] + j;
      fi;
    
  od;
od;

#print(convert(maj,list));
return(convert(maj,list));

end proc;

permute(3);
majList(3);

permute(4);
majList(4);

majList(5);

#freqDistMaj(n,L) Given a number n and a list containing values from 0 to n*(n-1)/2 (with duplicates),
# returns the frequency distribution.

freqDistMaj:=proc(n,L) local j, i, value, totals;

for j from 0 to n*(n-1)/2 do
  totals[j]:=0;
od;

for i from 1 to nops(L) do
  value:=L[i];
  totals[value] :=totals[value]+1;
od;
return(convert(totals,list));
end proc;

freqDistMaj(3,majList(3));

freqDistMaj(4,majList(4));

freqDistMaj(5,majList(5));

#ExactGFmaj(n,x) Inputs a positive integer n and a variable name x, and outputs the generating
# function whose coefficient of x^k is the exact number of permutations with maj=k

ExactGFmaj:=proc(n,x) local totals,maxMajors,i, value, resultSum;

totals:=freqDistMaj(n, majList(n));
print(totals);

maxMajors:= nops(totals) - 1;
print(maxMajors);
resultSum:=0;

for i from 0 to maxMajors do
  value:=totals[i+1];
  resultSum:=resultSum + value*x^i;
od;

end proc;

ExactGFmaj(3,x);
ExactGFmaj(4,x);
ExactGFmaj(5,x);

ClosedExactGFinv:=proc(n,x) local k,i,accum,oneFactor;

#return(product((1-x^k)/(1-x),k=1..n));

#return(product(sum(x^i,i=0..k),k=1..n));

accum:=1;
for k from 1 to n-1 do
  oneFactor :=0;
  for i from 0 to k do
    oneFactor:=oneFactor+x^i;
  od;
  accum:=accum*oneFactor;
od;
return(expand(accum));
end proc;


ClosedExactGFinv(2,x);

ClosedExactGFinv(3,x);

ClosedExactGFinv(4,x);

ClosedExactGFinv(5,x);

ClosedExactGFinv(6,x);

#The closed form of ExactGFmaj is the same as the closed form of ExactGFinv

ClosedExactGFmaj:=proc(n,x) local k,i,accum,oneFactor;

#return(product((1-x^k)/(1-x),k=1..n));

#return(product(sum(x^i,i=0..k),k=1..n));

accum:=1;
for k from 1 to n-1 do
  oneFactor :=0;
  for i from 0 to k do
    oneFactor:=oneFactor+x^i;
  od;
  accum:=accum*oneFactor;
od;
return(expand(accum));
end proc;


ClosedExactGFmaj(2,x);

ClosedExactGFmaj(3,x);

ClosedExactGFmaj(4,x);

ClosedExactGFmaj(5,x);

ClosedExactGFmaj(6,x);