# OK To Post
# Math 640 — Homework 6
# Jike Liu

# ------------------------------------------------------------
# 1) CycToPer(CycDec(pi)) = pi for all permutations of length 6
# ------------------------------------------------------------

# Done.


# ------------------------------------------------------------
# 2) Boring games: BoringGames(S,a,b) and NuBoringGames(S,a,b)
# ------------------------------------------------------------


BoringGames := proc(S,a,b) local G,s,G1,g1;
option remember:

# invalid scores
if a < 0 or b < 0 then
  RETURN({}):
fi:

# boring condition
if a < b then
  RETURN({}):
fi:

# base case
if a = 0 and b = 0 then
  RETURN({[[0,0]]}):
fi:

G := {}:

for s in S do
  # last event: Team I scored s
  G1 := BoringGames(S,a-s,b):
  G  := G union {seq([op(g1),[a,b]], g1 in G1)}:

  # last event: Team II scored s
  G1 := BoringGames(S,a,b-s):
  G  := G union {seq([op(g1),[a,b]], g1 in G1)}:
od:

RETURN(G):
end:

NuBoringGames := proc(S,a,b) local s;
option remember:

if a < 0 or b < 0 then
  RETURN(0):
fi:

if a < b then
  RETURN(0):
fi:

if a = 0 and b = 0 then
  RETURN(1):
fi:

RETURN(
  add(NuBoringGames(S,a-s,b), s in S)
+ add(NuBoringGames(S,a,b-s), s in S)
):
end:



# ------------------------------------------------------------
# 3) OEIS checks for the sequences (i=1..20)
# ------------------------------------------------------------

# Output sequences I obtained:

# Soccer (S={1}):
# [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,
#  208012, 742900, 2674440, 9694845, 35357670, 129644790,
#  477638700, 1767263190, 6564120420]

# Old-Time Basketball (S={1,2}):
# [1, 5, 22, 117, 654, 3843, 23323, 145172,
#  921508, 5942737, 38825546, 256431172, 1709356836, 11485249995,
#  77703736926, 528893901963, 3619228605738, 24884558358426,
#  171828674445330, 1191050708958096]

# Today's Basketball (S={1,2,3}):
# [1, 5, 29, 170, 1093, 7346, 50957, 362476,
#  2629150, 19371533, 144585146, 1090886362, 8306621114,
#  63752890716, 492671044866, 3830272606911, 29937476853483,
#  235104315621495, 1854181694878573, 14679397763545597]

# American football (S={3,6,7,8}):
# [0, 0, 1, 0, 0, 5, 1, 1, 22, 7, 7, 117, 71, 91, 737,
#  658, 908, 4990, 5931, 9108]


# OEIS A-numbers:

# - Soccer:  OEIS A000108 
# - Old-Time Basketball: OEIS A122951
# - Today's Basketball: OEIS A175883
# - American football: I did not find a matching OEIS entry from the initial terms above.


# ------------------------------------------------------------
# 4) Foata bijection Phi
# ------------------------------------------------------------

# Phi(pi): Foata bijection:
#  (i)  take cycle decomposition CycDec(pi)
#  (ii) put each cycle in canonical form using CFC
#  (iii) sort cycles by increasing first element (which is the maximum after CFC)
#  (iv) remove interior brackets (concatenate cycles)

Phi := proc(pi) local Cset, Clist, Can, Sorted;

  # cycle decomposition is a set of cycles
  Cset := CycDec(pi):

  # convert set -> list for indexing
  Clist := convert(Cset, list):

  # canonical form for each cycle
  Can := [seq( CFC(Clist[i]), i=1..nops(Clist) )]:

  # sort cycles by increasing first entry
  Sorted := sort(Can, (x,y) -> x[1] < y[1]):

  # remove interior brackets
  [op(op(Sorted))]:

end:

# End of file.