#OK to post homework 
#Zhizhang Deng, 10/19/2020, Assignment 10

1. 
(i).
    P1 = [3, 8, 4, 9, 1, 5, 6, 7, 2]
    P2 = [8, 5, 6, 4, 3, 9, 7, 2, 1]

    [By Hand]
    P1 * P2 = [6, 2, 4, 1, 8, 3, 9, 7, 5]
    P2 * P1 = [7, 1, 5, 9, 4, 2, 6, 8, 3]

    [By Program]
    MulPers(P1, P2) = [6, 2, 4, 1, 8, 3, 9, 7, 5]
    MulPers(P2, P1) = [7, 1, 5, 9, 4, 2, 6, 8, 3]

(ii). 
    P = [2, 4, 1, 5, 8, 9, 7, 3, 6]
    [By Hand]
    Inverse: [3, 1, 8, 2, 4, 9, 7, 5, 6]

    [By Program]
    InvPer(P) = [3, 1, 8, 2, 4, 9, 7, 5, 6]

(iii). 
    P = [4, 6, 9, 1, 3, 7, 5, 8, 2]
    
    [By Hand]
    P = 
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [4, 6, 9, 1, 3, 7, 5, 8, 2]

    Cycles: [1->4->1, 2->6->7->5->3->9->2, 8->8]
    Ordered Cycles: [4-1, 8, 9-2-6-7-5-3]

    [By Program]
    PtoC(P) = [[4, 1], [8], [9, 2, 6, 7, 5, 3]]

(iv). 
    P = [5, 7, 1, 4, 9, 8, 3, 6, 2]
    Majob index
        [By Hand]
        major index: 2 + 5 + 6 + 8 = 21
        [By Program]
        maj(P) = 21
    Inversion 
        [By Hand]
        inv = [5-1,5-4,5-3,5-2],[7-1,7-4,7-3,7-6,7-2],[4-3,4-2],[9-8,9-3,9-6,9-2],[8-3,8-6,8-2],[3-1],[6-2]
        inv = 4 + 5 + 2 + 4 + 3 + 1 + 1 = 20
        [By Program]
        inv(P) = 20

2. 
    InvGF := proc(n, q) local ps, res, i, ps_size option remember:

    ps := permute(n);
    res := 0;

    ps_size := nops(ps) ;

    for i from 1 by 1 to ps_size do
        res := res + q^(inv(ps[i]));
    end do;

    RETURN(res);

    end:

    MajGF := proc(n, q) local ps, res, i, ps_size option remember:

    ps := permute(n);
    res := 0;

    ps_size := nops(ps) ;

    for i from 1 by 1 to ps_size do
        res := res + q^(maj(ps[i]));
    end do;

    RETURN(res);

    end:

        seq(evalb(MajGF(n, x) = InvGF(n, x)), n = 1 .. 7) = true, true, true, true, true, true, true

3. 
    Look at the result of seq(simplify(InvGF(n, q)/InvGF(n - 1, q)), n = 2 .. 7) is as following
    1 + q
    q^2 + q + 1
    q^3 + q^2 + q + 1
    q^4 + q^3 + q^2 + q + 1
    q^5 + q^4 + q^3 + q^2 + q + 1
    q^6 + q^5 + q^4 + q^3 + q^2 + q + 1

    Conjecture will be: 
    InvGF(n, q) = InvGF(n - 1, q) * [sum_i_from_1_to_n-1(q^i) + 1]

4. 
    bad := proc(p) local n, a, b, c option remember: 

    n := nops(p);

    for a from 1 by 1 to n - 2 do
        for b from a by 1 to n - 1 do
            for c from b by 1 to n do
                if p[a] < p[b] < p[c] then
                    return true; 
                end if;
            end do;
        end do;
    end do;

    return false; 

    end:
    ##############################################
    abc := proc(n) local i, ps, ps_size, counter: 

    ps := permute(n);
    ps_size := nops(ps);
    counter := 0;

    for i from 1 by 1 to ps_size do
        if not bad(ps[i]) then
            counter := counter + 1; 
        end if;
    end do;

    return counter; 

    end:
    Multiple matches in OEIS, one of them is A000108

5.