# hw8JikeLiu.txt
# Jike Liu


Read C8.txt:

with(numtheory):
with(combinat):




# ------------------------------------------------------------
# Q1. test for k=2: show p<43 gives 0, but p=43 gives nonzero
# Compute: (xnP(p-1,p)+p-1)*xnP(p-1,p) mod p
# ------------------------------------------------------------

# Run this to print all primes <43:
Q1 := proc() local p, val, r;
  for p in primelist(42) do
    r := xnP(p-1, p):
    val := ((r + p-1) * r) mod p:
    print(p, r, val):
  od:
  # p = 43
  p := 43:
  r := xnP(p-1, p):
  val := ((r + p-1) * r) mod p:
  print(p, r, val):
end:

# My output:
# 2,  0, 0
# 3,  0, 0
# 5,  0, 0
# 7,  0, 0
# 11, 0, 0
# 13, 0, 0
# 17, 1, 0
# 19, 1, 0
# 23, 1, 0
# 29, 0, 0
# 31, 0, 0
# 37, 1, 0
# 41, 1, 0
# 43, 33, 24
#
# Conclusion: since for p=43 the value is nonzero mod 43, x_43 is NOT an integer.


# ------------------------------------------------------------
# Q2. Verify for all permutations pi of size <= 7:
# nops(LtoR(Foata(pi))) = nops(CycDec(pi))
# ------------------------------------------------------------

Q2 := proc()
  local n, pi, OK;
  for n from 1 to 7 do
    OK := true:
    for pi in permute(n) do
      if nops(LtoR(Foata(pi))) <> nops(CycDec(pi)) then
        OK := false: break:
      fi:
    od:
    print(n, OK):
  od:
end:

# Expected: prints (n, true) for n=1..7.


# ------------------------------------------------------------
# Q3. Why Foata implies: #perms with k cycles = #perms with k LtoR maxima
# ------------------------------------------------------------

# Foata is a bijection Phi: S_n -> S_n with the property:
#   (# cycles of pi) = (# left-to-right maxima of Foata(pi)).
# Therefore, restricting Phi to permutations with exactly k cycles gives a bijection
# onto permutations with exactly k left-to-right maxima. Hence the two sets have
# the same size for all n,k (k<=n).


# ------------------------------------------------------------
# Q4. AntiFoata: inverse map of Foata, and verify inverses for n<=7
# ------------------------------------------------------------

# AntiFoata(w): inverse of Foata. In Foata(pi), each cycle begins with its maximum,
AntiFoata := proc(w)
  local n, S, j, s, e, C;
  n := nops(w):
  S := LtoR(w):
  C := []:
  for j from 1 to nops(S) do
    s := S[j]:
    if j < nops(S) then
      e := S[j+1]-1:
    else
      e := n:
    fi:
    C := [op(C), [op(s..e, w)]]:
  od:
  CycToPer(C):
end:

# Verification for n<=7:
Q4 := proc()
  local n, pi, OK;
  for n from 1 to 7 do
    OK := true:
    for pi in permute(n) do
      if AntiFoata(Foata(pi)) <> pi or Foata(AntiFoata(pi)) <> pi then
        OK := false: break:
      fi:
    od:
    print(n, OK):
  od:
end:




# ------------------------------------------------------------
# Q5. Generalization x_{n,k}: 
# xnk(n,k) = (1 + xnk(0,k)^k + ... + xnk(n-1,k)^k)/n
# Note: xnk(n,2) = xn(n)
# ------------------------------------------------------------

# Direct definition (slow)
xnk := proc(n,k) local i;
option remember;
  if n=0 then
    RETURN(1):
  fi:
  (1 + add(xnk(i,k)^k, i=0..n-1))/n:
end:

# Clever recurrence (fast):
# x_{0,k}=1, x_{1,k}=2, and for n>=2:
# x_{n,k} = x_{n-1,k} * ( (n-1) + x_{n-1,k}^{k-1} ) / n
xnkC := proc(n,k) local x;
option remember;
  if n=0 then
    RETURN(1):
  elif n=1 then
    RETURN(2):
  fi:
  x := xnkC(n-1,k):
  simplify( x * ((n-1) + x^(k-1)) / n ):
end:

# Mod version for prime p (valid for n<p)
xnkP := proc(n,k,p) local x;
option remember;
  if n=0 then
    RETURN(1 mod p):
  elif n=1 then
    RETURN(2 mod p):
  fi:
  x := xnkP(n-1,k,p):
  ( x * ((n-1 + PowerMod(x,k-1,p)) mod p) * invmod(n,p) ) mod p:
end:




# End of hw8JikeLiu.txt