# OK to post homework
# Robert Dougherty-Bliss
# 2021-04-25
# Assignment 25

# 1.

# Return the hook set of `cell` in `L`.
# `cell` will always be the first element.
HookSet := proc(L, cell)
    local i0, j0, i, right, down:
    i0 := cell[1]:
    j0 := cell[2]:

    right := seq([i0, j], j=j0..L[i0]):
    down := NULL:
    for i from i0 + 1 to nops(L) while L[i] >= j0 do
        down := down, [i, j0]:
    end:

    {right, down}:
end:

# 2.

randomCell := proc(L)
    local n, i, j, k:
    n := rand(1..add(L))():

    i := 1:
    j := 1:

    for k from 1 to n - 1 do
        if j >= L[i] then
            i := i + 1:
            j := 1:
        else
            j := j + 1:
        fi:
    od:

    [i, j]:
end:

# Return the corner cell that you WOULD place an element in.
OneStepGNW := proc(L)
    local cell, H:
    # Here's something that DOESN'T work: Pick a random row, then a random
    # column in that row.

    # What is the probability that we choose (i, j)?
    #       1 / nops(L) * 1 / L[i]
    # This is not 1 / n.

    cell := randomCell(L):

    H := HookSet(L, cell):

    while nops(H) > 1 do
        cell := H[rand(2..nops(H))()]:
        H := HookSet(L, cell):
    od:

    return H[1]:
end:

# 3.

GNW := proc(L)
    local Lnew, T, k, cell, i:
    Lnew := L:
    T := [[] $ nops(L)]:

    for k from add(L) to 1 by -1 do
        cell := OneStepGNW(Lnew):
        # We don't NEED j if we just want the tableaux.
        # We could easily construct the record tableaux with it, though.
        i := cell[1]:
        Lnew[i] := Lnew[i] - 1:
        T[i] := [k, op(T[i])]:
    od:

    T:
end:

# Nearly instantaneous!
GNW([10 $ 10]);

# 4.

(*
    The n! factor is the same in both formulas, so we're really trying to prove
    the following:

        Delta(a1 + k - 1, a2 + k - 2, ..., ak) / (a1 + k1 - 1)! / (a2 + k - 2)! / ... / ak!
        =
        1 / prod(h(i, j), 1 <= i <= k, 1 <= j <= ai).

    Can we just write down h(i, j)?

        h(i, j) = a(i) - j + 1       +  number of a(k) >= i with k > i.
                ("right" of [i, j])       (strictly "below" [i, j])
                = a(i) - j + 1 + sum([a(k) >= i], k > i).

    My plan of attack (which I have not yet completed):

        Let H(n) be the product of the hook lengths of the shape [a1, a2, ...,
        an].

        1. Adding a new row increases some hook lengths by exactly 1 and adds
           some extra hook lengths.

            What are the hook lengths that increase? Exactly those where the
            "bottom" set extends down to the tableaux's bottom, and the new row
            is long enough. These would be the (i, j) such that

                a(k) >= j for i <= k <= n + 1.

            Call the set of these cells E(n + 1).
            Now we have the following:

                H(n + 1) = H(n) * A(n) / B(n)

                A(n) = a(n) * (a(n) - 1) * ... * 1 * prod(h(i, j) + 1, (i, j) in E(n + 1))
                B(n) = prod(h(i, j), (i, j) in E(n + 1)).

            In particular,

                H(n + 1) / H(n) = A(n) / B(n).

        2. Adding a new row modifies the discriminant and factorials in an
        obvious way.

            Let Delta(a1, a2, ..., an) = prod(ai - aj, 1 <= i < j <= n),
            and

                D(n) = Delta(a1 + n - 1, a2 + n - 2, ..., an).

            Then:

                D(n + 1) = D(n) * (a1 - a(n + 1) + n) * (a2 - a(n + 1) + n - 2) ... (an - a(n + 1)).

        3. Look at quotients.

    Actually, the *right* way to prove this is just to check that both sides
    satisfy the same recurrence. Yuxuan checked the Young-Frobenius case last
    week, and the GNW paper checks the the hook-length formula.
*)