#HomeWork#8
#Please do not post homework
#Abrar Almahmeed, Feb.22

#Question 1: 

for p from 2 to 43 do
  if isprime(p) then
 print(p,((xnP(p-1,p)+p-1)*xnP(p-1,p)) mod p):
fi:
od:
                              2, 0

                              3, 0

                              5, 0

                              7, 0

                             11, 0

                             13, 0

                             17, 0

                             19, 0

                             23, 0

                             29, 0

                             31, 0

                             37, 0

                             41, 0

                             43, 24

#This shows that this congruence holds for all primes p<43, but fails for p=43. 


#Question 2: 

with(combinat):

ok := true:

for i from 1 to 7 do
for pi in permute(i) do
if nops(LtoR(Foata(pi))) <> nops(CycDec(pi)) then
print("Failed at", pi);
ok := false:
break;
fi;
od;
if not ok then
break;
fi;
od;

if ok then
print("Verified for all permutations of size ≤ 7");
fi;


          "Verified for all permutations of size ￢ﾉﾤ 7"


#Question 3: Convince yourself that the Foata bijection implies that for all integers n and k ≤ n, the number of permutations with k cycles equals the number of permutations with k Left-To-Right maxima:

Foata's map is a bijection (i.e. a one to one and onto) on Sn, the set of all permutations on [n]. 
Foata's bijection maps permutations with k cycles and permutations with k left-to-right maxima.
Therefore, for all integers n and k ≤ n, the number of permutations with k cycles equals the number of permutations with k Left-To-Right maxima.

#Question 4:

AntiFoata := proc(pi)

local s;

    for s in permute(nops(pi)) do

        if Foata(s) = pi then

            return s;
        fi;
    od;

end proc:

#To check:
CheckAntiFoata := proc(n)
local pi:
    for pi in permute(n) do
        if Foata(AntiFoata(pi)) <> pi then
            return false:
        fi:
    od:
    true:
end:

seq(CheckAntiFoata(n),n=1..6);
               true, true, true, true, true, true

#Note: for n=7 maple took long time without any result.


#Question 5: 

xnk:=proc(n,k) local i: option remember:
if n=0 then
 1:
 else
 (1+add(xnk(i,k)^k,i=0..n-1))/n:
fi:
end:

seq(xnk(n,2),n=0..6);
                    1, 2, 3, 5, 10, 28, 154

seq(xn(n),n=0..6);
                    1, 2, 3, 5, 10, 28, 154


xnkC:=proc(n) option remember:
if n=1 then
2:
else (xnkC(n-1)+n-1)*xnkC(n-1)/n:
fi:
end:

xnkP:=proc(n,k,p) option remember:
if n=1 then
2:
else
(xnkP(n-1,k,p)+n-1)*xnkP(n-1,k,p)*n^(-1) mod p:
fi:
end: