1. 
    (a).
        By using ComboProject3.txt. 

        NuW([30, 25, 20], {[1, 0, 0],[0, 1, 0], [0, 0, 1]}) = 2478456799816702091914145225486880

        Totally 2478456799816702091914145225486880 ways to walk. 

    (b). 
        Because we need to stay in the region x>=y>=z. This is a good walk. 

        So we use 
        NuGW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}) = 41512613892711511465063226481480
        ways to walk. 

    (c).
        NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [2, 2, 2]}) = 
              31831650298097356165593942880232160 ways. 

    (d).
        NuSpecialGW:=proc(Pt,A) local a:
            option remember:

            if (Pt[1]<0 or Pt[2]<0 or Pt[3]<0 or Pt[1]<Pt[2] or Pt[1]<Pt[3]) then   # this is the line that changed from NuGW, we need to account for z > x 
            RETURN(0):
            elif Pt=[0,0,0] then
            RETURN(1):
            else
            add(NuSpecialGW(Pt-a,A),a in A):
            fi:
        end:

        NuSpecialGW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [2, 2, 2]}) = 3818966446210163616599115660989544
    (e). 
        TODO 

2. 
    (a).
        By using M8.txt
        f := CompsGFk({0, 1, 2, 3}, x, 30): # this is the generating function which after expansion the coefficient of x^n is the amount of words of length 30 that add up to n. 
        add(coeff(f, x, i), i = 0 .. 90);   # by summing over all possible coefficient we have the total number of words. 
        = 1152921504606846976

        Another way to do this is 4^30, for every slot we have 4 choice we need to choose 30 times. 

    (b).
        By using M8.txt
        f := CompsGF({1, 2, 3, 4}, x):  # this is the generating function which after expansion coefficient of x^n is the number of words that add up to n. 
        coeff(taylor(f, x, 301), x, 300) = 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769
    (c).
        We use weighted enumerator for this. 
        W_x = 1 + W_x1 + W_x2 + W_x3 + ...
        W_x = 1 + x*W_x + x^2*W_x + ...
        W_x = 1 + W_x(x + x^2 + x^3 + ...)
        W_x = 1 + W_x(1/(1-x) - 1)
        W_x = 1 / (2 - (1 / (1-x)))
        By using simplify(W_x) in Maple
        we have 
        gf := (x - 1)/(2*x - 1)
        So the general formula for number of words that add up to n is going to be the coefficent of the expansion of gf. 

    (d).
        The alphabet can be represented by 1 + 3 * i (i = 0 .. infinity)

        By using similar methodology like above, 
        we have
        W_x = 1 + W_x(x + x^4 + x^7 + x^10 ...)

        Notice that in the parenthesis
        x + x^4 + x^7 + x^10 ... = x*(1 + x^3 + x^6 + x^9 + ...)
        = x*((x^3)^0 + (x^3)^1 + (x^3)^2 + (x^3)^3 + ... ) # contains a infinite geometric series on x^3. 

        = x * (1/(1 - x^3))

        So
        W_x = 1 + W_x * x * (1 / (1-x^3))
        By simplifying using maple, we have
        W_x = (x^3 - 1)/(x^3 + x - 1). 

        So the generating function is W_x. 
        
    (e).
        TODO 

3. [egf]
    (a).
        Based on lecture notes. The egf of set-partitions is exp(exp(x)-1).

        coeff(taylor(exp(exp(x) - 1), x, 101), x, 100)*100! = 47585391276764833658790768841387207826363669686825611466616334637559114497892442622672724044217756306953557882560751

    (b).
        To express 1, 4, 7, 10, ... , it is actually 3*i + 1 for i = 0..infinity. 

        Because the components can be of anysize. 
        Component's generating function is
            f := sum(x^n/n!, n=1..infinity) = e^x - 1
        For the number of partitions, we can make 
            egf := add(f^(3*i+1)/(3*i+1)!, i=0..infinity);

        For the question {1,2...51}, because we have 51 elements, i = 17 can cover all the necessary cases. 

        So 
        egf := add(f^(3*i + 1)/(3 + 1)!, i = 0 .. 51);
        coeff(taylor(egf, x, 52), x, 51)*100! = 122664018294562348369198169770917045999440490335871253335316171776873737027682910088471911682377897417082729276836979409951882514641535694976150423994368000000000000
    (c).
        Because components can only have odd size. 
        So the size can be represented by 2 * i + 1 (i = 0..25)
        The egf for component is: 
            f := add(x^(2 * i + 1) / (2 * i + 1)!, i = 0..25); 
            Because number of components can be any non-negative integer, 
            So 
                egf := sum(f^n/n!, n = 1..infinity):
                coeff(taylor(egf, x, 52), x, 51)*51! = 101595492022700597152023270326642584710021120
    (d).
        Because components can only have odd size. 
        So the size can be represented by 2 * i + 1 (i = 0..25). 

        The egf for the component is 
        f := add(x^(2 * i + 1) / (2 * i + 1)!, i = 0..25);

        Because number of components has to be in the form of 3 * i + 1 (i = 0..infinity)
        So 
            egf := sum(f^(3*i + 1)/(3*i + 1)!, i = 0 .. 20):    # i = 20 here for safety, because we only have 51 elements we definitely have less than 61 components. 
            coeff(taylor(egf, x, 52), x, 51)*51! = 30143119660583350838086153637731292910753195


