Last Update: May 3, 2021

• Teacher: Dr. Doron ZEILBERGER ("Dr. Z")

• "Classroom": Synchronous Remote, Invitations were sent to the registered students. If you want to audit this class, please Email me at DoronZeil at gmail dot com and I will send you an invitation.
  

• Time: Mondays and Thursdays , period 3 (12:00noon-1:20pm)

  Dr. Zeilberger's Email: DoronZeil at gmail dot com ; Official Email: zeilberg@math.rutgers.edu
  

• Dr. Zeilberger's Remote Office Hours (Spring 2021): by appointment. Please email me.
  

Description

Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in that direction. In addition to learning the philosophy and methodology of this budding field, students will become computer-algebra wizards, and that should be very helpful in whatever mathematical specialty they are doing (or will do) research in.

We will first learn Maple, and how to program with it. This semester we will learn, from an experimental mathematics point of view, algorithmic enumerative and statistical combinatorics. The final projects may lead to published papers. People who already took previous editions are welcome to take it again, since except for the basics, there is very little overlap with previous editions.

This class is suitable for graduate students in other departments, and the software development skills learned will be useful for doing any quantitative research. Smart advanced undergraduates are also welcome. In particular, the statistical methods learned for researching enumerative combinatorics should be applicable almost everywhere.

Added March 22, 2021: Pick a class Final project.

Texts

• Combinatorial Algorithms (by Herbert Wilf and Albert Nijenhuis)

• CC (by Dennis and Dennis)

• Don's masterpiece

• Enumerative and Algebraic Combinatorics (by Dr. Z.)

• Guru Don Knuth's Half-page rendition of Hao Huang's Wondeful proof of the Sensitivity Conjecture

  [See also Hao Huang's original article and Jean-Paul Delahaye's charming April 2021 column (en Francais, appared in Pour La Science, April 2021).]

• The Greene-Nijenhuis-Wilf seminal proof of the Hook-Length Formula

Optional (but Highly recommended) Getting Started Homework

For more details, see this 2002 masterpiece.

How to submit homework

