hw8FirstLast.txt

Indicate whether it is OK to post

1. Examine the Maple code of

   Maple code for Lecture 8.

   Use them to get the following numbers

   (i) The number of 10-letter words in the alphabet {1,4,6} that add-up to 201

   (ii) The number of words in the alphabet {2,3,7} of ANY length, that add-up to 411

   (iii) The number of sequences of any length whose entries are either 1 (mod 5) or 4 (mod 5) and that add up to 341

2. In a
   composition
   the order matters. For example the set of compositions of 3 is {111,12,21,3}. In a
   partition
   the order does not matter, hence we agree to list it in weakly-decreasing order. For example, the set of partitions of 3 is {3,21, 111} (since 12 is the same as 21).

   Using the convention of representing partitions as weakly-decreasing sequences, write a procedure, call it Pnk(n,k) that inputs non-negative integers n and k and outputs the SET of all partitions of n whose LARGEST part is k. For example,

   [Added Oct. 1, 2020: example corrected thanks to Kent Mey, before it was according to the number of parts]

   Pnk(5,1)={[1,1,1,1,1]} , Pnk(5,2)={[2,2,1], [2,1,1,1]} , Pnk(5,3)={[3,1,1], [3,2]} , Pnk(5,4)={[4,1]]}, Pnk(5,5)={[5]}

   REMEMBER to use "option remember"

   Hint: When you take a partition [a1,a2,, .., ar] whose largest part is k (i.e.) a1=k and remove the first component (that is k), you get the partition [a2,.., ar] of n-k whose largest part a2, is <=k , so it is in natural bijection with

   Pnk(n-k,k) Union Pnk(n-k,k-1) Union ... Union Pnk(n-k,1)

   Another hint: Pnk(n,k) is the Empty Set if k>n

3. Adapt the above to write a procedure, pnk(n,k), that inputs non-negative integers n and k and outputs the NUMBER of all partitions of n whose largest part is k. For example,

   pnk(5,1)=1 , pnk(5,2)=2 , pnk(5,3)=2 , Pnk(5,4)=1, Pnk(5,5)=1

   REMEMBER to use "option remember"

4. By using pnk(n,k) write a procedure pn(n), that inputs a positive integer n and outputs the NUMBER of partitions of n.

   What is the OEIS A number of the integer sequence

   seq(pn(n),n=0...30);

   Hint: The set of partitions of n is Pnk(n,1) Union Pnk(n,2) Union ... Union Pnk(n,n)

5. [Typo corrected Oct. 5, 2020, previously pn was written p]

   What are
   [seq(pn(5*n+4) mod 5, n=1..50)]
   [seq(pn(7*n+5) mod 7, n=1..50)]
   [seq(pn(11*n+6) mod 11, n=1..50)]

6. [History of Math Optional challenge] Who discovered these facts?

   Added Oct. 5, 2020: The solutions of the students who kindly agreed to have them posted are in this directory

   ---

