# hw10JikeLiu.txt
# Math 640 — Homework 10
# Jike Liu
#

read "C10.txt":

# ------------------------------------------------------------
# 1) CompsMod(n,a,S)
# ------------------------------------------------------------

# CompsMod(n,a,S): compositions of n whose parts x satisfy (x mod a) in S.
CompsMod := proc(n,a,S) local A,i;
  A := {}:
  for i from 1 to n do
    if member(i mod a, S) then
      A := A union {i}:
    fi:
  od:
  CompsG(n, A):
end:

# [seq( nops(CompsMod(n,2,{1})), n=1..10)];
# [seq( nops(CompsMod(n,3,{1})), n=1..10)];
# [seq( nops(CompsMod(n,5,{1,4})), n=1..10)];

# outputs:
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
# [1, 1, 1, 2, 3, 4, 6, 9, 13, 19]
# [1, 1, 1, 2, 3, 5, 7, 10, 15, 23]


# ------------------------------------------------------------
# 2) OddParStupid(n)
# ------------------------------------------------------------

# OddParStupid(n): partitions of n (from Par(n)) with only odd parts.
OddParStupid := proc(n) local P, p;
  P := Par(n):
  { seq(p, p in P
          if andmap(x -> (x mod 2 = 1), p) ) }:
end:


# ------------------------------------------------------------
# 3) DistinctParStupid(n)
# ------------------------------------------------------------

# DistinctParStupid(n): partitions of n with distinct parts.
DistinctParStupid := proc(n) local P, p;
  P := Par(n):
  { seq(p, p in P
          if nops(convert(p,set)) = nops(p) ) }:
end:


# ------------------------------------------------------------
# 4) Verify for n<=15: nops(DistinctParStupid(n)) = nops(OddParStupid(n))
# ------------------------------------------------------------

for n from 1 to 15 do
  print(n, evalb( nops(DistinctParStupid(n)) = nops(OddParStupid(n)) )):
od:

# output: (n,true) for n=1..15.


# ------------------------------------------------------------
# 5) odd parts partitions = distinct parts partitions
# ------------------------------------------------------------

# Let o(n) be the number of partitions of n into odd parts,
# and let d(n) be the number of partitions of n into distinct parts.
# We prove o(n)=d(n) for all n by showing their generating functions are equal.

# Odd parts:
# In a partition into odd parts, each odd integer (2m-1) may appear 0,1,2,... times.
# Therefore the generating function is
#
#   Sum_{n>=0} o(n) x^n
#     = Product_{m>=1} (1 + x^{2m-1} + x^{2(2m-1)} + ...)
#     = Product_{m>=1} 1/(1 - x^{2m-1}).

# Distinct parts:
# In a partition into distinct parts, each integer m may appear either 0 or 1 time.
# Therefore the generating function is
#
#   Sum_{n>=0} d(n) x^n
#     = Product_{m>=1} (1 + x^m).

# Key identity:
# We use 1 - x^{2m} = (1 - x^m)(1 + x^m), hence
#
#   1 + x^m = (1 - x^{2m})/(1 - x^m).
#
# Multiplying over m>=1 gives
#
#   Product_{m>=1} (1 + x^m)
#     = Product_{m>=1} (1 - x^{2m})/(1 - x^m)
#     = (Product_{m>=1} (1 - x^{2m})) / (Product_{m>=1} (1 - x^m)).

# Now split the denominator into even and odd factors:
#
#   Product_{m>=1} (1 - x^m)
#     = (Product_{m>=1} (1 - x^{2m})) * (Product_{m>=1} (1 - x^{2m-1})) .
#
# Substitute this into the previous expression:
#
#   Product_{m>=1} (1 + x^m)
#     = (Product_{m>=1} (1 - x^{2m}))
#       / ( (Product_{m>=1} (1 - x^{2m})) * (Product_{m>=1} (1 - x^{2m-1})) )
#     = 1 / (Product_{m>=1} (1 - x^{2m-1})) .

# But 1 / (Product_{m>=1} (1 - x^{2m-1})) is exactly the generating function
# for partitions into odd parts. Hence
#
#   Sum_{n>=0} d(n) x^n = Sum_{n>=0} o(n) x^n,
#
# so the coefficients are equal for every n:
#
#   d(n) = o(n)  for all n.

# ------------------------------------------------------------
# 6) Bijection: compositions of n  <-> 0-1 vectors length n starting with 1
# ------------------------------------------------------------

# A composition C=[c1,...,ck] of n corresponds to a 0-1 vector v of length n
# where v[j]=1 exactly at the start positions of each part:
#   v[1]=1, v[1+c1]=1, v[1+c1+c2]=1, ..., v[1+c1+...+c_{k-1}]=1.
# This gives all 0-1 vectors of length n that start with 1. (Count = 2^(n-1).)

# CompTo01(C): composition -> 0-1 vector
CompTo01 := proc(C) local n, v, s, i;
  n := add(C[i], i=1..nops(C)):
  v := [0$n]:
  v[1] := 1:
  s := 1:
  for i from 1 to nops(C)-1 do
    s := s + C[i]:
    v[s] := 1:
  od:
  v:
end:

# VecToComp(v): 0-1 vector starting with 1 -> composition
VecToComp := proc(v) local n, ones, j;
  n := nops(v):
  if n=0 or v[1] <> 1 then error "vector must start with 1" fi:
  ones := [seq(j, j=1..n if v[j]=1)]:
  [ seq(ones[j+1]-ones[j], j=1..nops(ones)-1), n+1-ones[-1] ]:
end:




# ------------------------------------------------------------
# 7) Bijection: odd-part compositions of n  <-> {1,2}-compositions starting with 1
# ------------------------------------------------------------

# Map:
# For an odd part a=2r+1, map it to the block [1, 2$ r], which sums to 1+2r=a.
# Concatenating blocks gives a {1,2}-composition that starts with 1.
#
# Inverse: given a {1,2}-composition starting with 1, split into blocks at each 1:
#   [1,2^r1, 1,2^r2, ..., 1,2^rk]
# and map each block back to odd part 2ri+1.

# OddCompTo12(C): odd-part composition -> {1,2}-composition starting with 1
OddCompTo12 := proc(C) local out, i, r;
  out := []:
  for i from 1 to nops(C) do
    r := (C[i]-1)/2:
    out := [op(out), 1, 2$r]:
  od:
  out:
end:

# Comp12Start1ToOdd(W): {1,2}-composition starting with 1 -> odd-part composition
Comp12Start1ToOdd := proc(W) local out, i, r, n;
  n := nops(W):
  if n=0 or W[1] <> 1 then error "input must start with 1" fi:

  out := []:
  r := 0:
  for i from 2 to n+1 do
    if i=n+1 or W[i]=1 then
      out := [op(out), 2*r+1]:
      r := 0:
    elif W[i]=2 then
      r := r+1:
    fi:
  od:
  out:
end:

# End