4. [super-set-partition]
    (a).
        [K = 1]
        {{{1},{2},{3}}},
        {{{1,2},{3}}}.
        {{{1,3},{2}}}
        {{{1},{2,3}}}
        {{{1,2,3}}}

        [K = 2]
        One partition has to have 1 number, and the other one has to have 2 numbers. 
        {{{1}},{{2},{3}}}
        {{{1}},{{2,3}}}
        {{{2}},{{1},{3}}}
        {{{2}},{{1,3}}}
        {{{3}},{{1},{2}}}
        {{{3}},{{1,2}}}

        [K = 3]
        Every partition has to have 1 number 
        {{{1}},{{2}},{{3}}}

        Totally 12 ways. 

    (b). 
        By using M11.txt. 

        To form a set partition of set partition over n elements. We first need to see the set partition of these n elements. Then for every possible set partition of size k, we compute another set partition of k elements make this number q. We sum all the q, then we will have our result. 

        supersetp := proc(n) local i, res;
            res := 0;
            for i from 1 to n by 1 do
                res := res + Snk(n, i) * Bell3(i);  # here we use stirling number of second kind to get how many ways we can partition n elements into i sets. Then we run set partition on i elements and sum the result. 
            end do;
            return res;
        end:

        seq(supersetp(i), i = 1 .. 10) = 1, 3, 12, 60, 358, 2471, 19302, 167894, 1606137, 16733779  [in OEIS A258]

        Another way to do this is by using the fundamental theorem of exponential generating function which we can get the explicit formula being exp(exp(exp(x) - 1)-1)


    (c).
        We can keep using 
        f := exp(f - 1) to find the next level of generating function. 

        m = 3: in OEIS: A307
        m = 4: in OEIS: A357
        m = 5: in OEIS: A405
        m = 6: in OEIS: A1669
        m = 7: in OEIS: A81624
        m = 8: in OEIS: A81629
        m = 9: in OEIS: A81697
        m = 10: in OEIS: A81740
        m = 11: not in OEIS.

5.  [integer partition]
    (a).
        By using M24.txt
        pn(1000) = 24061467864032622473692149727991
    (b).
        pnC(1000, {1}, 2) = 8635565795744155161506
    (c).
        pnD(1000, 1) = 8635565795744155161506
    (d).
        TODO. 

6. [rooted labelled tree]
    (a).
        By using M22.txt
        L := TreeSeq(31)[31] = 17761887753093897979823770061456102763834271
    (b).
        TODO  
        
    (c).
        SeqRTchild := proc(S, N) local egf, z, s, L, n: 
            egf := 1;

            for s in S do: 
                egf := egf + z^s/s! # note, this comes from after removing the root, we wlil have s many more components 
            end do; 

            L := FunEqToSeq(egf, z, N); 
            
            return [seq(L[n] * n!, n = 1..N)];
        end: 

        SeqRTchild({1, 3, 4}, 31)[31] = 388391178300656853181332829972846230000000
    (d).
        For this we use another procedure that I wrote for HW 22 

        SeqRTchildNone := proc(S, N) local egf_modifier, z, s, L, n: 
            egf_modifier := 0;

            for s in S do: 
                egf_modifier := egf_modifier + z^s/s!
            end do; 

            L := FunEqToSeq(exp(z) - egf_modifier, z, N); 
            
            return [seq(L[n] * n!, n = 1..N)];
        end:

        SeqRTchildNone({1, 3, 4}, 31)[31] = 2863465748628395267057869436794752181

7. [complete binary tree]
    (a).
        BT(4) = {[[],[[],[[],[]]]], [[],[[[],[]],[]]], [[[[], []], []],[]], [[[],[[],[]]], []], [[[],[]],[[],[]]]}
    (b).
        TODO