# OK to post homework
# Robert Dougherty-Bliss
# 2021-03-07
# Assignment 13

# 1.

# Euler's Pentagonal theorem is a statement about inverses.

# Let E(q) be the right-hand side of Euler's Pentagonal theorem. This is the
# ogf of the sequence

#       a(n) = sum((-1)^k [n = k(3k - 1) / 2], k),

# n from -infinity to infinity. (This is something like (-1)^n [n is a
# pentagonal number], but the (-1)^n is more complicated.)

# Let P(q) be the ogf of the partition function p(n).

# Euler's Pentagonal theorem says that

#   1 / P(q) = E(q).

# We're in great luck, because generating function inverses usually imply
# *some* kind of recurrence: E(q) P(q) = 1 is equivalent to a pretty
# convolution identity.

# The coefficient on q^n for n >= 1 in E(q) P(q) = 1 is

#    sum(p(n - k) a(k), 0 <= k <= n) = 0.

# Note that a(0) = 1, so this says

#       p(n) = -sum(p(n - k) a(k), 1 <= k <= n).

# All well and good, but let's expand that a(k):

#       p(n) = -sum(p(n - k) (-1)^j [k = j(3j - 1) / 2], j, 1 <= k <= n)
#            = -sum(p(n - j(3j - 1) / 2) (-1)^j [k = j(3j - 1) / 2], j, 1<= k <= n).

# If we dictate that p(n) = 0 for n < 0, then we can write

#       p(n) = -sum(p(n - j(3j - 1) / 2) (-1)^j, |j| >= 1)

pnE := proc(n)
    option remember:

    if n < 0 then
        return 0:
    fi:

    if n = 0 then
        return 1:
    fi:

    ret := 0:
    j := 1:
    k1 := j * (3 * j - 1) / 2:
    k2 := -j * (3 * (-j) - 1) / 2:

    while k1 <= n or k2 <= n do
        ret := ret - (-1)^j * (pnE(n - k1) + pnE(n - k2)):
        j := j + 1:
        k1 := j * (3 * j - 1) / 2:
        k2 := -j * (3 * (-j) - 1) / 2:
    od:

    ret:
end:

# pnE is much faster than pn.
# pn(1000) takes nearly 15 seconds, but pnE(1000) takes less than half of one.

# 2.

# Fabian Franklin's proof is quite pretty.

#####################
#   BEGIN RAMBLING  #
#####################

# The very high-level idea is this: Pick a set S and assign a weight of +1 to
# some elements and -1 to other elements. If we can construct an involution
# from a subset of the +1's to a subset of the -1's, then when we "sum" these
# elements together, everything in these subsets cancel since we can pair +1's
# with -1's.

# Franklin's idea is to construct an involution from partitions with an even
# parts to partitions with an odd number of parts.

# Take an arbitrary partition of n into distinct parts and look at its Ferrers
# diagram. There is a "diagonal" line that makes a 45 degree angle starting
# from the final largest part and continuing down. Call the length of this line
# s. Call the size of the smallest part m.

# If s < m, then take the dots on the diagonal and move them down to form a new
# smallest part. If s >= m, then we can take the smallest part and move it up
# to make a new diagonal.

# Claim: This almost always changes the parity of the number of parts, and
# almost always keeps the parts distinct.

# The product (1 - q)(1 - q^2) ... weightedly counts numbers of distinct
# partitions. Partitions with even parts are +1, partitions with odd parts are
# -1. Whenever Franklin's idea works on the partitions of n, the sums cancel
# out, and the coefficient on q^n is 0.

# When does Franklin's idea fail?

# If m = s + 1 and diagonal meets the last row (number of parts equals s), then
# moving it down will create duplicate sizes. No beuno.

# If m = s and the diagonal meets the last row (number of parts equals s), then
# the operation doesn't make much sense. Trying to move the last row into a
# diagonal will run out of room at the end.

# Otherwise, we're all good!

# For what n does this happen, and how do the weights work out in those cases?

# If m = s and the diagonal meets the last row, then

#   n = m + (m + 1) + ... + (m + s - 1)
#     = m(3m - 1) / 2.

# The weight of this partition is (-1)^s = (-1)^m. This is also clearly the
# unique partition of n that will cause this problem.

# If m = s + 1 and the diagonal meets the last row, then

#   n = m + (m + 1) + ... (m + s - 1)
#     = (m - 1)(3m - 2) / 2
#     = k(3k - 1),

# where k = 1 - m. The weight here is (-1)^s = (-1)^(m - 1) = (-1)^k.

# Again, this is the unique partition that creates a problem.

# So, when we sum everything up, it all cancels except for these pesky, unique
# problem partitions of pentagonal numbers. Fascinating!

#####################
#   END RAMBLING    #
#####################

franklin := proc(L)
    m := L[-1]:
    s := 1:

    res := L:

    while s < nops(L) and L[s + 1] = L[s] - 1 do
        s := s + 1:
    od:

    if m = s and nops(L) = s then
        return FAIL:
    fi:

    if m = s + 1 and nops(L) = s then
        return FAIL:
    fi:

    if m <= s then
        # Move the bottom row to the first m rows.
        for k from 1 to m do
            res[k] := res[k] + 1:
        od:

        res := res[..-2]:
    else
        # Move the leading diagonal to the bottom row.
        for k from 1 to s do
            res[k] := res[k] - 1:
        od:
        res := [op(res), s]:
    fi:

    res:
end:

# 3.

read "hw12RDB.txt":

FranklinOldMaids := proc(n)
    uniquePartitions := PnD(n, {0}):

    res := []:

    for L in uniquePartitions do
        if franklin(L) = FAIL then
            res := [op(res), L]:
        fi:
    od:

    res:
end:

# The n where this returns a singleton will be the generalized pentagonal
# numbers, i.e., numbers of the form n = k(3k - 1) / 2 for arbitrary k. That's
# straight from Franklin's proof. You can also figure out exactly what those
# partitions will be, which came up in Franklin's proof as well.