Math 640: EXPERIMENTAL MATHEMATICS (Automated Enumerative and Statistical Combinatorics) (Spring 2021) [Synchronous Remote]

http://sites.math.rutgers.edu/~zeilberg/math640_21.html

Last Update: May 3, 2021


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


Optional (but Highly recommended) Getting Started Homework

Teach yourself the basics of Maple by reading Frank Garvan's golden-oldie part 1, part 2
Note: a few commands are no longer valid in today's Maple. The most important one is that " has been replaced by %.

For more details, see this 2002 masterpiece.

How to submit homework


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

Programs done on Thurs., Jan. 21, 2021

C1.txt , Contains procedures

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

Please email ShaloshBEkhad at gmail dot com an email with

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)2 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

C2.txt , Contains procedures

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

Please email ShaloshBEkhad at gmail dot com an email with

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

C3.txt , Contains procedures

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

Please email ShaloshBEkhad at gmail dot com an email with

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 exception2 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

    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

    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

    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

    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

    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

      Pn(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(Pn(a) xn/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 xn, (multiplied by n!, of course), and then applied to ak, 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 ,

    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-μ)2*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 ,

    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 xk 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 Pn(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(Pn(t) xn/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 Pn(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 ,

    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 Pn(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

      P4(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(Pn(t),n=0,1,2,3...] is an infinite sequence of POLYNOMIALS, in t, such that Pn(1)=pn(n)

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

      Sum(Pn(t) qn, n=0..infinity)=Product(1/(1-tqi),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 {Pn(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:

    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:

    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:

    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:

    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:

    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:

    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 p11/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 p11/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

    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