7. Lecture 9: Due Oct. 11, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw9FirstLast.txt

   Indicate whether it is OK to post

   1. Carefully read and understand the Maple code for Lecture 9, that contain procedures

      DiagSeq2(f,x,y,N), DiagWalks2D(S,N), DiagSeq3(f,x,y,z,N), DiagWalks3D(S,N)

      Using these procedures answer the following questions. Let a[i] be the i-th digit of your RUID. If it is zero, make it 1.

      • (i) What is the coefficient of x⁵⁰y⁵⁰ in the bi-Taylor expansion (around (0,0)) of the rational function

        1/(1-a[1]*x-a[2]*y+a[5]*x*y-a[6]*x^3+a[7]*y^3)

      • (ii) In how many ways can you walk from [0,0,0] to [30,30,30] if the fundamental ("atomic") steps are
        {[a[1],a[3],a[9]], [a[2], a[4], a[5], [a[4],a[3],a[3]}
        

   2. Write a Maple procedure WordsMod(a,S,x) that inputs a positive integer a, subse>t S of {1,2,..., a} and a variable x and outputs the rational function that is the generating function of finite sequence of positive integers that leave remainder that belongs to S when divided by a. Use the Maple "factor" to make it as nice as possible.

      What is the number of ways of walking from 0 to 100 where all positive steps are allowed except multiples of 5?

   3. Write a Maple procedure, ResComps(S,x), that inputs a finite set S of positive integers, and outputs the generating function for a(n) defined as the number of compositions of n where each component can be any positive integer except members of S.

      Using this, find the exact value of the number of walks from 0 to 300 where every step-size is permitted except 2 and 3

   4. Using procedure DiagWalks2D(S,N), with N=40 (or higher, if necessary) find which of the following is in the OEIS, and also use Maple's command

      gfun[listtorec](L,f(n))

      to guess a linear recurrence equation with POLYNOMIAL coefficients for the sequences DiagWalks2D(S,40) where

      • (i) S={[0,1],[1,0]}
      • (ii) S={[0,1],[1,0],[1,1]}
      • (iii) S={[0,1],[1,0],[0,2],[2,0]}
      • (iv) S={[0,1],[0,2],[1,0],[2,0],[1,1],[2,2]}

   5. Using procedure DiagWalks3D(S,N), with N=50 (or higher, if necessary) find which of the following is in the OEIS, and also use Maple's command

      gfun[listtorec](L,f(n))

      to guess a linear recurrence equation with POLYNOMIAL coefficients.

      • (i) S={[1,0,0],[0,1,0],[0,0,1]}
      • (ii) S={[0,0,1],[0,1,0],[0,0,1],[1,1,0],[1,0,1],[0,1,1]}
      • (iii) S={[0,0,1],[0,1,0],[0,0,1],[1,1,0],[1,0,1],[0,1,1],[1,1,1]}

   6. Write a 4-dimensional analog of DiagSeq3(f,x,y,z,N) and DiagWalks3D(S,N), calling them DiagSeq4(f,x1,x2,x3,x4,N) and DiagWalks4D(S,N) where S is a set of quadruples of positive integers (except that [0,0,0,0] is not allowed

   7. [Optional Challenge] Write k-dimensional analogs for ARBITRARY k call them

      DiagSeqk(k,x,f,N) and DiagWalkskD(k,S,N)

      that inputs a positive integer k, a symbol x, and a rational function f of x[1], ..., x[k], as well as a positive integer N for DiagSeqk and a pos. integer k, a set of lists of length k of positive integers S (where [0, ..., 0] is not allowed) and a positive integer N for DiagWalkskD.

      What is

      DiagWalkskD(5,{[0,0,0,0,1],[0,0,0,1,0],[0,0,1,0,0],[0,1,0,0,0],[1,0,0,0,0]},30)?

      Is it is in the OEIS? What about

      DiagWalkskD(5,{[0,0,0,0,1],[0,0,0,1,0],[0,0,1,0,0],[0,1,0,0,0],[1,0,0,0,0],[1,1,1,1,1]},30)?

   Added Oct. 12, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

   ---

   Lecture 10: Due Oct. 11, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw10FirstLast.txt

   Indicate whether it is OK to post

   1. Carefully read and understand the Maple code for Lecture 10, that contain procedures

      MulPers(P1,P2) , InvPer(P) , GrabCycle(P,i), PtoC(P), CtoP(C), FunT(pi), GG(S) , inv(pi), maj(pi) , FunT(pi)

      By doing the following computations, both by hand and by computer as follows

      • (i) Generate two random permutations of length 9 (use combinat[randperm](9)) , call them P1, P2, and BY HAND, find both P1*P2 and P2*P1 (* in the sense of permutation multiplication) check your answers by performing MulPerms(P1,P2) , and MulPerms(P2,P1). Are they the same

      • (ii) Generate a random permutations of length 9 (use combinat[randperm](9)) , call it P, and BY HAND, find the inverse permutation P^(-1). Then check it with InvPer(P)

      • (iii) Generate a random permutations of length 9 (use combinat[randperm](9)) , call it P, and BY HAND, find its cycle structure using the convention of PtoC(P) (each cycle must start with the largest element, and the cycles are arranged in increasing order of their first (i.e. largest) element. Then test your calculation by applying PtoC(P)
      • (iv) Generate a random permutations of length 9 (use combinat[randperm](9)) , call it P, and BY HAND, find its number of inversions and its major index (the sum of the places i such that pi[i]>pi[i+1]). Check that it agrees with inv(P) and maj(pi)

   2. Write procedures InvGF(n,q) and MajGF(n,q) that inputs a positive integer n, and a variable q, and outputs the weight-enumerator of the set of permutations of length n according to the number of inversion and major-index. In other words the sum of q^inv(pi) and q^maj(pi) respectively over all n! permutations. Is it true that InvGF(n,q)=MajGF(n,q) for n=1,...,7?

   3. Try to conjecture a formula for InvGF(n,q), by looking at the ratios InvGF(n,q)/InvGF(n-1,q) for n=2....,7.

   4. A permutation P is abc-avoiding if you can't find triples 1 ≤ a < b < c ≤ n such that pi[a] < pi[b] < < pi[c]. For example 43215 is abc-avoiding but 31425 is not. Find the first 8 members of the sequence

      "Number of abc-avoiding permutations of length n"

      and check whether it is in the OEIS.

      Hint: First write a procedure IsBad(P) that returns true as soon as you found an abc-pattern by doing a triple do-loop similar to the double do-loop in inv(P). Then write another procedure that goes over all the n! permutations and counts the ones that are not bad.

   5. [A little challenging, but do your best] Write a procedure InvFunT(P) that inputs a permutation P and outputs a permutation Q such that P=FunT(Q). Check it by running

      S:=permute(7): {seq(evalb(InvFunT(FunT(pi))=pi), pi in S)};{evalb(FunT(InvFunT(pi))=pi), pi in S)};

      getting {true} and {true}

      [Hint: Look at the structure of the output of FunT(P) and try "undo" it (or "parse" it), getting a list of cycles, and then use procedure CtoP]

   Added Oct. 12, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

   ---

   Lecture 11: Due Oct. 18, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw11FirstLast.txt

   Indicate whether it is OK to post

   1. In how many ways can you assemble 11 Russian dolls of different sizes into 5 different "towers"? In how many ways can you do it with any number of towers.

   2. First Write a one-line procedure xn(x,n) that inputs a variable x and a non-negative integer n and outputs
      x*(x-1)*(x-2)*...*(x-(n-1))
      using this, write another one-line procedure, call it Axn(x,n) that inputs a variable x and a non-negative integer n and outputs

      Sum(Snk(n,k)*xn(x,k),k=0..n)

      [Don't forget to use the Maple command "expand" so that you get the expanded form]

      What are Axn(x,i) for i=1..20? Can you get the formula for Axn(x,n) for any non-negative integer n?

   3. The (unsigned) Stirling number of the first kind, c(n,k) are defined as the number of permutations of {1,...,n} with exactly k cycles. By looking at a typical permutation (in cycle notation) of {1, ..., n-1} and figuring how to "insert" n into it, prove the recurrence

      c(n,k)=c(n-1,k-1)+ (n-1)*c(n-1,k)

   4. Write a Maple procedure cnk(n,k) (don't forget to use "option remember") analogous to Snk(n,k) in
      M11.txt
      that inputs positive integers n and k (1 ≤ k ≤ n) and outputs c(n,k)

   5. Can you get an explicit expression for

      Sum(c(n,k)*x^k,k=1..n) ?

      [Hint: don't forget to factor it at the end]

   6. [Optional challenge] Can you prove it?

   Added Oct. 19, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

   ---

   Lecture 12: Due Oct. 18, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw12FirstLast.txt

   Indicate whether it is OK to post

   ---

   I thank Yifan Zhang for spotting several errors in a previous version. He won 5 dollars.

   ---

   1. By iterating procedure CP(L1,L2), in

      M12.txt

      write a procedure

      CPg(L)

      that inputs a list of lists L=[L1,L2, ...,Lk] of "databases" (represented as lists L1, L2, ..., Lk) and outputs

      CP(L1,L2, ..., Lk)

      In particular, CPg([L1,L2]) should output the same as CP(L1,L2) for any two lists of integers L1 and L2

   2. Procedures AveClever(L) and kthMomentClever(L,k) inputs a database L, and first finds its weight-enumerator. Suppose that you already know the weight-enumerator, call it f, in the variable x. Modify these procedures to write procedures

      AveGF(f,x) and kthMomentGF(f,x,k)

      that do the same things if you already have the weight-enumerator f (in terms of x).

      In particular, for any "data-base" L, check that

      AveGF(WtEn(L,x),x)= AveClever(L)

      and

      kthMomentGF(WtEn(L,x),x,k)= kthMomentClever(L,k)

   3. The scaled moment about the mean of a "random variable" X (in other words some numerical attribute on a combinatorial) set, defined on a "sample spaces" is defined by

      m_k(X)/m_2(X)^(k/2)

      , where m_k(X) is the k-th moment about the mean.

      Write a procedure

      ScaledMomentGF(f,x,k)

      that compute it, given the weight-enumerator (alias generating-function)

   4. We proved in class that the weight-enumerator of the set of words in the alphabet {0,1} of length n, according to their sum (equivalently, the number of 1-s) is (1+x)ⁿ

      Leaving n as a symbol, use Maple to find explicit expressions for

      ScaledMomentGF(((1+x)/2)^n,x,k), k=2,3,4,5,6,7,8,9,10

      Then take limits as n goes to infinity (using the Maple command lim( ..., n=infinity)) Get a sequence of numbers. What is it?

      Is it in the OEIS?

   Added Oct. 19, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

   ---

   Lecture 13: Due Oct. 25, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw13FirstLast.txt

   Indicate whether it is OK to post

   ---

   1. Let A be the set of letters in your name e.g. in my case it is {b,d,e,i,g, o,l, r,n,z}.
      (i) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two consonants can be adjacent?
      • (ii) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be adjacent?

      • (iii) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two vowels can be adjacent and no consonants can be adjacent?

      • (iv): Let a(n) be the number of n-letters of words in that alphabet that have neither adjacent vowels nor adjacent consonants, and let

        f(t)=Sum(a(n)*t^n,n=0..infinity)

        Find f(t) explicitly.

   2. Using the appropriate procedure in M13.txt solve the following ancient puzzle (no credit for other methods!)

      A farmer, a wolf, a sheep, and a (very big) cabbage have to cross a river using a row boat that can only have the farmer and one of the other animals/vegetable. The wolf and the sheep can't be left unsupervised, and neither can the sheep and the cabbage (but the wolf and the cabbage can be left safely alone). How can this be done?

   3. [Optional Challenge] Write a Maple program that inputs a set of entities S, and a set of pairs {s1,s2} where s1 and s2 are not to be left alone unsupervised. Write a Maple program that

      • (i) Finds all the way ofs crossing the river safely (where each crossing should have the farmer, since he is the only one who knows how to row)

      • The number of ways of doing it

   4. Using the appropriate procedure in M13.txt solve the following more challenging puzzle

      3 Missionaries and 3 Cannibals have to cross a river using a row boat that can have at most two passengers (and at least one, it is not a self-driving boat). At no time can the cannibals outnumber the missionaries on either river-bank (unless there are no missionaries, of course). How to do it?

   5. [Optional Challenge] Write a Maple procedure MC(n,k), that generalizes the above from n=3 to general n and the maximum capacity of the boat is k. The above classical puzzle would be the case MC(3,2).

   Added Oct. 26, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

   ---

   Lecture 14: Due Oct. 25, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw14FirstLast.txt

   Indicate whether it is OK to post

   ---

   1. Use a procedure

      CountRuns(L,k)

      that inputs a list L of numbers (or for that matter, any objects) and outputs the number of "runs" of length k in L

      [A run of length k is a string L is an occurrence of an i such that L[i]=L[i+1]=...=L[i+k-1]

      For example

      CountRuns([1,2,2,2,1,1,1,1,2,2,2],3)

      is 4 for the runs starting at i=2, i=5, i=6, i=9. Note that it can be part of a longer run.

      [Hint: a quick way to find whether location i is the beginning of a run of length k (where i is between 1 and nops(L)-k+1, is to see if nope({op(i..i+k-1,L)})=1]

   2. Use the above CountRuns(L,k) that you just wrote, combined with procedure RPath in M14.txt to write a procedure

      AvePathRuns(m,n,k,N)

      That inputs positive integers m,n,k, and a LARGE positive integer N, generated N random paths, for each of them records the number of runs, and finds the sample average and standard-deviation (the square-root of the variance)

      Run

      AvePathRuns(200,200,5,3000)

      ten times and see what you get. Are they close to each other?

   3. Do the analogous thing for Good paths, writing

      AveGPathRuns(m,n,k,N)

      [Hint: you only have to change one word in the code]

      Run

      AvePathGRuns(200,200,5,3000)

      ten times. How does it compare with the previous output for all paths?

   4. A maximal run is a run L[i]=L[i+1]=...L[i+k-1] AND L[i-1]<> L[i] and L[i+k]<>L[i]

      [Hint: a quick way to find whether location i is the beginning of a MAXIMAL run of length k (where i is between 1 and nops(L)-k+1, is to see if nope({op(i..i+k-1,L)})=1 and L[i-1]<>L[i] and L[i+k]<>L[i]]

      Write procedures

      CountMaximalRuns(L,k), AvePathMaximalRuns(m,n,k,N), and AveGPathMaximalRuns(m,n,k,N)

      and do the analogous thing for the above two problems, (that you did for Runs) for Maximal Runs.

   5. Write a procedure

      GoodBrother(L)

      that inputs an arbitrary list of ODD length that adds up to 1 (so if the length is 2*n+1 it must have n+1 1's and n -1's), and outputs the UNIQUE cyclic shift that is a so-called Dyck path of length 2*n with 1 appended at the end.

      For example

      GoodBrother([[1,-1,-1,1,1,1,1,-1,-1,-1,1]=[1,1,1,-1,-1,-1,1,1,-1,-1,1]

   6. [Human exercise] Prove that the all the cyclic shifts of a word in {1,-1} that adds up to 1 are distinct.

      [Hint: if two cyclic shifts of such an L are identical, it means that there is some word w such that L is w repeated k times. The sum of L is k times the sum of w. Show that this can only happen if k=1]

   7. [Optional Challenge] Use the Wilf methodology discussed in the lecture to write a procedure

      RandSetPartition(n)

      That inputs a positive integer n and outputs a set-partition of {1, ..., n} where each of them has the same probability of being picked.

      Hint: One way of doing it is first write a preliminary procedure

      RandSetPartition1(n,k)

      that inputs positive integers n and k (k between 1 and n) and outputs a random set-partition with exactly k parts, using Snk(n,k) of M11.txt doing a LDie([Snk(n-1,k-1), k*Snk(n-1,k)]) and if the die lands on Snk(n-1,k-1) recursively generate a set partitions of {1, ..., n-1} with k-1 members [calling RandSetPartition1(n-1,k-1) ] and adjoin {n} to it, and in the latter case generate a random set partion of {1, ..., n-1} with k members, [calling RandSetPartition1(n-1,k) ] and then rand(1..k) to decide which of the k sets should invite n to join.

      Having done that RandSetPartition(n) would use

      LDie([seq(Snk(n,k),k=1..n)])

      To pick a k, then use the above procedure RandSetPartition1(n,k) with that k

   Added Oct. 26, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

   ---

   Lecture 15: Due Nov. 1, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw15FirstLast.txt

   Indicate whether it is OK to post

   1. Using the same methods in procedures KtG and KiG in ComboProj1.txt, write analogous procedures RoG(k,n), for the graph of a rook on a k by n chess-board, and use SAWnu(G), to find the first few terms of the number of Hamiltonian cycles in a 3 by n chessboard. Is it in the OEIS?

   2. Start exploring ComboProj2.txt, and use it to find the number of ways of walking from [0,0] to [40,40] with atomic steps {[1,0],[0,1],[1,1],[2,2]}

      How many of these never go above x=y?

      Start exploring ComboProj3.txt, and use it to find the first 20 terms of of the sequence enumerating walks from [0,0,0] to [n,n,n] with atomic steps {[1,0,0],[0,1,0],[0,0,1],[1,1,1]}. What is the corresponding sequence for those walks that stay in x ≥ y ≥ z ?

   Added Nov. 2, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

   ---

   Lecture 16: Due Nov. 1, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

   hw16FirstLast.txt

   Indicate whether it is OK to post

   1. An involution is a permutation whose cycle structure consists only of cycles of length 1 and 2. Let p_3(n) be the number of permutations whose cycle structure consists of cycles of length 1, 2, or 3. Find a linear recurrence satisfied by p_3(n), and express the linear recurrence operator ope(n,N) annihilating it. What is the order of the recurrence? Using procedure SeqFromRec in in ComboProject4.txt find p_3(200).

   2. [Optional Challenge] Let p_k(n) be the number of permutations whose cycle structure consists of cycles of length ≤ k. Find a linear recurrence satisfied by p_k(n), and express the linear recurrence operator ope(n,N) annihilating it. What is the order of the recurrence?

   3. Write a procedure that inputs a positive integer n and outputs the sum of binomial(n,k)^6 from k=0 to n. Call is S6(n). Then write a one-line procedure S6seq(N) that inputs a positive integer N and outputs the first N terms of the sequence S6(n).

      Using procedure Findrec in ComboProject4.txt find a linear recurrence operator annihilating it (equivalently a recurrence) and the initial condition, and write procedure S6seqClever(N) that uses procedure SeqFromRec from the same Maple package to do the same thing as S6seq(N).

      What are

      time(S6seq(1000));

      and

      time(S6seqClever(1000)); ?

      Added Nov. 2, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

      ---

      Lecture 17: Due Nov. 8, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw17FirstLast.txt

      Indicate whether it is OK to post

      1. Use the appropriate procedure in ComboProject1.txt to find the number of ways a King can travel on a 3 by 50 chessboard, return to the starting square and visit each of the 150 squares exactly once.

      2. Use the appropriate procedures in ComboProject2.txt to find the number of ways of walking from [0,0] to [3000,3000] using, as atomic steps {[1,0],[0,1],[1,1],[1,2],[2,1]}, all the while staying in the region x ≥ y

         Don't do it directly! Use Findrec followed by SeqFromRec.

      3. Use the appropriate procedures in ComboProject3.txt to find the number of ways of walking from [0,0,0] to [3000,3000,3000] using, as atomic steps {[1,0,0],[0,1,0],[0,0,1],[1,1,1]}, all the while staying in the region x ≥ y ≥ z

         Don't do it directly! Use Findrec followed by SeqFromRec.

      4. Use the appropriate procedures in ComboProject4.txt to find

         Sum(binomial(3000,k)^2*binomial(3000+k,k)^2,k=0..3000)

         Don't do it directly! Use Z and then use SeqFromRec.

      5. Use the appropriate procedures in ComboProject5.txt to find the number of 3 by 101 TicTacToe boards that ended in a tie (i.e. had 151 X's and 150 O'x and no three consecutive Xs, or O's horizontally, vertically, or diagonally.

      6. Use the appropriate procedures in ComboProject6.txt to approximate the average degree of an induced graph if you take 1000 random choices of 257 vertices in Bn(9). Of course it changes from run to run, but it should be close.

      7. Use the appropriate procedures in ComboProject7.txt to find the coefficient of x²⁰⁰⁰ y²⁰⁰⁰ in the bi-variate Taylor series of

         1/(1-4*x-5*y+11*x*y)

         Don't do it directly!

      Added Nov. 9, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

      ---

      Lecture 17a: Due Nov. 8, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw17aFirstLast.txt

      Indicate whether it is OK to post

      1. Use Wikipedia (or otherwise) to find the final outcome of the electoral votes for the presidential elections for 2000, 2004, 2008, 2012, and 2016, and find the number of ways in which it could have been counted to lead to the final outcome, by using the appropriate procedures in ComboProject8.txt.

      2. Assuming, rather unrealistically, that the probability of winning for either of the candidates is the same for each state, and that they are independent of each other, use the popular vote (also given in Wikipedia), use the appropriate procedure to find the (estimated) probability of the ultimate winner of (i) winning (i.e. scoring at least 270 votes) (ii) scoring that many electoral votes or more.

      3. Using procedure SimCount(L,p,N,K) with N=2000, K=4, four times and with p=3/10, 2/5,1/2,3/5,7/10, and L=USEC(), see whether the first component of the output (that give estimates for the expectation, standard-deviation, and the 3rd, and 4th moments) agree with each other (remember they are only statistical estimates) and how they are close to the true value obtained by using StatAnal(f,x,K) applied to GFvp(USEC(),p,x). I have no clue about the theoretical (exact) value of the probability that such a count is consistent, but the second output of SimCount(L,p,N,K) give estimates. How close, in the above-mentioned four runs are there to each other?

      Added Nov. 9, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

      ---

      Lecture 18: Due Nov. 15, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw18FirstLast.txt

      Indicate whether it is OK to post

      1. [Better Version of Nov. 11, 2020 ]

         Generalize procedure NuConG(N) of M18.txt to write a procedure

         NuKcomponentsGraphs(N,K)

         that inputs a positive integer N and another positive integer K and outputs the first N terms of the sequence enumerating the number of labeled graphs on n vertices with Exactly K componets. Make sure that NuKComponentsGraphs(N,1) equals NuConG(N) for N ≤ 6
         Hint: Of course, you first need to write a procedure AllKcomponentsGraphs(n,K) by tweaking procedure AllConGraphs(n) and change the line nops(CCs(s))=1 to nops(CCs(s))=k

         Are the following sequences in the OEIS? If yes, what are the A-numbers

         NuConGgen(5,2), NuConGgen(5,3)

      2. Using procedures RandGr(n,K) and CCs(G), in M18.txt

         write a procedure

         AveNuCC(n,K,M)

         that generates M random graphs on n vertices with K edges, and for each of them finds the number of components and take the average over these M random graphs. Run it several times with n=30 and M=1000 to check that you get close answers. If not what M would give such agreement?

      3. Using the above,say, write a procedure

         EstimateCutOff(n,M)

         that inputs a positive integer n and outputs an estimate for the "threshold" for K, when most graphs with K edges start to be connected (say when the average number of connected componets is less than 1.05)

      4. [Optional challenge] Running it for various n from 100 to 200, and M=1000 (or possibly larger) Can you conjecture an expression for that cut-off in terms of n?

      5. [Optional challenge in human mathematics] Prove that a graph in n vertices has no cycles if and only if it is (i) connected (ii) has exactly n-1 edges

      Added Nov. 16, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

      ---

      Lecture 19: Due Nov. 15, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw19FirstLast.txt

      Indicate whether it is OK to post

      1. Carefully read the section about exponential generating functions in Dr. Z.'s essay. Reproduce the proof that egf(AxB)=egf(A)*egf(B) in your own words, and understand it . [It may come up in the oral part of the Final Exam!]

      2. Using Maple or otherwise find the ordinary generating function and exponential generating function for

         a(n)=n*(n-1)*(n-2) (n ≥ 0)

      3. (i) How many ordered pairs [SP1,SP2] are there where SP1 and SP2 are set partitions of different sets whose total numbers is 100 and the labels are {1, ..., 100}

         (ii) How many sets {SP1,SP2} where SP1 and SP2 are set-partitions of different sets whose total numbers is 100 and the labels are {1, ..., 100} ?

         [Reminder the egf of set-partitions is exp(exp(x)-1) ]

      Added Nov. 16, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

      ---

      Lecture 20: Due Nov. 22, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw20FirstLast.txt

      Indicate whether it is OK to post

      1. How many set partitions are there of a 100-element set such that

         (i) There are exactly 7 components, and each component has odd size

         (ii) There are exactly an odd number of components, but the sizes of the components can be any strictly positive integer

         (iii) There are exactly an odd number of components, but the sizes of the components can be any strictly positive integer except that we do not allow componets of size 2 and 5

      2. How many permutations are there of {1,2,..., 100} such that

         (i) There are exactly 7 cycles, and each cycle has odd size

         (ii) There are exactly an odd number of cycles, but the length of the cycles can be any strictly positive integer

         (iii) There are exactly an odd number of cycles, but the lengths of the cycles can be any strictly positive integer except that we do not allow cycles of length 2 and 5

      3. How many labeled connected graphs are there with 100 vertices? How many are there with exactly 2 components? With exactly 100 components?

      Added Nov. 23, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

      ---

      Lecture 21: Due Nov. 22, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw21FirstLast.txt

      Indicate whether it is OK to post

      1. How many labeled connected graphs with 50 vertices and 70 edges are?

      2. How many labeled graphs with i connected components with 50 vertices and 70 edges are for i=2,3,4,5? Explain how you do it, by using the taylor command in Maple.

      3. In the homework assigment for Lecture 18 you were asked to write a procedure

         EstimateCutOff(n,M)

         by simulating it M times, and using as cutoff 1.05. Procedure FindCutOff(n,co) in

         M21.txt

         does it EXACTLY, for an arbitrary parameter co (foremerly I asked you to take 1.05).

         Comparee the output of the simulated procedure with the exact one, i.e. compare your EstimateCutOff(30,1000) with my exact FindCutOff(30,1.05)

      4. Try to do the optional challenge from the homework of Lecture 18 exactly, using evalf(FindCutOff(n,1.05)/n), for n= 20,30,40,50,60. Do you see a trend?

      5. Generalize procedure

         EstProbConn(n,m,N):

         and write a procedure

         EstProbKcomps(n,m,k,N):

         that estimates the probability that a random graph with n vertices and m edges has exactly k components, by sampling N such random graphs.

         Note that EstProbKcomps(n,m,1,N) is exactly the same as EstProbConn(n,m,N) (except, since we are doing simulations, you get different answers each time)

      6. Generalize procedure

         ProbConn(n,m):

         To write a procedure

         ProbKcomponents(n,m,k)

         that uses the method of exponential generating functions to find the EXACT probability that a random graph with n vertices and m edges has k components. Note that ProbKcomponents(n,m,1) is EXACTLY the same as ProbConn(m,m,1)

         [Hints: (i) you may need to write another procedure generalizing one of those that I wrote and that was used in ProbConn(n,m). (ii) the egf of labeled graphs with n vertices and k components with keeping track of the number of edges (i.e. the weight-enumerator according to the weight a^{number of edges}) is

         (log(Sum((1+a)^(n*(n-1)/2)*x^n/n!,n=0..infinity))^k/k!

         How does ProbKcomponents(40,50,2) differ from EstProbKcomps(40,50,2,300)?

      Added Nov. 23, 2020: The solutions of the students who kindly agreed to have them posted AND were perfect (or almost perfect) are in this directory

      ---

      Lecture 22: Due Dec.6, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw22FirstLast.txt

      Indicate whether it is OK to post

      1. (i) How many labeled ROOTED trees are there with 67 vertices and 12 leaves? (recall that a leaf is a vertex with no children) (ii) How many labeled connected graphs are there with 40 vertices and 43 edges?

         [Added Nov. 30, 2020: The procedure TreeSeqL(N,t) counts ROOTED labelled trees, according to the number of leaves, and not as (possibly) stated erroneusly in the lecture, unrooted trees].

      2. Write a procedure SeqRTchild(S,N), that inputs a finite set of positive integers, S, and a positive integer N, and outputs the first N entries in the lhe list enumerating rooted labeled trees where every vertex is either a leaf (i.e. 0 children) or has a mumber of children that must be in the set S.

         Output SeqRTchild(S,30) for the following sets S if it is in the OEIS, state the A-number. If it is not, say so.

         (i) S={1,2}

         (ii) S={1,2,3}

         (iii) S={1,2,3,4}

         (iv) S={1,3,4}

         (v) S={2,3,4}

      3. Write a procedure SeqRTchildNone(S,N), that inputs a finite set of positive integers, S, and a positive integer N, and outputs the first N entries in lhe list enumerating rooted labeled trees where every vertex is either a leaf (i.e. 0 children) or has a mumber of children that must NOT be in the set S (otherwise it can have any number of children)

         Output SeqRTchildNone(S,30) for the following sets S if it is in the OEIS, state the A-number. If it is not, say so.

         (i) S={1,2}

         (ii) S={1,2,3}

         (iii) S={1,2,3,4}

         (iv) S={1,3,4}

         (v) S={2,3,4}

      4. By using procedure TreeSeqL(N,x) and procedure AveAndMoms(f,x,K) with K=6, added after class, try to

         (i) Estimate the limit of the average number of leaves in a labelled tree with vertex n divided by n

         (ii) Estimate the limit of the standard-deviation of the number of the random variable ` number of leaves in a labelled tree with vertex n', divided by n

         The third, fourth, fifth, and sixth scaled moments

      5. Optional challenge: Derive the exact value of the limit in (i) above

      6. Optional even bigger challenge: Derive the exact value of the limit in (ii) above

      ---

      Lecture 23: Due Dec.6, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

      hw23FirstLast.txt

      Indicate whether it is OK to post

      1. Pick a random tree, T, using RandTree(14); of M23.txt and find its Pruffer Code, BY HAND! Check that it agrees with Pruffer(T);

      2. Pick a random function from {1,2,..., 15} to itself, using RandF(15), call it f, and find, BY HAND, the doubly-rooted tree that you get with Joyal's mapping. Check that it is the same as Joyal(f).

      3. Read and understand procedure Pruffer(T) and InvPruffer(C). Check empirically, for several choices of RandTree(100), that InvPruffer(Pruffer(T))=T

      4. Write a competitor to RandTree, Call it RandTree1(n), that inputs a positive integer n and outputs a random tree with n vertices, but that uses procedure InvPruffer(C) rather than Joyal(f). First generated a random list of length n-2, whose entries are from {1, ..., n}, and then apply InvPruffer to it.

         By typing
         time(RandTree(2000));
         several times, and your own
         time(RandTree1(2000));
         the same number of times, find out who is faster. Can you explain why?

      5. Write a procedure: EstAveLeaves(n,K), that inputs a posive integer n and a large positive ineger K, and outputs an ESTIMATE for the average number of leaves in a labelled tree on n vertices.

         [Hint: use RandTree(T), K times, finding the number of leaves (using nops(Leaves(T))]

         Run EstAveLeaves(100,1000) several times. How close is it to 99/exp(1)? (that we got exactly in Lecture 22)

      6. Read and understand this gem, for yet another proof of Cayley's formula. Implement in Maple the function R(e,b) given by equation (*) (Remember to use "option remember"), and verify empirically that it equals indeed b(b+e)^e-1

      7. [Optional Challenge] Write a procedure RevJoyal, that inputs a doubly-rooted tree in the format SetOfEdges,[FirstRoot,SecondRoot] (like the output of Joyal), and outputs a function f from {1,...n} to itself given as a list of length n. Check that RevJoyal(Joyal(f))=f for several choices of Randf(30); in M23.txt

         [Hint: First write a function Path(T,i,j) that inputs a tree T (given as a set of edges) and two vertices i and j, and outputs the unique path that joins i and j. For example, Path({{1,2},{1,3},{1,3}},2,4); should output [2,1,4] and Path({{1,2},{1,3},{1,3}},2,2); should output [2]. Then the sekeleton of the doubly rooted tree T,[a,b] (the output of Joyal(f)) is Path(T,a,b). Then use CtoL to get a collection of cycles, that would give you how f acts on members of the cycles. Then restore the edges that are not part of the skeleton, but now they have directions, and this would give you the rest of the function f].

      ---

      class web-page