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 sequenes of any length whose entries are either 1 (mod 5) or 4 (mod 5) and that add up to 341

2. In a
   compositon
   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 LARGET 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, subsest 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 inegers S (where [0, ..., 0] is not allowed) and a positive ineteger 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 permuations 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 permuations 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 permuations 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 calclulation by applying PtoC(P)
      • (iv) Generate a random permuations 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) explicilty.

   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 Canibals 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 canniabls 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 clasical 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 occurence 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 inetgers 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 squre-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-partion of {1, ..., n} where each of them has the same probability of being picked.

      Hint: One way of doing it is first write a prelininary 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 partions 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 ?

   ---

   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)); ?

      ---

      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 exaxtly 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 consectutive Xs, or O's horizontally, vertically, or diagonally.

      6. Use the appropriate procedures in ComboProject6.txt to approxinate the average degree of an induced graph if you take 1000 random choices of 257 vetrices in Bn(9). Of coure it changses 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!

      ---

      class web-page