• Every class has a homework assignment. Both Mondays and Thursdays' are due 10:00pm Sunday of the following week.

  It should be sent to the email address

  ShaloshBEkhad at gmail dot com

  Subject: HomeWork#X

  and then attach a .txt file(s) called

  hwXYourFirstNameYourLastName.txt

  where X is the number of the assignment

  Except for the first assignment, you should have two attached .txt files.

  For example, when Yukun Yao submits homework assignments 2 and 3, he should email ShaloshBEkhad at gmail dot com, with

  Subject: HomeWork#2#3

  and attach the text files (the source code plus human comments (such lines must start with #)

  hw2YukunYao.txt and hw3YukunYao.txt

• The very first line of the .txt files should have

  #Please do not post homework
  or
  #OK to post homework

  Followed by
  #Your Name, Date, Assignment X

Lecture 1 ( Thurs., Jan. 21, 2021)

Programs done on Thurs., Jan. 21, 2021

• LC(p): Inputs a RATIONAL number p and outputs a pseudo-random number5A 1 with probability p and 2 with probability 1-p

• IsDer(pi): inputs a permutation of {1,...,n} pi (n=nops(pi)) and outputs true iff it is a derangement

  RandDer(n): Generates a random derangement of {1,...,n}, using the NAIVE approach suggested by5A Alon Itai in his not entirely-raving Math review of the Nijenhuius-Wilf classic

Homework for Thurs., Jan. 21, 2021, class (due Sunday Jan. 24, 9:00pm)

Subject: hw#1

and an attachment

hw1FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are exempt from this] Read and do all the examples, plus make up similar ones, in the first 30 pages of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. Read and understand the introduction and Chapter 1 of the Nijenhuis-Wilf masterpiece Do not worry about the details.

3. Write a procedure

   FP(pi)

   that inputs a permutation pi of {1,...n}, (where n=nops(pi)) and outputs an integer between 0 and n indicating the number of fixed points, i.e. the number of places i such that pi[i]=i. Note that if pi is a derangement, then FP(pi)=0.

4. Modify RandDer(n) to write a procedure

   RandAlmostDer(n,k)

   that inputs a positive integer n, another positive integer k, (between 0 and n) and outputs a random permutation whose number of fixed points is <=k. Note that RandAlmostder(n,0) does the same thing as RandDer(n)

5. Write a procedure

   EstimateAveFP(n,K)

   thas inputs a positive integer n, and a large positive integer K, picks randompermutations of {1,...,n} (using randperm(n) in the combinat package of Maple) and outputs the average number of fixed points. By taking K fairly large, say K=10000, and various n, can you guess the exact value?

6. [Optional challenge] Can you find the exact value of the average? Can you prove it mathematically?

7. Write a procedure

   EstimateMomFP(n,r,K)

   thas inputs a positive integer n, another positive integer, r, and a large positive integer K, picks randompermutations of {1,...,n} (using randperm(n) in the combinat package of Maple) and outputs the average number of FP(pi)^r. Note that EstimateMomFP(n,1,K) does the same thing as EstimateAve(n,K). By taking K fairly large, say K=10000, r=2, and various n, can you guess the exact value of the average of FF(pi)^2?

8. [Bigger Optional challenge] Can you find the exact value of the average of random variable FP(pi)² over all permutations of length n? Can you prove it mathematically?

Added Jan. 25, 2021: The students' nice solutions can be found in this directory

Lecture 2 ( Monday., Jan. 25, 2021)

Programs done on Monday, Jan. 25, 2021

• FP(pi): Inputs a permutation pi of {1,...n}, (where n=nops(pi)) and outputs an integer between 0 and n indicating the number of fixed points, i.e. the number of places i such that pi[i]=i. Note that if pi is a derangement, then FP(pi)=0.

• MomFP(n,k): Inputs a positive integer n and outputs the EXACT (not approximate) value of the average of the k-th power of FP(pi) over all permutations MomFP:=proc(n,k) local S,pi:S:=permute(n):add(FP(pi)^k, pi in S)/nops(S):end:

• MyPS(S): Inputs a set S and outputs the powerset of S, i.e. the set of all subsets of S

• Box(L): Inputs a list L (where k=nops(L)) of non-negative integers L outputs the LIST of all LISTS [a1,a2,..., ak] in LEX ORDER such that ai is in {0,1,.., L[i]) In particular the n-dim UNIT cube would be Box([1$n]);

Homework for Monday, Jan. 25, 2021, class (due Sunday, Jan. 31, 9:00pm)

Subject: hw#2

and an attachment

hw2FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are exempt from this] Read and do all the examples, plus make up similar ones, in pages 30 to 60 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. Write a procedure SetToVec(S,n) that inputs a subset S of {1,...,n} and outputs the 0-1 vector of length n such that v[i]=1 iff i belongs to S. Be sure to check that the input is legal (i.e. that S is indeed a set, and that n is a non-neg. integer and that S is indeed a subset of {1,...,n}.

3. [Clarified thanks to Blair Seidler] Write a procedure VecToSet(v) that inputs a 0-1 vector v and outputs the subset of {1,...,n} (where n=nops(v)) such that v[i]=1 iff i belongs to S.

4. [Corrected and clarified thanks to Blair Seidler] Write a procedure

   CheckBij(n)

   that checks that SetToVec(VecToSet(v),n)=v is always true for each member of Box([1$n]) and VecToSet(SetToVec(S,n))=S for each member of MyPS({seq(i,i=1..n)}) .

5. [A little bit challenging] Write a procedure NextInLine(L,v) that inputs a list L and a member v of the list of lists (dictionary) and returns the vector right after it (in dictionary (lex.) order) without actually constructing the (usually) very large set Box(L)

Added Feb.1, 2021: The students' nice solutions can be found in this directory

Lecture 3 (Thursday, Jan. 28, 2021)

Programs done on Thurs., Jan. 28, 2021

• [From C2.txt] Box(L): Inputs a list L (where k=nops(L)) of non-negative integers L outputs the LIST of all LISTS [a1,a2,..., ak] in LEX ORDER such that ai is in {0,1,.., L[i]) In particular the n-dim UNIT cube would be Box([1$n]);

• CAT(L1,L2): joining two lists in order

• PreP(a,L): Given a list L of lists, outputs the list where sticks a to the beginning of each of them

• App(L,a): Given a list L of lists, outputs the list where sticks a to the end of each of them

• UC(n): inputs a non-neg. integer n, and outputs the n-dim unit cube [0,1]^n AS A LIST OF 0-1 vectors in Lex-order (same as Box([1$n])

• NEX(w): Inputs a 0-1 vector w (of length n=nops(w)) outputs the vector right after it in lex order or returns FAIL, using recursion

• NEXr(w): Same as NEX(w), but with "option remember" (just for trying)

• REV(L): The reverse of the list L

• UCG(n): inputs a non-neg. integer n, and outputs the n-dim unit cube [0,1]^n but USING THE GRAY-CODE WHERE ONLY ONE BIT CHANGES AT A TIME

• [Finished after class] NEXG(w): inputs a word in {0,1}^n (n=nops(w)) and outputs the NEXT one in the the Gray Code given by UCG(n), using recursion (with its companion procedure PREG(w)

• PREG(w): inputs a word in {0,1}^n (n=nops(w)) and outputs the PREVIOUS one in the the Gray Code given by UCG(n). (it is needed for NEXG(w) (see above), and is also of interest on its own right.

• [Added after class] RBW(n): A random binary word in {0,1} of length n

Homework for Thurs., Jan. 28, 2021, class (due Sunday, Jan. 31, 9:00pm)

Subject: hw#3

and an attachment

hw3FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Also have your name at the first line #Homework by ...

1. Carefully read the code for the recursive procedure NEXG(w) in C3.txt , (with its companion procedure PREG(w)) and write a procedure

   NewUCG(n)

   that has the same input and output as UCG(n), but instead starts with the vector [0$n] and keeps applying NEXG(w), always appending the new guy to the list. Check that UCG(n)=NewUCG(n) are the same for n from 1 to 14.

2. [A little challenging]

   Generalize UCG(n) to write a procedure

   BoxG(L)

   that inputs a list of positive integers and outputs a list whose members are the same as Box(L), but in such an order that when you go from one member to the next, it only changes in one place

   What is

   BoxG([2,2,2])?

3. Write procedures

   Tomorrow(Date), Yesterday(Date)

   that inputs four-tuple

   Date=[DayOfTheMonth , Month , Year, DayOfTheWeek ]

   and outputs the dates of the next day, and previous day, respectively.

   For example

   Tomorrow([28,1,2021,5]), Yesterday([28,1,2021,5])

   should output [29,1,2021,6], [27,1,2021,4] respectively

   [Hint: Feb. has 28 days except in leap years. A leap year is a multiple of 4 with the exception that a multiple of 100 is not a leap year with the exception² that a multiple of 400 is a leap year.]

4. [Optional challenge] Can you write a version of NEXG(w), call it MyNEXG(w) that does not use recursion? (i.e. the Gray analog of the last problem from hw2)

5. [Optional, I don't know the answer] When you try NEXG(w) on a 0-1 vector of length <=3261, you get a very fast answer

   w:=RBW(3261): NEXG(w):

   But when I did

   w:=RBW(3262): NEXG(w):

   I got an error Maple, exceeding the "stack" length that handles recursion in Maple. Is there a way to change it?

   Added Feb.1, 2021: The students' nice solutions can be found in this directory

   ---

   Lecture 4 (Monday, Feb. 1 2021)

   Programs done on Monday, Feb. 1, 2021

   C4.txt , Contains procedures
   • Snk(n,k): Inputs NON-NEG. integer n and an integer k and OUTPUTS THE SET OF k-element subsets of {1,...,n} FOR EXAMPLE Snk(3,2) should be {{1,2},{1,3},{2,3}}

   • NuSnk(n,k): Inputs NON-NEG. integer n and an integer k and OUTPUTS THE NUMBER OF k-element subsets of {1,...,n} FOR EXAMPLE NuSnk(3,2) should be 3

   • LD(L): Inputs a list of positive integers L (of n:=nops(L) members) outputs an integer i from 1 to n with the prob. of i being proportional to L[i].
     For example LD([1,2,3]) should output 1 with prob. 1/6, output 2 with prob. 1/3, output 3 with prob. 3/6=1/2

   • Rnk(n,k): Inputs NON-NEG. integer n and an integer k and OUTPUTS A (UNIFORMLY AT-RANDOM) k-element subsets of {1,...,n}

     FOR EXAMPLE Rnk(3,2) should output each of {1,2},{1,3},{2,3} with prob. 1/3

   Homework for Monday, Feb. 1, 2021, class (due Sunday, Feb. 7, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#4

   and an attachment

   hw4FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Prove that NuSnk(n,k)=n!/(k!*(n-k)!). You can do it by hand, but you are welcome to use Maple to verify that G(n,k):=n!/(k!*(n-k)!) satisfies the equation

      G(n,k)=G(n-1,k)+G(n-1,k-1)

   2. Write a procedure

      RnkFast(n,k) by replacing the line

      LD([NuSnk(n-1,k), NuSnk(n-1,k-1)])

      By

      LD([n-k,k])

      First explain why it is valid, and then find out, for fairly large n and k (say n=5000, k=2000) whether it is indeed faster. Why?

   3. (i) Write a procedure

      EstimateAveMax(n,k,K)

      that uses Rnk(n,k) (or if you prefer, your RnkFast(n,k)) K times, and estimates the average of the quantity (max(S)) over all k-element subsets of {1,...,n}. Experiment it with various n and k, and K=1000.

      (ii) [Optional human challenge] Can you find the EXACT value of that average as an expression in n and k?

   4. (i) Write a procedure

      EstimateAveSum(n,k,K)

      that uses Rnk(n,k) (or if you prefer, your RnkFast(n,k)) K times, and estimates the average of the quantity sum(S) over all k-element subsets of {1,...,n}. Experiment it with various n and k, and K=1000.

      (ii) [Optional human challenge] Can you find the EXACT value of that average as an expression in n and k?

   5. As you know, k-element subsets of {1,...,n} are in one-to-one correspondence with n-letters words in the alphabet {0,1} with exactly k ones and n-k zeroes. Adapt Snk(n,k), NuSnk(n,k), and Rnk(n,k) to write procedure

      Wnk(a,b), NuWnk(a,b), RWnk(a,b)

      that input non-negative integers a,b, and outputs, respectively, the set of all words in {1,2} with a 1s, b 2s, their number, and a random such word.

   6. Write a procedure

      W3nk(a,b,c), NuW3nk(a,b,c), RW3nk(a,b,c)

      that input non-negative integers a,b, c and outputs, respectively, the set of all words in {1,2,3} with a 1s, b 2s, c 3s, their number, and a random such word.

   7. [Optional challenge] Write a procedure

      WORDS(L), NuWORDS(L), RandWORD(L)

      that inputs a list L, of length k, say, (i.e. nops(L)=k) of non-negative numbers, and outputs, respectively, the of all words in the alphabet {1,2,...k} with exactly L[1] 1s, L[2] 2s, ..., L[k] k-s, their number, and a random such word.

   ---

   Lecture 5 (Thurs., Feb. 4, 2021)

   Programs done on Thurs., Feb. 4, 2021

   C5.txt , Contains procedures
   • Redu(L): inputs a list L of numbers and outputs The multi-set permutation of {1, ...,nops({op(L)}) where n is the number of number of distinct members of L and the smallest number in {op(L)} replaced by 1, the second smallest by 2, etc. For example
     Redu([evalf(Pi),evalf(Pi),evalf(exp(1)),evalf(exp(1))]
     should return [2,2,1,1]

   • Expa(pi,S): inputs a permutation pi of 1,..., nops(pi) and a sorted list of distinct numbers S, replaces 1 by the smallest member of S, etc. For example
     Expa([2,1,3],[11,13,15])= [13,11,15]

   • PermuA(n): inputs a non-neg. integer n and outputs the list of all n! permutations of {1,...,n} in lex-order (same as combinat[permute](n) )

   • [completed/corrected after class]
     PermuI(n): the list of all permutations of {1, ...,n} using insertion

   Homework for Thurs., Feb. 4, 2021, class (due Sunday, Feb. 7, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#5

   and an attachment

   hw5FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Read the description of the Johnson-Trotter algorithm here (by Dennis and Dennis) and implement it by writing a procedure

      PermuG(n)

      that inputs a non-negative integer n and outputs a list of all permutations of {1,...,n} such that when you move along the list the next permutation is an adjacent transposition (swapping neighboring entries).

      [Hint, it is a relatively minor tweak of PermuI(n), but the sliding of "n" changes direction at reach pass]

   2. [A little bit challenging] Write procedures

      NextPG(pi), PrevPG(pi)

      That inputs a permutation pi of {1, ...,n} for some n, and outputs the ones that come right after (and right before it, respectively) in the above PermuG(n), but of course, without actually constructing this super-exponentially large set.

      Run

      pi:=randperm(100): NextPG(pi): PrevPG(pi), evalb(NextPG(PrevPG(pi))=pi),evalb(PrevPG(NextPG(pi))=pi)

      For several random permutations

   3. Write procedures

      MyRandPermA(n), MyRandPermI(n)

      that input a non-neg. integer n and outputs a random permutation of {1,...,n} (uniformly at random) using
      (i) The pre-pending paradigm, inspired by PermuA(n)
      (ii) The insertion paradigm, inspired by PermuI(n)

      compare the timing of combinat[randperm](n), and your MyRandPermA(n), MyRandPermI(n), for n=1000000. How do the timings compare?

   4. A permutation π of {1,...,n} contains the pattern 123 if there exists a triple 1 ≤ i1 < i2 < i3 ≤ n
      such that
      π[i1] < π[i2] < π[i3].

      Write a procedure

      NoABC(n)

      That inputs a positive integer n and outputs the set of permutations AVOIDING the pattern 123.

      Find

      [seq(nops(NoABC(n)),n=1..8)]

      Is it in the OEIS? What is its A number?

   Added Feb.8, 2021: The students' nice solutions can be found in this directory

   ---

   Lecture 6 (Monday, Feb. 8, 2021)

   Programs done on Monday, Feb. 8, 2021

   C6.txt , Contains procedures

   • [From C4.txt] LD(L): Inputs a list of positive integers L (of n:=nops(L) members) outputs an integer i from 1 to n with the prob. of i being proportional to L[i] For example LD([1,2,3]) should output 1 with prob. 1/6 output 2 with prob. 1/3 output 3 with prob. 3/6=1/2

   • Walks2D(A,pt): Inputs a list A of `atomic' steps A in the form [a,b] (with a,b non-neg. and a+b>0) and a final location (final score in game, e.g. [31,9]). OUTPUTS the SET of all WALKS from [0,0] to to pt, described by giving the intermediate location

   • FootBall(): The scoring events of American football ([[0,2],[0,3],[0,6],[0,7],[0,8],[2,0],[3,0],[6,0],[7,0],[8,0]])

   • NuWalks2D(A,pt): Inputs a list A of `atomic' steps A in the form [a,b] (with a,b non-neg. and a+b>0) and a final location (final score in game, e.g. [31,9]). OUTPUTS the NUMBER of all WALKS from [0,0] to to pt, described by giving the intermediate location e.g.:[[0,0],[2,0],[10,0],[10,2],[10,10]]

   • RandWalk2D(A,pt): inputs a list of atomic steps A and a final destination pt, outputs UNIFORMLY at random a walk from [0,0] to pt using the steps in A

   • GWalks2D(A,pt): Inputs a list A of `atomic' steps A in the form [a,b] (with a,b non-neg. and a+b>0) and a final location (final score in game, e.g. [31,9]). OUTPUTS the SET of all GOOD (subdiagonal) WALKS from [0,0] to to pt, described by giving the intermediate location

   Homework for Monday, Feb. 8, 2021, class (due Sunday, Feb. 14, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#6

   and an attachment

   hw6FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Write procedures GNuWalks2D(A,pt), and GRandWalk2D(A,pt), that inputs a list of atomic steps A (in 2 dimensions) and output, respectively, the number of subdiagonal steps using A and ending at pt, and a (uniformly) at random such good walk.

   2. Which of the following sequences are in the OEIS? State their A numbers

      (i) seq(NuWalks2D([[1,0],[0,1]],[i,i]),i=1..20):

      (ii) seq(GNuWalks2D([[1,0],[0,1]],[i,i]),i=1..20):

      (iii)seq(NuWalks2D([[1,0],[0,1],[2,0],[0,2]],[i,i]),i=1..20):

      (iv) seq(GNuWalks2D([[1,0],[0,1],[2,0],[0,2]],[i,i]),i=1..20):

      (v) seq(NuWalks2D([[1,0],[0,1],[2,0],[0,2],[3,0],[0,3]],[i,i]),i=1..20):

      (vi) seq(GNuWalks2D([[1,0],[0,1],[2,0],[0,2],[3,0],[0,3]],[i,i]),i=1..20):

      (vii) seq(NuWalks2D([[1,0],[0,1],[1,1]],[i,i]),i=1..20):

      (viii) seq(GNuWalks2D([[1,0],[0,1],[1,1]],[i,i]),i=1..20):

      (ix) seq(NuWalks2D(FootBall(),[i,i]),i=1..20):

      (x) seq(GNuWalks2D(FootBall(),[i,i]),i=1..20):

   3. (i)Using NuWalks2D and GNewWalks2D (that you wrote), conjecture an explicit expression for the probability that in a soccer game that ended with a tie [n,n], the visiting team was Never (strictly) leading.

      (ii) [Optional human challenge] Prove your conjecture (it is OK to "peak" at the internet or books)

   4. [I don't know the answer] Estimate the analogous probability for an American football game. Try to conjecture a form for the asymptotics of that probability. Is it like 1/n^alpha for some alpha?

   5. [A little big challenging] Generalize to k-dimensional NuWalks2D(A,pt), GNuWalks2D(A,pt) to write procedures

      NuWalkskD(A,pt) and GNuWalkskD(A,pt) and

      (let k=nops(pt), and assume that all the members of A are lists of length k)

      What are the OEIS A-numbers (if they exist) of

      (i) seq(NuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..10):

      (ii) seq(GNuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..10):

      (iii) seq(NuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..10):

      (iv) seq(GNuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..10):

   Added Feb.15, 2021: The students' nice solutions can be found in this directory

   ---

   ---

   Lecture 7 (Thurs., Feb. 11, 2021)

   Programs done on Thurs., Feb. 11, 2021

   C7.txt , Contains procedures
   • SPnk(n,k): Inputs pos. integers k and n (1 ≤ k ≤ n) and outputs the SET of set-partitions of {1,...,n} with exactly k parts

   • SPn(n): The set of all set-partitions of {1,...,n} (same as combinat[setpartition](n))

   • NuSPnk(n,k): The number of set-partitions of {1,...,n} into exactly k parts (aka Stirling numbers of the second kind)

   • NuSPn(n): The number of set-partitions of {1,...,n} (aka the Bell numbers)

   • (from C4.txt): LD(L): Inputs a list of positive integers L (of n:=nops(L) members) outputs an integer i from 1 to n with the prob. of i being proportional to L[i]

   • RandSPnk(n,k): a random set partition of {1,..,n} with k parts

   Homework for Thurs., Feb. 11, 2021, class (due Sunday, Feb. 14, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#7

   and an attachment

   hw7FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Write a procedure

      NiceValentine()

      that outputs a nice valentine that contains the text "I love Experimental Mathematics". The Maple code should he in hw7FirstNameLastName.txt, but the output (as a .jpeg file) should be submitted as an attachment. You should use the Maple plot package. If possible use plot3d.

   2. Write a procedure

      DrawMandelbrot(R,K)

      that plots the Mandelbrot set by picking all those complex c (of the form x+I*y, with x,y in [-4,4] with resolution 1/R, and deciding whether to accept it if iterating z goes to z^2+c (starting at z=0) after K iterations stay bounded. Also send the output as .jpeg file, for R as large as possible.

   3. By using LD(L) and RandSPnk(n,k) write a procedure

      RandSPn(n)

      that inputs a positive integer n and outputs a (uniformly) at random set partition of {1,...,n}

   4. (i) Write a procedure

      NuAdjacentMates(SP,n)

      that inputs a set partition, SP, of {1, ...n}, and outputs the number of i between 1 and n such that i and i+1 are part-mates

      (ii) Write a procedure

      EstimateAvAdjacentMates(n,K)

      that uses the above procedure, and your RandSPn(n), K times, to estimate the average of the number of adjacent mates in a random set partition of {1,...n}. What did you get for

      EstimateAvAdjacentMates(100,1000)?

      (run it several times to make sure that they are close)

      (iii) [Optional challenge] Find an explicit formula (or efficient algorithm) to find the EXACT value, of that average, for a general n.

   Added Feb.15, 2021: The students' nice solutions (including GORGEORUS Valentines and Mandelbrojt sets) can be found in this directory

   ---

   Lecture 8 (Monday, Feb. 15, 2021)

   Programs done on Monday Feb. 15, 2021

   C8.txt , In addition to procedures from Lecture 7 and Lecture 4 (see `Help7();' and `Help4();' Contains procedures
   • RandSPn(n): (from Yuxuan Yang's hw7): A randon set-partition of {1, ..,n}

   • NuSPnF(n): The number of set-partitions of an n-element set (aka Bell numbers) using the NEW approach

   • RandSPnF(n): A random set-partition of {1, ...,n} using the NEW approach

   • BellSeq(n): The first n bell numbers using the exponential generating function

   Homework for Monday, Feb. 15, 2021, class (due Sunday, Feb. 21, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#8

   and an attachment

   hw8FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Write a procedure

      SPnF(n)

      that inputs a non-neg. integer n and outputs the set of set-partitions of {1,..,n} using the NEW approach (the one used in NuSPnF(n) and RandSPn(n)

   2. Read and understand the section on exponential generating functions in Dr. Z.'s masterpiece

   3. Convince yourself that the exponential generating function for the sequence

      a(n)=Number of CONNECTED labeled graphs on n vertices is

      is

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

      Use the taylor command in Maple to find the first 30 terms. Is it in the OEIS?

   4. The number of ALL labeled graphs on n vertices is 2^(n*(n-1)/2) (used above). The ordinary generating function according to the weight a^("number of edges") is obviously (1+a)^(n*(n-1)/2) [why?]. Let

      P_n(a)

      be the polynomial in a (of degree n*(n-1)/2) whose coefficient of a^k is the number of CONNECTED labeled graphs on exactly k edges.

      Using a "weighted generalization" of the exponential formula, convince yourself that

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

   5. Using the above, and taylor, (and coeff, first applied to xⁿ, (multiplied by n!, of course), and then applied to a^k, write a procedure

      NuCG(n,k)

      that inputs positive integers n and k, and outputs the number of labeled connected graphs with n vertices and k edges.

      (i) What is seq(NuCG(n,n-1),n=1..20)? What is its OEIS A-number (if it exists)

      (ii) For which r=0,1,2,3,... are the sequences

      seq(NuCG(n,n+r),n=1..20)? in the OEIS? What are their A numbers? What is the smallest r that is NOT in the OEIS.

   6. [Optional] Submit it to the OEIS.

   Added Feb.22, 2021: The students' nice solutions are in this directory

   ---

   Lecture 9 (Thurs., Feb. 18, 2021)

   Programs done on Thurs. Feb. 18, 2021

   C9.txt ,
   • RRV(n,K): A random random variable on {1, ... n} where the values are from 0 to K (uniformly)

   • Ave(X): inputs a RV X (given as list of values where the value of Mr. or Ms. i is L[i]) outputs the average (alias expectation, alias mean)

   • SA(X,K): inputs a discrete r.v. X (given as a list of numbers) and a pos. integer K outputs a list of length K whose (i) first entry is the average (ii) second entry variance The remaining entries are the scaled-third moment (about the mean) aka skewness scaled fourth-moment (about the mean) aka kurtosis and so on up to the K-th moment

   • Pgf(X,x): inputs a RV X (given as list of values where the value of Mr. or Ms. i is L[i]) outputs the prob. generating function of X using the variable

   • [To be continued as homework] SAc(f,x,K): The SA(X,x,K) of the rv X such whose Pgf is f of x

   Homework for Thurs., Feb. 18, 2021, class (due Sunday, Feb. 21, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#9

   and an attachment

   hw9FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Convince yourself that if f(x) is the pgf of a random variable X, then μ=f'(1), Var(X)= (x d/dx)^2 (f(x)/x^μ)|x=1, and more generally the kth moment about the mean is

      (x d/dx)^k (f(x)/x^μ)|x=1

      Using this, finish writing procedure SAc(f,x,K), that we barely started in class.

      Make sure that

      SAc(Pgf(X,x),x,8)=SA(X,8)

      for several X obtained by using RRV(100,1000) (say)

   2. We will soon see (and you proably already know that) that the pdf of tossing a fair coin n times is ((1+x)/2)^n.

      Using the above-mentioned SAc that you wrote above, and leaving n symbolic, find closed-form expressions for the average, variance, and third through the 10th scaled moments. By using Maple's limit command, find the limits. Can you conjecture an explicit expression for the k-th scaled moment as an expression in k?

   3. [Corrected, Feb. 20, 2021, thanks to Yuxuan Yang]

      Using procedure RandSPn(n), with n=100,200,300 from C8.txt , 10000 times, and SA(X), estimate the average and variance of the random variable "number of parts" of a random set-partition of {1,...,n}. See how close it is to the exact values

      μ:=Sum(k*Snk(n,k),k=0..n)/Bell(n)

      sig2:=Sum((k-μ)²*NuSPnk(n,k),k=0..n)/Bell(n)

   Added Feb. 22, 2021: The students' nice solutions are in this directory

   ---

   Lecture 10 (Monday, Feb. 22, 2021)

   Programs done on Monday Feb. 22, 2021

   C10.txt ,
   • ]Taken from Blair Seidler's homework (who adapted a previous code from Dr. Z.)]
     SAc(f,x,K): inputs a probability (or enumeration) prob. gen. function assumed to be a polynmial in x, and a positive integer K, outputs the list consisting, in that order of the expectation, variance, and the SCALED i-th moment from 3 to K.

   • [from a previous class]
     LD(L): Inputs a list of positive integers L (of n:=nops(L) members) outputs an integer i from 1 to n with the prob. of i being proportional to L[i] For example LD([1,2,3]) should output 1 with prob. 1/6, output 2 with prob. 1/3, output 3 with prob. 3/6=1/2

   • [Corrected after class, following a suggestion of Blair Sidler]
     PlotDist(f,x,K): Inputs a prob. generating function of some r.v. X outputs a graph of its SCALED distribution A graph of the pdf of (X-mu)/sig. It draws it from -K*sig to K*sig

   • OneTrial(p,n): The outcome of ONE trial of tossing a coin n times where Pr(Head)=p. Returns the number of Heads

   • ManyTrials(p,n,K,x): the EMPIRICAL PGF in the variable x, of repeating K times OneTrial(p,n)

   Homework for Monday, Feb. 22, 2021, class (due Sunday,Feb. 28 , 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#10

   and an attachment

   hw10FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Given a permutation of {1,...,n}
      • the number of inversion, denoted by inv(π), is the number of pairs 1 ≤ i < j ≤ n such π[i] > π[j]
        [For example inv(631425)=8]

      • The number of descents, denoted by des(π), is the number of places i, such that π[i] > π[i+1] [For example inv(631425)=3]

        The major index, denoted by maj(π), is the SUM of the places i, such that π[i] > π[i+1] [For example maj(631425)=1+2+4=7]

      Write procedures

      ExactGFinv(n,x) ,ExactGFmaj(n,x) , ExactGFdes(n,x)

      that inputs a positive integer n and a variable name n, and outputs the generating function whose coefficient of x^k is the exact number of permutations with inv=k, maj=k, des=k, respectively.

      Try to conjecture (or derive mathematically) closed form or efficient recurrences for these generating functions that will enable you to easily compute them for say n=100. [Warning: I don't think that the g.f. according to des has a nice closed form, but it has a recurrence]

   2. By using randperm(n), write procedures

      EstGFinv(n,x,K) ,EstGFmaj(n,x,K) , EstGFdes(n,x,K)

      that samples K random permutations and finds the empirical prob. gen. function. Compare plotDist and SAc for up to the 8th moment, with n=100, and K=2000.

   3. Let P_n(t) be the weight-enumerator of the r.v. "number of parts" defined over set partitions of {1, ...,n}. Using geneartingfunctionology, convince yourself that

      Sum(P_n(t) xⁿ/n!,n=0..infinity)= exp(t*(exp(x)-1) )

      Using Maple's command "taylor", write a procedure

      PnSeq(N,t)

      That inputs a positive integer N and outputs the first N terms of P_n(t)

      (i) Using SAc, do they seem to be asymptotically normal?

      (ii) [I don't know the answer] Does the average number of parts and the variance divided by n tend to some constants?\

   4. Using the procedure to generate a random set partition of {1,...,n} from a previous class, write estimated versions and see how close they get to the exact values, for say, n=100.

   Added March 1, 2021: The students' nice solutions are in this directory

   ---

   Lecture 11 (Thurs., Feb. 25, 2021)

   Programs done on Thurs. Feb. 25, 2021

   C11.txt ,
   • PnClass(n): THE SET of integer partitions of n, using the approach suggested by the students

   • Pnk(n,k): The LIST of integer partitions of n with largest part k

   • Pn(n): The list of integer partitions of n in rev. lex. order

   • pnk(n,k): the NUMBER of integer partitions of n with largest part k

   • pn(n): the NUMBER of integer partitions of n

   • pnSeq(N): the first N+1 terms of sequence A41, starting at n=0, using pn(n) above

   • pnSeqGF(N):the first N+1 terms of sequence A41, starting at n=0, usinn Euler's famous generating function

     Sum(p(n)qⁿ, n=0..infinity)=Product(1/(1-qⁱ),i=1..infinity):

   Homework for Thurs., Feb. 25, 2021, class (due Sunday, Feb. 28 , 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#11

   and an attachment

   hw11FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Using the same type as recursion as in Pnk(n,k) and Pn(n), and using the Wilf methodology (using pnk(n,k), write procedures

      RandPnk(n,k), and RandPn(n)

      that, respectively, generate, uniformly at random, a partition of n with largest part k, and a partition of n

   2. Write a procedure

      EstStatAnalOfLargestPart(n,K,N)

      that inputs a positive integer n and a fairly large K, and (using previous functions), estimate the expectation, variance, and the 3rd- through K-th scaled moments, of the r.v. "number of parts" when running over the sample space of (integer) partitions of n.

      Run

      EstStatAnalOfLargestPart(100,10000,6)

      several times and see of they are not too far from each other (especially the expectation and variance)

      Then run

      EstStatAnalOfLargestPart(200,10000,6)

      several times, and see whether the 3rd, and 4th scaled moments are close to the previous ones for n=100.

   3. [Made more explicit, Feb. 28, 2021, 9:55am]

      Let P_n(t) be the weight-enumeator of the set of integer partitions of n, according to the r.v. "number of parts"

      For example, Par(4)={[4],[3,1],[2,2],[2,1,1],[1,1,1,1]}, so the naive count of Par(4) (what we call Pn(4)), i.e. pn(4), is 5.

      The weight-enumerator, according to the weight "number of parts" is

      P₄(t)=t^nops([4])+ t^nops([3,1])+ t^(nops([2,2]))+t^nops([2,1,1])+ t^nops([1,1,1,1]) =t^1+t^2+t^2+t^3+t^4=t^4+t^3+2t^2+t

      So [seq(P_n(t),n=0,1,2,3...] is an infinite sequence of POLYNOMIALS, in t, such that P_n(1)=pn(n)

      Convince yourself that the generating function, with respect to the variable q, viewing t as a parameter is:

      Sum(P_n(t) qⁿ, n=0..infinity)=Product(1/(1-tqⁱ),i=1..infinity):

   4. Using the above, adapt procedure pnSeqGF(N), to write prodedure

      pnSeqGFt(N,t)

      that inputs N, and a variable t, and outputs the first N+1 (starting at n=0) of the sequence {P_n(t)} mentioned in the previous problem.

      For example the output of pnSeqGFt(4,t) should be

      [1,t,t^2+t,t^3+t^2+t,t^4+t^3+2t^2+t]

      Find the EXACT average, expectation, and the 3rd through 6th scaled moments of the r.v. "number of parts" for n=100, n=200. How do they compare with the estimate?

   5. [Optional, I don't know the answers. You are welcome to search the literature] Is it true that the expectation of the r.v. "number of parts" is roughly a constant times n? If yes what is that constant? Similar for the variance. Do the scaled moments converge to constants? What are they?

   6. [Optional, I don't know the answer, suggested by Robert Dougherty-Bliss] analyze the running time of PnClass(n) vs. Pn(n), and explain why the former seems to be slower. [Of course, for larger n it is a moot question, since the set grow exponentially (in sqrt(n))]

   Added March 1, 2021: The students' nice solutions are in this directory

   ---

   Lecture 12 (Monday, March 1, 2021)

   Programs done on Monday, March 1, 2021

   C12.txt ,

   Contains procedures:

   • Ferr(L): The Ferrers graph of the partition L

   • Conj(L):The conjugate partition of the partition L

   • TSprintf:(): Nice print (found by Victoria Chayes)

   • RandPnk(n,k): a uniformly at random INTEGER partition of n with largest part k (taken From Yuxuan Yang's homework)

   • RandPn(n): a uniformly at random INTEGER partition of n (taken From Yuxuan Yang's homework)

   • pnSeqGFt(N,t): the first N+1 weight-enumerators according to the r.v. "number of parts" (or equivalently, "largest part"), starting at n=0

   Homework for Monday March 1, 2021, class (due Sunday, March 7, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#12

   and an attachment

   hw12FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Generalize procedures Pnk(n,k), Pn(n), RandPnk(n,k), RandPn(n), pnk(n,k), and pn(n), to write (respectively) procedures

      PnkC(n,k,S,m), PnC(n,S,m), RandPnkC(n,k,S,m), RandPnC(n,S,m), pnkC(n,k,S,m), and pnC(n,S,m) that input in addition of n (and sometimes k) also a set S that is a subset of {0,1,..,m-1} and a positive integer m, and outputs respectively

      • PnkC(n,k,S,m): The set of partitions of n with largest part k where all parts are congruent to a member of S mod m.
      • PnC(n,S,m): The set of partitions of n where all parts are congruent to a member of S mod m

      • RandPnkC(n,k,S,m): A random partition of n with largest part k where all parts are congruent to a member of S mod m.

      • RandPnC(n,k,S,m): A random partition of n where all parts are congruent to a member of S mod m

      • pnkC(n,k,S,m):The NUMBER of partitions of n with largest part k where all parts are congruent to a member of S mod m.

      • pnC(n,S,m):The NUMBER of partitions of n where all parts are congruent to a member of S mod m.

      Note that if S={0} and m=1, you get back the original functions.

   2. Generalize procedures Pnk(n,k), Pn(n), RandPnk(n,k), RandPn(n), pnk(n,k), and pn(n), to write (respectively) procedures

      PnkD(n,k,DI), PnD(n,DI), RandPnkD(n,k,DI), RandPnD(n,S,DI), pnkC(n,k,DI), and pnD(n,DI) that input in addition of n (and sometimes k) also a set DI that is a set of non-negative integers and outputs respectively

      • PnkD(n,k,DI): The set of partitions of n with largest part k where the difference of two consecutive parts is NOT in DI

      • PnD(n,DI): The set of partitions of n where the difference of two consecutive parts is NOT in DI

      • RandPnD(n,k,DI): A random partition of n with largest part k where the difference of two consecutive parts is NOT in DI

      • RandPnD(n,k,DI): A random partition of n where the difference of two consecutive parts is NOT in DI

      • pnkD(n,k,DI):The NUMBER of partitions of n where the difference of two consecutive parts is NOT in DI

      • pnD(n,DI):The NUMBER of partitions of n where the difference of two consecutive parts is NOT in DI

      Note that if DI={} you get back the original functions.

   3. What OEIS A numbers are
      • [seq(pnC(n,{1},2),n=1..30)]

      • [seq(pnC(n,{1,4},5),n=1..30)]

      • [seq(pnD(n,{0}),n=1..30)]

      • [seq(pnD(n,{0,1}),n=1..30)]

   Added March 8, 2021: The students' nice solutions are in this directory

   ---

   Lecture 13 (March 4, 2021)

   Programs done on Thurs., March 4, 2021

   C13.txt ,

   Contains procedures:

   • LE(N,q): The first N+1 terms of the infinite product Prod(1-q^i,i=1..infinity), done directly

   • LEc(N,q): The first N+1 terms of the infinite product Prod(1-q^i,i=1..infinity), via the conjecture done in class, conjectured before by Leonhard Euler, and proved by him (with an ugly proof) 25 yeasrs later

   • SeqFn(N): The first N+1 terms of the Fibonacci sequence, via the generating function

     SeqFnF(N): the first N+1 terms of the Fibonacci numbers using the RECURRENCE

   Homework for Thurs, March 4, 2021, class (due Sunday, March 7, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#13

   and an attachment

   hw13FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Convince yourself that Euler's Pentagonal theorem

      Prod(1-q^i,i=1..infinity)= 1+ Sum((-1)^j *(q^((3*j-1)*j)/2+q^((3*j+1)*j)/2),j=1..infinity)

      implies the recurrence

      p(n)=-Sum((-1)^j* p(n-((3*j-1)*j)/2),j=1..infintiy) - Sum((-1)^j* p(n-((3*j+1)*j)/2),j=1..infinity)):

      where "infinity" is replaced by the largest j that make the argument of p non-negative.

      Then write procedure, pnE(n), that implements it. Then write, pnSeqE(N), that has the same output as pnSeq(N) and pnSeqGF(N), but hoplefully is faster. Compare the running times for N=1000, N=2000 (and possibly higher values)

   2. Look up the entry "Pentagonal Number Theorem" in wikipedia (or any other source), and write a procedure

      Franklin(L)

      that implements Fabian Franklin's beautiful proof of Euler's Pentagonal Theorem.

      It should input a distinct integer partition (i.e. an integer partition with distinct parts), and outputs another one with one or less number of parts. It should return FAIL, if it not applicable.

   3. Using your procedure

      PnD(n,DI)

      From homework 12, with DI={0}, write a procedure

      FranklinOldMaids(n)

      that inputs a non-negative integer n, and outputs the (usually empty, and otherwise a singleton, if you believe Euler) partitions for which Franklin(L) returns FAIL. Can you find a structure to thoese "old maids".

   Added March 8, 2021: The students' nice solutions are in this directory

   ---

   Lecture 14 (Monday, March 8, 2021)

   Programs done on Monday, March 8, 2021

   C14.txt ,

   Contains procedures:

   • F01ab(a,b): The SET of integer partition of (0 to a*b) with largest part <=a and number of parts <=b in other words their Ferrers diagram is included in b by a rectangle

   • Fab(a,b): The SET of integer partition of (0 to a*b) with largest part <=a and number of parts <=b in other words their Ferrers diagram is included in b by a rectangle

   • [From George Spahn, 3/7/2021, Assignment 13]

     pnE(n): The number of (integer) partitions of n using Euler's recurrence

   • pnSeqE(N):The first N terms of the sequence p(n), starting at n=1

   • [From George Spahn, 3/7/2021, Assignment 13]

     Franklin(L): implements Franklin's bijecive proof of Euler's Pentagonal Theorem

   • [From George Spahn, 3/7/2021, Assignment 13]

     FranklinOldMaids(n) inputs a non-negative integer n, and outputs the partitions for which Franklin(L) returns FAIL.

   Homework for Monday March 8, 2021, class (due Sunday, March 14, 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#14

   and an attachment

   hw14FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Search the internet for "Bijecting Euler's Partition Recurrence", find out who were the geniuses who did it and write a procedure

      BZ(L,j)

      that inputs a partition L and an integer j, and outputs a pair [L', j'] where j' has opposite parity than j and

      |L|+(3*j-1)*j/2 =|L'|+(3*j'-1)*j'/2

   2. Write procedures

      Glashier(L), InvGlashier(L)

      that input a partition into odd parts, and a partition into distinct parts, respectively, and perform Glashier's (look it up) famous bijective proof that these are equinumerous.

   3. Implement Sylverster's even better bijection, and its inverse as described in this gem

   4. [Optional Challenge] Implement Rademacher's "monster" exact convergent series for p(n) as found in mathworld.

   5. [Optional challenge] Program both directions of the Bressoud-Zeilberger Bijective Proof of the Rogers-Ramanujan identity (that you found empirically in homework 13) that says that the number of partitions of n into parts that are 1,4 (mod 5) is the same as the number of partitions of n where the difference between consecutive parts is larger than one.

   Added March 15, 2021: The students' nice solutions are in this directory

   ---

   Lecture 15 (Thurs., March 11, 2021)

   Programs done on Thurs., March 11, 2021

   C15.txt ,

   Contains procedures:

   • IsUD(pi): Is the permutation pi an up-down permutation?

   • UD(n): The set of up-down permutations of length n, by complete brute force

     ud(n): The NUMBER OF up-down permutations of length n using the non-linear recurrence

     ud(n)=Sum(i=1..trunc(n/2), binomial(n-1, 2*i-1)*ud(2*i-1)*ud(n-2*i))

   • udPi(n): A (very good approximation) to Pi, that follows from the fact that (you still need to prove) that

     evalf(2*n*ud(n-1)/ud(n))

     converges to Pi, since (as you are going to prove in the homework, and we discovered experimentally in class)

     Sum(ud(i)*x^i/i!,i=0..infinity)= csc(x)+ tan(x)

     and that the closest root of the denominator is Pi/2, hence that is the radius of convergence, and the rest follows from the ratio test from calculus.

   Homework for Thurs. March 11, 2021, class (due Sunday, 3/14 of 2021,(i.e. π Day!), 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#15

   and an attachment

   hw15FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Write a procedure

      UDbetter(n)

      that outputs the same thing a UD(n), but using the ideas behing the enumeration procedure ud(n)

      ( Hint, you are welcome to use the Maple command combinat[choose] )

   2. Read and understand the proof of the Pythagorean Theorem in this masterpiece, and use this method to prove that indeed the egf of ud(n) is sec(x)+tan(x)

   3. Go to the home page of Jesus Guillera and using Digits=10000, compute Pi to 10000 decimal places using the infinite series given at the bottom of the page (that computes 128/Pi^2 (so you need to take the reciprocal, multiply by 128, and take the square-root).

   Added March 15, 2021: The students' nice solutions are in this directory

   ---

   Lecture 16 (Monday, March 22, 2021)

   Programs done on Monday, March 22, 2021

   C16.txt ,

   Contains procedures:

   • PiJG(d): Computing Pi using Jesus Guillera's amazing formula for 128/π² to d decimal digits (it combines ideas of several students)

   • [added after class]
     IsGood1(T): Given a potential Latin trapezoid (in the right-angled format) that you know that its horiz. , vertical and its NW->SE diagonals for the truncated version (where you chopped the last row), returns true iff the new one is also OK

   • LT(n,k): The SET OF REDUCED n by k LATIN TRAPEZOIDS The bottom line is 1,...,n, and each floor above it of length n-1,n-2, .., n-k+1 has all DIFFERENT entries also VERTICALLY all different also A[i][i],A[i+1][i+1], ... are all different

   Homework for Monday March 22, 2021, class (due Sunday, 3/28/2021 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#16

   and an attachment

   hw16FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Extend the method of Robert Dougherty-Bliss to write a procedure

      ComputCons(F, P, n, d)

      that inputs an F, that is a product and/or quotient of expressions of the form (a*n+b)! (e.g. binomial(2*n,n)/10^n), a polynomial P in n, a variable name n, and a positive integer d, and outputs the value of

      Sum(((-1)^n*P(n)*F(n),n=0..infinity)

      to d decimail digits.

      Hint: first find the simplified version of P/subs(n=n-1,P) and call it something.

      Use your procedure to compute the constant

      Sum(((-1)^n*(n^3+1)*k^n/binomial(2*n,n)^10,n=0..infinity)

      for k=1,2,3,...

      and compare it with just using the Maple add command.

   2. Read and understand procedure LT(n,k) finished after class.

      Is seq(nops(LT(i,i)),i=1..7); in the OEIS?

   3. Is seq(nops(LT(i,2)),i=2..7); in the OEIS?

      If it is, what is the A number? What is its meaning in the OEIS?

   4. [10 dollars for the first solver, I don't know the answer] Prove rigorously that the sequence enumerating reduced n by 2 Latin trapezoids is indeed equal to that OEIS sequence
      Added March 29, 2021: George Spahn and Yuxuan Yang each won 10 dollars! See George Spahn's proof and see Yuxuan Yang's proof

   Added March 29, 2021: The students' nice solutions are in this directory

   ---

   Lecture 17 (Thurs., March 25, 2021)

   Programs done on Thurs., March 25, 2021

   C17.txt ,

   Contains procedures:

   • Rseq(r,N): The first N coefficients of q*eta(q)^r, where eta(q)=(1-q)*(1-q^2)*(1-q^3)*... done the "dumb" way. When r=24, it is the famous Ramanujan tau function

   • RseqF(r,N): a Fast version of Rseq(r,N), using Euler's pentagonal numbers theorem.

   • RseqFF(r,N): a Fast version of Rseq(r,N), using Euler's pentagonal numbers theorem and the J.C.P.Miller recurrence

   • RseqFFF(r,N): Yet faser version of Rseq(r,N) using tauF(r,N) [see below]

   • JC(P,x,m,K): inputs a polynomial P in the variable x, a pos. integer m and a pos. integer K, outputs the list of coeffs. of x^n from n=0 to n=K. It uses the J.C.P. Miller (that according to DOn Knuth goes back to L. Euler) rediscovred by Dr. Z. in this gem.

   • [Added after class]
     JC1(P,x,m,K): same input and output as JC(P,x,m,K), for checking purposes. Ironially, it seems to be faster than the "clever" JC, but perhaps Maple is using it? (it definitely did not way back in 1994).

   • [Added after class]
     RseqFF(r,N): a yet Faster version of RseqF(r,N) (see above) using the J.C.P. Miller recurrence and Euler's Pentagonal number theorem

   • [Added after class]
     FZ(r,N): The first place where the coefficient of q^i in q*eta(q)^r is zero looking at the first N coefficeints of q*eta(q)^r. if they are all non-zero, it returns infinity. Lehmer's conjecture is that FZ(24,infinity) is infinity. When we test it, we take N to be as large as we can.
   • [Added March 26, 2021]
     tauF(r,k): directly implementing J.C.Miller's applied to Euler's Pentagonal theorem to compute the coefficeint of q^k in q*eta(q)^r. When r=24, it is the famous Ramanujan τ function.

   Homework for Thurs. March 25, 2021, class (due Sunday, 3/28/2021 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#17

   and an attachment

   hw17FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. [Human homework] Read and unerstand the statement and proof of the recurrence in Dr. Z.'s gem [that apparently goes back to Euler], and make sure that procedure JC(P,x,m,K) does it correctly.

   2. [Optional, I don't know the answer. Reward for a good answer] To my dismay, JC1(P,x,m,K) is even faster for the random examples that I tried. Can you explain? (It definitely was much slower back in 1994. Perhaps Maple is using this algorithm now?)

      Can you find inputs for which JC(P,x,m,K) is much faster than JC1(P,x,m,K)?

   3. Write a procedure

      CheckMordell(N)

      that verifies that τ(p)*τ(q)=τ(pq) for all primes p,q, between 2 and N. Please use RseqFF(24,N), with N as large as your computer would agree to.

   4. Write a procedure

      CheckDeligne(N)

      that outputs the primes between 2 and N such that |&tau[(p)|/2 p^11/2 is as small as possible, followed by its value (that hopefully is less than 2). Who is the lucky prime? What is the value of |τ(p)|/2 p^11/2 for that lucky prime?

      If you make N larger, do you get new champions? Perhaps you can sharpen Deligne's theorem and replace 2 by something smaller?

   5. Read and understand the code for procedure FZ(r,N). By taking N fairly large (say 50000, or whatever your computer will allow) find the first 30 terms of FZ(r,50000), for r from 1 to 40. Discarding the (conjectural) infinities, is it in the OEIS? Should it be? Which r would give a (possible) Lehmer conjecture?

   Added March 29, 2021: The students' nice solutions are in this directory

   ---

   Lecture 18 (Monday, March 29, 2021)

   Programs done on Monday, March 29, 2021

   I deleted by accident C18.txt, but at any rate it was unfinished, the first homework problem is to follow the outline in the lecture and write procedure Aigner(n).

   Homework for Monday March 29, 2021, class (due Sunday, 4/4/2021 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#18

   and an attachment

   hw18FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Write a procedure

      Aigner(n)

      that inputs a positive integer, and uses Martin Aigner's ingenious lexigoraphic greed idea to output a Symmetic Chain Decomposition of the Boolean Lattice

      For example, Aigner(2) should return

      [ [[],[1],[1,2]] , [[2]] ]

   2. Write a procedure

      SCD(n)

      that uses the idea at the very end of the lecture to construct from each chain of SCD(n-1) by creating two new chains of SCD(n). Verfy that you get the same output as Aigner(n)

   Added April 5, 2021: The students' nice solutions are in this directory

   ---

   Lecture 19 (Thurs, April 1, 2021)

   Programs discussed on Thurs., April 1, 2021

   C19.txt ,

   Please see the various Helps19 and the comments in the above file (too numerous to list here)

   We discussed three famous NP hard problems.

   Homework for Thurs. April 1, 2021, class (due Sunday, 4/4/2021 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#19

   and an attachment

   hw19FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Read and understand procedure CrP(G,t) in C19.txt

   2. [A challenge, I don't know the answer] Write a version of CrP(G,t), call it

      CrPbetter(G,t)

      That tries to pick an "optimal edge" to delete/contract with each time, using a subroutine

      BestEdge(G)

      That picks the best edge (using some criteria) rather than a random one (like in the original code)

   3. Look up the definition of the Petersen graph and use CrP(G,t) to find its chromatic polynomial. In how many ways can you color it with 1000 colors?

   4. [Optional Challenge, I don't know the answer] Find an even better algoritm for deciding the Knapsack problem.

   5. [Optional Challenge] IsHam(G) in C19.txt is extremeley inefficient. Find a quicker way, that hopefully would work with graphs up to 20 vertices (20! is hopeless)

   Added April 5, 2021: The students' nice solutions are in this directory

   ---

   Lecture 20 (Nonday, April 5, 2021)

   Programs discussed on Monday, April 5, 2021

   C20.txt ,

   Contains procedures

   • Box(Dim): inputs a list of pos. integers DIM and outputs the set of vectors {1,2,3.., Dim[1]} x....x {1,2,... Dim[nops(Dim)]}

   • HamD(u,v): The Hamming distance between vectors u and v

   • Nei(S,v): inputs a set of vectors S and a vector v outputs the number of members of S whose Hamming distance to v is 1

   • MaxHD(S): inputs a set of vectors S and outputs the max number of neighbors a member of S can have

   • Hao(Dim,J): Inputs a list Dim, and an integer J between 1 and nops(Box(Dim)) and outputs the champion, and the record in the competition which subset of Box(Dim) with J elements has the minimimum degree

   Homework for Monday April 5, 2021, class (due Sunday, 4/11/2021 9:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#20

   and an attachment

   hw20FirstNameLastName.txt

   and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

   Also have your name at the first line #Homework by ...

   1. Write a procedure

      AvHD(S)

      that inputs a set of vectors S and outputs the average number of neighbors a vertex has, rather than the maximum

   2. Write a procedure

      AvAv(Dim,J,K)

      that inputs Dim, J (like in Hao(Dim,J)) and a LARGE integer K, and by using combinat[randcomb](Box(Dim),J) picks K random subsets, for each computes AvHD(S), and averages over all of them. What are your estimates for (run it serval times and see whether you get close answers to each other)

      AvAv([2,2,2,2,2,2,2],65,10000) ;

   3. Corrected April 6, 2021, thanks to Blair Seidler]
      [Optional challenge, 10 dollars (I do know the answer)] Find a formula for AvAv([2$n],J) for arbitrary J and n. Compare it to the estimates that you got above by simulation.

   4. Write a procedure

      SimuHao(Dim,J,K): that Inputs a list Dim, and an integer J and a large positive integer K, uses combina[randcomb](Box(Dim),J) to generate a random subset of size J, K times, and outputs the "champion" and the "record" among the K sampled sets. What did you get for

      SimuHao([2$10],513,10000)?

      (If you could investigate all binomial(1024, 513) subesest, the answer, according to Hao Huang, should be ceiling(sqrt(10))=4)

   Added April 12, 2021: The students' nice solutions are in this directory

   ---

   Lecture 21 (Thurs., April 8, 2021)

   Programs discussed on Thurs., April 8, 2021

   C21.txt ,

   Contains procedures

   • In(n):n by n identity matrix, expressed as a list of lists

   • An(n): The matrix A_n in Knuth's note about Hunag's proof

   • Check1(n): checks that An(n)^2=n*In(2^n) (in Line 1 of the proof)

   • Bn(n): The 2^n by 2^(n-1) matrix B_n defined in the second paragraph of Knuth's note on Hao Huang's proof

   • Check2(n):checks that A_n B_n = sqrt(n) B_n

   • [Completed after class]
     Findx(n,H): inputs a pos. integer n and an arbitrary subset, H, of {1,...,2^n} of cardinality 2^(n-1)+1 finds the vector 2^(n-1)-dimensional vector x such that all the rows of Bn(n) that correspond to those that do NOT belong to H in Bn(n)x are 0 For example: Findx(3,{1,3,5,6,8});

   • [done after class]
     Findy(n,H): The 2^n-dimensinal vector B_n x where x=Findx(n,H) (see above)

     Homework for Thurs. April 8, 2021, class (due Sunday, 4/11/2021 9:00pm)

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: hw#21

     and an attachment

     hw21FirstNameLastName.txt

     and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

     Also have your name at the first line #Homework by ...

     1. Read and understand the end of procedure Findx done after class, and the new procedure Findy

     2. Write a procedures

        IntegterToVec(k,n), VecToInteger(v,n)

        that inputs an integer k in [1,2^n] (and n) and outputs the vector of length n that corresponds to the binary represenation of k-1 (written as a list) (with zeros padded at the front to make it of length n, if necessary)

        and its inverse procedure VecToInteger(v,n)

     3. Write a procedure

        FindAlpha(H,n)

        That inputs a subset of Box([2$n]) and computes the member(s) of H predicted by taking the index (indices) with the largest absolute value of Findy(n,H). Check that its number oe neighbors is indeed the number of neighbors in H (number of other vectors in H whose Hamming distance with it is 1). In other words, the procedure checks the last step in Knuth's version of Hao Huang's proof.

     4. Try it out with many random subsests of cardinality 2^(n-1)+1 of Box([2$n]) (once the {1,2} is converted to {0,1})

     Added April 12, 2021: The students' nice solutions are in this directory

     ---

     Lecture 22 (Monday, April 12, 2021)

     Programs discussed on Monday, April 12, 2021

     C22.txt ,

     Contains procedures

     • [From C11.txt)] Pn(n): The list of integer partitions of n

     • Ap(Y,i,m):write a procedure that inputs a Standard Young Tableau and an integer i between 1 and nops(Y)+1 and inserts the entry m at the end of the i-th row, or if i=nops(Y)+1 make a new row with 1 cell occupied with m

     • SYT(L): inputs an integer partion (given as a weakly decreasing list of POSITIVE integers OUTPUTS the LIST of Standard Young Tableax of shape L (n=Number of boxes of L) (A way of filling 1, ..., n in the boxes such that horiz. and vertically they are increasing

       syt(L): inputs an integer partion (given as a weakly decreasing list of POSITIVE integers OUTPUTS the NUMBER of Standard Young Tableax of shape L (n=Number of boxes of L) (A way of filling 1, ..., n in the boxes such that horiz. and vertically they are increasing

     Homework for Monday April 12, 2021, class (due Wed., 4/14/2021 9:00pm) [Note unusual due date]

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: hw#22

     and an attachment

     hw22FirstNameLastName.txt

     and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

     Also have your name at the first line #Homework by ...

     1. Using the Wilf methodogy, with a "loaded die" (from C4.txt ) write a function

        randomSYT(L)

        that inputs an integer partition L (aka shape) and outputs, uniformly at random, one of the syt(L) Standard Young tableaux of that shape,

     2. Write a procedure

        TotalSYT(n)

        that inputs a positive integer n, and outputs the total number of standard Young tableaux with n cells [Hint: sum-up syt(L) over all members of Pn(n)

        Is that sequence in the OEIS? What is its A-number

     3. More generally, write a procedure

        TotalSYTpower(n,k)

        that inputs a positive integer n, and outputs the total number of k-tuples of standard Young tableaux of the same shape with n cells [Hint: sum-up syt(L)^k over all members of Pn(n)

        Is that sequence for k=2, in the OEIS? What is its A number? What about k=3, k=4, etc.?

     4. Optional Challenges (also due, Wed. April 14, 9:00pm)

        The next challenges require you to be honest!, you should do them all by yourself (no internet, no books, nor articles, no asking people, only using Maple and the programs done in C22.txt )

        • [5 dollars to be divided among all correct solvers] Conjecture a closed-form formula, in terms of a1, a2, for the number of Standard Young tableaux of two rows of lengths a1,a2. In other words, an algebraic formula for syt([a1,a2]) (where of course a1 ≥ a2 ≥ 0).

          [Added April 15, 2021: This was solved correctly by AJ Bu, Robert Dougerty-Bliss, and Yuxuan Yang (see this directory)]

        • [5 additional dollars] Rigorously prove this formula (You can use Maple to do the needed algebra)

          [Added April 15, 2021: This was solved correctly by Robert Dougerty-Bliss, and Yuxuan Yang (see this directory)]

        • [10 dollars to be divided among all correct solvers] Conjecture a closed-form formula, in terms of a1, a2, a3, for the number of Standard Young tableaux of three rows of lengths a1,a2,a3 In other words, an algebraic formula for syt([a1,a2,a3]) , (where of course a1 ≥ a2 ≥ a3 ≥ 0).

          [Added April 15, 2021: This was solved correctly by Robert Dougerty-Bliss, and Yuxuan Yang (see this directory)]

        • [10 additional dollars] Rigorously prove this formula (You can use Maple to do the needed algebra)

          [Added April 15, 2021: This was solved correctly by Yuxuan Yang (see this directory)]

        • [15 dollars to be divided among all solvers] Conjecture a closed-form formula, in terms of a1, a2, ..., ak, for the number of Standard Young tableaux with k rows of length a1,..,ak, In other words, an algebraic formula for syt([a1,a2,...ak]) , (where of course a1 ≥ a2 ≥... ak ≥ 0).

          [Added April 15, 2021: This was solved correctly by Robert Dougerty-Bliss, (see here) and Yuxuan Yang (see here and here) ]

        • [Additional 25 dollars to be divided among all correct solvers] Prove it rigorously.

          [Added April 15, 2021: This was "almost" solved correctly by Yuxuan Yang (see here). Yuxuan gave a correct expression involving k! terms, so as k gets larger it would be impractical. However, it is possible to express it as a determinant, and use linear algebra to get the formula conjectured by Robert Dougherty-Bliss, the famous Young-Frobenius formula] ]

     Added April 15, 2021: The students' nice solutions are in this directory

     ---

     Lecture 23 (Thurs., April 15, 2021)

     Programs discussed on Thurs., April 15, 2021

     C23.txt ,

     Contains procedures

     • Ins(Y,i,m): Inputs a (partially filled tableux Y, a row i, between 1 and nops(Y)+1 and an integer m and tries to place it LEGALLY at row i (if it is larger than all the current entries of row i and does not stick out, i=1 OR nops(Y[i])
     • RS1(Y,m): ONE STEP OF THE Robinson-Schenstead algorithm

     • RSleft(pi): The left tableau,S of the pair (S,T) that is the output of the Robinson-Scheastead mapping

     • AllSYT(n): The set of all Standard Young Tableau with n cells

     Homework for Thurs. April 15, 2021, class (due Sunday, 4/18/2021 9:00pm)

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: hw#23

     and an attachment

     hw23FirstNameLastName.txt

     and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

     Also have your name at the first line #Homework by ...

     1. Study and understand procedure RSleft(pi), finished after class.

     2. Write a short function SYTpairs(n) that inputs a positive integer n and outputs the set of pairs of standard Young tableaux of the same shape [S,T] each with n cells.

     3. [A little bit of a challenge] Write a procedure

        RS(pi)

        that inputs a permutation pi and outputs a member of STYpairs(n). S is the output of RSleft(pi) and T is the "template" tableau obtained by inserting, in turn 1,2,3,...,n to the new cell that emerges each time the shape of the left tableau increases by one cell. (Look it up "Robinson-Schenstead" in the internet for details)

     4. [A little bit of a challenge] Write a procedure

        InvRS(P)

        That inputs a pair [S,T] of standard Young tableaux of the same shape and outputs a permutation of 1,2,...n (where n is the number or cells of S (or T))

        Check that InvRS(RS(pi)) gives you pi for each pi in permute(7), and RS(InvRS([S,T])=[S,T] for each member of SYTpairs(n)

     5. [Optional challenge, 10 dollars] By phrasing Yuxuan Yang's beautiful formula for the number of standard Young tableaux of a given shape [a1,a2,...,ak] as a k by k determinant, and using linear algebra, derive Robert Dougherty-Bliss's formula (aka as the Young-Frobenius formula).

     Added April 19, 2021: The students' nice solutions are in this directory

     ---

     Lecture 24 (Mon., April 19, 2021)

     Programs discussed on Monday, April 19, 2021

     C24.txt ,

     Contains procedures

     • [From George Spahn's homework]
       SYTpairs(n) inputs a positive integer n and outputs the set of pairs of standard Young tableaux of the same shape [S,T] each with n cells

     • [From George Spahn's homework]
       RS1m(Y,m): ONE STEP OF THE RS algorithm modified to also return the row of the insertion

     • [From George Spahn's homework]
       RS(pi): the pair [S,T] that is the output of the Robinson-Scheastead mapping

     • [From George Spahn's homework]
       InvRS(P): The inverse of the Robinson-Schenstead mapping (so far tested for pairs [S,T] where both S and T are STANDARD Young tableaux of the same shape)

     • [Added after class]
       APP(Y,b,m): inputs a tableaux Y with entires {1,...,m-1} and and a vector b of either the same length of Y or one longer and appends b[i] m's to the end of row i for i=1..nops(Y) and if nops(b)=nops(Y)+1 a new row of b[nops(b)] m's. For example APP([[1,1,2],[2,2]],[1,1,1],3) should be
       [[1,1,2,3],[2,2,3],[3]]

     • [Completed after class]
       TAB(L,m): the set of all tableaux of shape L with entries in {1,2,...,m}

     Homework for Monday April 19, 2021, class (due Sunday, 4/25/2021 9:00pm)

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: hw#24

     and an attachment

     hw24FirstNameLastName.txt

     and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

     Also have your name at the first line #Homework by ...

     1. Convince yourself that procedure TAB(L,m), completed after class, using the subroutine APP(Y,b,m), works correctly

     2. Write a procedure

        TabPairs(n,m)

        that outputs all pairs [S,T] where S is a a (column-strict) tableau with entires from {1,...,m}, and T is a STANDARD tableau of the SAME shape

     3. We saw in class that RS(pi) also works when pi is a word. Either explain why George Spahn's InvRS(P) works for the more general scenario, or tweak it to make it work.

     Added April 26, 2021: The students' nice solutions are in this directory

     ---

     Lecture 25 (Thurs., April 22, 2021)

     Programs discussed on Thurs., April 22, 2021

     C25.txt ,

     Contains procedures

     • Wt(L,x): The weight according to x[1],..., x[m] of the tableau L

     • ScStupid:(L,x,m): the weight-enumerator, according to the weight

       x[1]^{Number of 1s} ...x[m]^{Number of ms}

       of the set of tableaux of shape L whose largest entry is m, done the STUPID way, by adding up all the weights of the member of TAB(L,m) of Lecture 24.

     • Sc(L,x,m): Same as ScStupid(L,x,m) (see above), but done more cleverly, using dynamical programming (mimicking TAB(L,m)

       This is called the Schur polynomial in the variables x[1],.., x[m], of shape L, usually denoted in books (and articles), by

       s_λ(x₁, ..., x_m)

     • [THANKS TO Blair Seidler, taken from a previous homework assigment]
       randomSYT(L): inputs an integer partition L (aka shape) and outputs, uniformly at random, one of the syt(L) Standard Young tableaux of that shape

     Homework for Thurs. April 22, 2021, class (due Sunday, 4/25/2021 9:00pm)

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: hw#25

     and an attachment

     hw25FirstNameLastName.txt

     and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

     Also have your name at the first line

     1. Write a procedure

        HookSet(L,cell)

        That inputs a shape L and a cell [i,j], with 1≤ i ≤nops(L), 1 ≤ j ≤ L[i], and outputs set set of all cells that are (weakly) to the right in the same row, and (weakly) down in the same column. For example,

        HookSet([5,5,3,2,1],[2,2]);

        should output the set

        {[2,2],[2,3],[2,4],[2,5],[3,2],[4,2]}

     2. [Corrected April 25, 2021, 11:00am, thanks to Blair Seidler, who won a dollar]

        Write a procedue

        OneStepGNW(L)

        that implements one iteration of the beautiful Greene-Nijenhuis-Wilf algorithm, by ( note correction thanks to Blair S.), picking one of the n cells, uniformly at random, and starting at that cell, "walking" to a corner cell, by at each step, (if you are currently at location cell), picking UNIFORMALLY at random a member of

        HookSet(L,cell) minus {cell}

        and going there, until you hit a corner cell, placing n there.

     3. By iterating the above OneStepGNW(L), n steps, (where n is the number of boxes, i.e. add(L)) write a procedure

        GNW(L)

        That does the same as randomSYT(L).

        [You can also do it recursively, using OneStepGNW(L) to find the corner cell where to put n, calling the shrunk shape L1, calling GNW(L1), and adding the above cell with n it it].

        Convince yourself that GNW([10,10,10]) is MUCH faster than randomSYT([10,10,10]). How long does it take to get

        GNW([9$9]);

     4. [Human challenge (but mandatory, do your best)]. Defnoting by h_ij the hook-lenght of the cless [i,j], prove (say by induction on the number of rows, or otherwise) that the hook-lenght formula that stays that

        syt([a1,a2,..., ak])=n!/Product(h_ij, over all the n cells [i,j] of L)

        Is equivalent to the Robert-Dougerty-Smith formula (previously called the Young-Frobenius formula) that says that

        syt([a1,..., ak])= Delta(a1+k-1,a2+k-2, ..., ak)*(a1+...+ak)!/((a1+k-1)!(a2+k-2)!....ak!)

        Where Delta(x1,...xk) is the discriminant, i.e the produc of xi-xj over all 1 ≤ i ≤ j ≤ k.

     5. [Optional challenge, 10 dollars] Without "peeking" (no internet, books, or asking people), conjecture an "explicit" formula (it is OK to use determinants) for the Schur polynomial Sc(L,x,m).

        [Hint: Multiply Sc(L,x,m) that you got from Maple, by the Discrimiant Delta(x[1], ..., x[m]), expand, and try to detect a pattern.]

     6. [Optional challenge, another 10 dollars] Prove that formula, using the implied recurrence behind procedure Sc(L,x,m), or otherwise.

     Added April 26, 2021: The students' nice solutions are in this directory

     ---

     Lecture 26 (Monday, April 26, 2021)

     Programs discussed on Monday, April 26, 2021

     C26.txt ,

     Contains procedures

     • ekn(k,n,x): e_k(x[1],...,x[n]): the elementary symmetric coeff of t^(n-k) in(t+x[1])*(t+x[2])*...*(t+x[n]). Also the weight enumerator of all subests of k elements in {1, ...,n}

     • hkn(k,n,x): h_k(x[1],...,x[n]): the full homogeneous symmtric functions coeff of t^k 1/(1-x[1]*t)/(1-x[2]*t).... also the weight enumerator of all sequenes of 1<= i1<=i2 <=i3<= ...<=ik <=n

     • Is2First(Y): Inputs a Standard Young tableau Y, decides whether 2 is in the row

     • Est2First(L,K): estimates the probability of the event "2 is in the first row" by doing a public opinion poll among K random Standard Young tableaux (using GNW)

     • sytC(L): The number of standard Young tableaux of shape L using the Young-Frobenius formula

     • ScY(L,x,m): The Schur polynomial in x[1],..., x[m] of the shape L, according to the determinant formula rediscovered by Yuxuan Yang

     • [Courtesy of Yuxuan Yang, from hw25]

       GNW(L): inputs a shape L and outputs a (uniformly at) random Standard Young tableau using the Greene-Nijenhuis-Wilf amazing algorithm

     Homework for Monday. April 26, 2021, class (due Sunday, 5/2/2021 9:00pm)

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: hw#26

     and an attachment

     hw26FirstNameLastName.txt

     and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

     Also have your name at the first line

     1. Implement the two Jacobi-Trudi formulas for the Schur polynomials as described in wikipedia, and make sure that they give you the same answers as Sc(L,x,m) and ScY(L,x,M).

     2. Wrire a procedure

        StartShape(Y,k)

        That inputs a Standard Young tableau and a positive integer, and outputs the shape of the sub-tableau consisting of {1,2,3,..,k}. For example

        StartShape([[1,3,4],[2,5],[6]],4);

        should give you [3,1]

     3. Write a procedure

        EstStart(L,k,K)

        that uses GNW(L) K times (K large) and for each of the partitions of k (use Pn(k)) estimates the probability that a random Standard Young tableau of shape L has that starting shape (so the output is a list of length pn(k), corresponding to the frequency of it being the Start Shape with k cells.

        What did you get for

        EstStart([9$12],5,10000)?

     4. [Optional challenge, 10 dollars] Write a procedure

        ExatStart(Y,k)

        that finds the EXACT values estimated by EstStart(Y,k,K) (for large K)

        [Hint: write a procedure sytSkew(L,L1) that finds the number of standard Young tableaux of skew-shape L\L1 (look up Skew-shape)]

     Added May 3, 2021: The students' nice solutions are in this directory

     ---

     Lecture 27 (Thurs., April 29, 2021)

     Programs discussed on Thurs., April 29, 2021

     C27.txt ,

     Contains procedures

     • [From Victoria Chayes' hw9]
       SAc(f,x,K): inputs a generating function and outputs the list of length K consisting of the average, variance, and 3rd throught Kth moments about the mean

     • ScM(f,x,K): The expectation, variance, and scaled moments about the mean (up to the K-th #moment) of the r.v. whose prob. generating function is f in the variable x

     • [From C11.txt]
       pnk(n,k): The number of integer partitions of n with largest part k

     • pn(n,t): The enumerative generating function of the set of integer partitions of n according to the weight t^{Largest Part}

     • GMN(M,N): The Gaussian Lattice: the list of lentgh MN+1 starting at rank 0 and ending at rank MN, whose i-th entry is the list of all integer partitions of i with largest part ≤M and number of parts ≤ N, given in lexigrophaic order

     Homework for Thurs.. April 29, 2021, class

     Work on your project. The preliminary draft, hopefully to be expanded during the summer, is due May 10, 2021.

     Programs discussed on Thurs.

     ---

     Lecture 28 (Monday, may 4, 2021)

     Programs discussed on Monday May 3, 2021

     See the lecture

     Homework for Monday. May 3, 2021, class

     Work on your project. The preliminary draft, hopefully to be expanded during the summer, is due May 10, 2021.

     HAVE A GREAT SUMMER! See you in the next edition of this class, Spring 2022.

     ---

     Dr. Z.'s teaching page