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

# 1.

# Return the set of all partitions of n with largest part k such that every
# part is congruent to some element of S mod m.
PnkC := proc(n, k, S, m)
    if k > n or not (k mod m in S) then
        return []:
    fi:

    if k = n then
        return [[n]]:
    fi:

    # Now generate the partitions of n - k with largest part <= k.
    ret := []:
    for largest from min(n - k, k) by -1 to 1 do
        parts := PnkC(n - k, largest, S, m):
        ret := [op(ret), seq([k, op(part)], part in parts)]:
    od:

    ret:
end:

# Return the set of all partitions of n such that every part is congruent to
# some element of S mod m.
PnC := proc(n, S, m)
    [seq(op(PnkC(n, k, S, m)), k=1..n)]:
end:

# Return the number of all partitions of n with largest part k such that every
# part is congruent to some element of S mod n.
pnkC := proc(n, k, S, m)
    option remember:
    if k > n or not (k mod m in S) then
        return 0:
    fi:

    if k = n then
        return 1:
    fi:

    # Every smaller partition adds 1.
    add(pnkC(n - k, largest, S, m), largest=1..min(n-k, k)):
end:

# Return the number of all partitions of n such that every part is congruent to
# some element of S mod n.
pnC := proc(n, S, m)
    option remember:
    add(pnkC(n, k, S, m), k=1..n):
end:

# 2.

# Return the set of all partitions of n with largest part k such that every
# difference of consecutive parts is NOT in Di.
PnkD := proc(n, k, Di)
    if k > n then
        return []:
    fi:

    if k = n then
        return [[n]]:
    fi:

    # Now generate the partitions of n - k with largest part <= k.
    ret := []:
    for largest from min(n - k, k) by -1 to 1 do
        if k - largest in Di then
            next:
        fi:

        parts := PnkD(n - k, largest, Di):
        ret := [op(ret), seq([k, op(part)], part in parts)]:
    od:

    ret:
end:

# Return the set of all partitions of n such that every difference of
# consecutive parts is NOT in Di.
PnD := proc(n, Di)
    [seq(op(PnkD(n, k, Di)), k=1..n)]:
end:

# Return the number of all partitions of n with largest part k such that every
# part is congruent to some element of S mod n.
pnkD := proc(n, k, Di)
    option remember:
    if k > n then
        return 0:
    fi:

    if k = n then
        return 1:
    fi:

    # Every smaller partition adds 1.
    add(ifelse(k - largest in Di, 0, pnkD(n - k, largest, Di)), largest=1..min(n-k, k)):
end:

# Return the number of all partitions of n such that every part is congruent to
# some element of S mod n.
pnD := proc(n, Di)
    option remember:
    add(pnkD(n, k, Di), k=1..n):
end:

# 3.

[seq(pnC(n,{1},2),n=1..30)]; # A9 - definition (famous)
[seq(pnC(n,{1,4},5),n=1..30)]; # A3114 - definition
[seq(pnD(n,{0}),n=1..30)]; # A9 - definition (famous)
[seq(pnD(n,{0,1}),n=1..30)]; # A3114 - in the comments

# Some other interesting ones:
[seq(pnD(2 * n, {0}), n=1..10)];