Math 640: EXPERIMENTAL MATHEMATICS (Algorithmic Algebraic Combinatorics) Fall 2016 (Rutgers University) Webpage

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

Last Update: March 21, 2017.


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 algebraic combinatorics, and the powerful theory of symmetric functions. This is a beautiful subject for its own sake, and approaching it from the standpoint of computer algebra will make it crystal clear.

In addition to the actual, very important content, students will master the methodology of computer-generated and computer-assisted research that is so crucial for their future.

There are no prerequisites (except for mathematical maturity). In particular, no prior knowledge of Maple, or any programming experience, is assumed. Also, no overlap with previous years.


Textbooks

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 %.

How to submit homework


Diary and Homework assignments

Programs done on Thurs., Sept. 8, 2016

C1.txt , Contains procedures

Homework for Thurs., Sept. 8, class (due Sunday Sept. 11, 10: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 .
    Note: a few commands are no longer valid in today's Maple. The most important one is that " has been replaced by %.

  2. [Optional, but strongly recommended for novices]
    Generalize SW(n) to write a procedure

    GSW(n,S)

    that inputs a positive integer n, and a set of two-dimensional vectors with integer entries, the set of fundamental steps and outputs the set of self-avoiding walks of length n. The output of GSW(n,{[1,0],[-1,0],[0,1],[0,-1]}) should be the same a SW(n).

  3. [Optional, but strongly recommended for novices]
    Use the nops command, and the above procedure to write a one-line procedure

    SeqGSW(N,S)

    that outputs the list, of length N, of the cardinalities of GSW(n,S), from n=1 to n=N.

    Which of the following are in the OEIS

  4. [Optional, but strongly recommended for novices]
    Generalize SW(n) to write a procedure SWfm(n,d) that inputs a positive integer n, and outputs the set of "finite-memory" walks where you can't revisit a lattice point that you have visited in the last d, steps, but being forgetful, you don't mind visiting places that were visited more than d steps ago (note that SWfm(n,n) equals SW(n)).

  5. [Optional, but strongly recommended for novices; MANDATORY FOR EXPERTS]
    Use the nops command, and the above procedure to write a one-line procedure

    SeqSWfm(N,d)

    that outputs the list, of length N, of the cardinalities of SWfm(n,d), from n=1 to n=N.

    Which of the following are in the OEIS


Added Sept. 12, 2016: See the students' nice solutions.


Programs done on Monday, Sept. 12, 2016

C2.txt , Contains procedures

Homework for Monday Sept. 12, class (due Sunday Sept. 18, 10: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. Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 2

  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-60 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
    Only record a small sample in hw2YourName.txt .
    Note: a few commands are no longer valid in today's Maple. The most important one is that " has been replaced by %.

  2. [Optional, but strongly recommended for novices; MANDATORY FOR EXPERTS]

    Write an analog of CompC(n,C), call it

    PartitionsC(n,C)

    with the same inputs, a non-neg. integer n, and a function C that inputs a positive integer and outputs a condition (e.g. n-> n mod 2=1) and outputs the set of PARTITIONS of n (weakly-decreasing vectors that add-up to n.

    [Hint, you may want to first write a program PartitionsC1(n,m,C) for the set of partitions of n whose largest part is m, and that satisfies the condition C, and then take the union of these for m from 1 to n]

  3. [Optional, but strongly recommended for novices; MANDATORY FOR EXPERTS] Write an enumeration analog of the above, call it

    NuPartitionsC(n,C)

  4. Write a one-line procedure

    SeqNuPartitionsC(N,C)

    that outputs the first N+1 terms, starting at n=0.

  5. Which of the following are in the OEIS


Added Sept. 19, 2016: See the students' nice solutions.


Programs done on Thurs., Sept. 15, 2016

Today was a nice day, and we used the computer between our shoulders.

Homework for Thurs. Sept. 15, class (due Sunday Sept. 18, 10: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 in the second line
#YourName, Math 640 (Fall 2016) homework assignment 3

  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 60-90 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
    Only record a small sample in hw2YourName.txt .
    Note: a few commands are no longer valid in today's Maple. The most important one is that " has been replaced by %.

  2. Carefully read, and then write, in your own words, a one page summary of Enumerative and Algebraic Combinatorics

  3. [Optional, but strongly recommended for novices; MANDATORY FOR EXPERTS]

    Write a procedure

    WtE(m,S,t)

    that inputs a positive integer m, a subest S, of {0,...,m-1}, and a variable-name t, and outputs the rational function whose coefficient (in its Maclaurin expansion) of t^n is the number of compositions of n (vectors of positive integers) whose components only belong to the residue classes

    s (mod m) for s in S

    What are

    WtE(5,{1,4},t); WtE(7,{3,7},t);?

  4. [Human Challenge, 5 dollars to be divided among the first solvers] Find a bijection (both ways) between the set of compositions of n into parts that are a (mod b), and the set of compositions of n-a into parts that belong to the two-element set {a,b}. Describe both directions, and implement them in Maple.

Added Sept. 19, 2016: See the students' nice solutions.


Programs done on Monday, Sept. 19, 2016

C4.txt , Contains procedures under construction, that were supposed to be continued next class, but were abandoned in favor of the Goulden-Jackson Cluster method.

Homework for Monday Sept. 19, class (due Sunday Sept. 25, 10: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 in the second line
#YourName, Math 640 (Fall 2016) homework assignment 4

  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 90-end of Frank Garvan's awesome Maple booklet ( part 1, part 2)

  2. Write a procedure

    Comp([L1,L2],t)

    that inputs a list of integers L1 all relatively prime, and another list of integers L2, of the same length, such that L2[i] is between 0 and L1[i]-1 (inclusive), and outputs the generating functions whose coefficients of tn is the number of compositions of n into parts that belong to at least one of the congruences classes

    L2[i] (mod L1[i]), i=1..nops(L1)

    Hint: Use chrem (Chinese remaindering) and Inclusion-Exclusion to first find the generating function (weight-enumerator) of the set of integers that belong to that union.


Added Sept. 26, 2016: See the students' nice solutions.


Programs done on Thursday, Sept. 22, 2016

C5.txt, Contains procedures

Homework for Thursday Sept. 22, class (due Sunday Sept. 25, 10: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 in the second line
#YourName, Math 640 (Fall 2016) homework assignment 5

  1. Carefully read and understand pp. 4-10 of the Noonan-Zeilberger masterpiece. Write a short summary of the method in your own words.

  2. Write a procedure

    GoodWords(A,BadW,n)

    that inputs

    and outputs the set of n-letter words in A that do not contain, as consecutive subwords, any of the members of BadW.

  3. Using GJ and GoodWords, write a short procedure

    CheckGJ(A,BadW,N)

    that checks that the coefficient of t^n in GJ(A,BadW,n) equals nops(GoodWords(A,BadW,n)) for n from 0 to N.

  4. Generalize procedure GJ(A,BadW,t) to write a procedure

    GJs(A,BadW,t,s)

    that inputs the same arguments as GJ, and in addition, a variable s, and outputs the rational function in t and s, whose coefficient of t^n is the polynomial in s that is the weight-enumerator of n-letter words in the alphabet A according to the weight sNumberOfBadSubWords. Of course, when s=0 you should get the old output, and when s=1, you should get 1/(1-t*|A|).

    Hint: Instead of the trivial identity 0=1+(-1), use the deep identity s=1+ (s-1). Everything should extend in Clu with -1 replaced by s-1.

  5. Write a procedure

    CleanUp(BadW)

    that inputs a set of words, and outputs the subset of minimal words. For example

    CleanUp({[1,2,1,2],[2,1],[1,2,3,4],[2,3]});

    should output {[2,1],[2,3]}

  6. Use procedure GJ to prove the following interesting fact

    Let a(n) be the number of ways of tossing a coin n times and never getting two consecutive Heads, and let b(n) be the number of ways of tossing a coin n times so that you never get three consecutive Heads and never get three consecutive Tails. Then, for n ≥ 1, we have

    b(n)=2a(n-1)

  7. [Challenge, 10 dollars to be divided (I don't know the answer)] Give a nice bijective proof of the above proposition.


Added Sept. 26, 2016: See the students' nice solutions.


Programs done on Monday, Sept. 26, 2016

C6.txt, Contains procedures

Homework for Monday Sept. 26, class (due Sunday Oct. 2, 10: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 in the second line
#YourName, Math 640 (Fall 2016) homework assignment 6

  1. [corrected Sept. 29, 2016, thanks to Jinyoung Park]

    Prove Humanly, that if there is a rational function N(t)/D(t), whose denominator's smallest root (in absolute value) is distinc and positive, let's call that smallest root 1/α, then if a(n) are coefficients of its Taylor expansion

    sum(a(n)*t^n, n=0..infinity) = N(t)/D(t) then

    a(n) is asymptotic to C*(α)^n, for some constant C. Let's call α the GROWTH CONSTANT. Can you find an expression for C? (in terms of N(t), D(t) and α) .

  2. It follows from the Goulden-Jackson algoritm that for any set of words BadW, in any alphabet, the sequence a_w(n) enumerating the number of words of length n in the alphabet A that avoid w as a cosecutive subword is asymptotic to C*(αw)n for some constant αw (< |A|). Let's call that number its growth-constant. Write a program

    GC(A,Badw)

    that inputs an alphabet A, and a set of words Badw, and outputs the growth constant of the sequence enumerating n-letter words avoiding the members of Badw. The output should be a floating-point number.

  3. Write a procedure

    Ranker(m,k)

    that inputs positive integers m and k, and outputs the list of length m^k that lists all the k-letter words in the alphabet {1,...,m} according to their growth constant, togetger with their respective growth constant.

    What are

    Ranker(2,2), Ranker(2,3), Ranker(2,4), Ranker(3,3)?

  4. Use the Goulden-Jackson procedure to find the generating function enumerating memory-4 self-avoiding walks in the 2D square lattice. How many such walks are there of length 1000?

    Hint: The alphabet is {-1,1,2,-2} and the "bad words" are [-1,1],[1,-1],[2,-2],[-2,2], and [1,2,-1,-2] and all its images under the group of signed-permutation of order 2.

  5. [Challenge] Ditto for memory 6 SAWs.



Added Oct. 4, 2016: See the students' nice solutions.

Programs done on Thurs., Sept. 29, 2016

C7.txt, Contains procedures

Homework for Thurs. Sept. 29, class (due Sunday Oct. 2, 10: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 in the second line
#YourName, Math 640 (Fall 2016) homework assignment 7

  1. Generalize

    PlotT(T,Rx,Ry,dx,dy,eps), that inputs a complete binary tree T

    and write a procedure

    PlotTg(T,Rx,Ry,dx,dy,eps)

    that inputs any ordered tree (not necessarily a complete binary tree) and plots it.

    Plot and save (as a .jpg or .gif file) the picture for

    PlotTg( [ [[]$3]$4, [[]$5]$2] ,0,0,10,10,2);

  2. Recall that a composition of an integer n is a list of positive integers that add-up to n. Write a procedure (using recursion)

    Comp(n,k)

    that inputs a positive integer n, and another positive integer k (k ≤ n), and outputs the set of compositions of n into exactly k parts.

    For example

    Comp(5,3)={[3,1,1],[1,3,1],[3,1,1],[2,2,1],[2,1,2],[1,2,2]}   .

  3. [Mandatory for experts ( a bit of a challenge), optional for novices]

    Using procedure Comp(n,k) (with various k's) write a procedure

    gTreesLeaves(n,S)   ,

    that inputs a positive integer n, and a set of positive integers S, and outputs the set of ordered trees on n LEAVES where each vertex is either a leaf (has zero children), or its number of children is a member of S. For example

    gTreesLeaves(n,{2})=BT(n)   .

    Hint: You may want to write a procedure (of find out whether Maple has one)

    CartProd(ListOfSets)

    that inputs a list of sets and outputs their Cartesians product (if ListOfSets=[S1, ..., Sk], the set of lists [s1,..., sk] with s1 in S1, ..., sk in Sk). (the best way is to recurse on the length of ListOfSets).

  4. By ever-so-slightly modifying the above gTreesLeaves(n,S), write a procedure

    gTreesVertices(n,S)   ,

    that inputs a positive integer n, and a set of positive integers S, and outputs the set of ordered trees on n VERTICES where each vertex is either a leaf (has zero children), or its number of children is a member of S.

    Pick some random trees in gTreesVertices(10,{1,2,3}) and plot them using PlotTg(T,Rx,Ry,dx,dy,eps) that you have nicely written above.


    Added Oct. 4, 2016: See the students' nice solutions.


    Stuff Covered Oct. 3, 2016

    Today the class was fortunate to have a guest lecture by the great GURU, Neil Sloane the founder and President of the amazing OEIS

    Slides for Dr. Sloane's Oct. 3, 2016 Guest Lecture


    Programs done on Thurs., Oct. 6, 2016

    C9.txt, Contains procedures

    Homework for Thurs. Oct. 6 class (due Sunday Oct. 9, 10: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 in the second line
    #YourName, Math 640 (Fall 2016) homework assignment 9

    1. Write a procedure

      SeqManyCL(i,N)

      that inputs a positive integer i, and a positive integer N, and outputs the first N term of the sequence enumerating ordered trees with n LEAVES, where every vertex either has no children, or at least i children.

      Which ones are in the OEIS? (indicate the A numbers, if they are). Are they for this reason, or a different one?

      • SeqManyCL(2,30);
      • SeqManyCL(3,30);
      • SeqManyCL(4,30);
      • SeqManyCL(5,30);
    2. Write a procedure

      SeqManyCV(i,N)

      that inputs a positive integer i, and a positive integer N, and outputs the first N term of the sequence enumerating ordered trees with n VERTICES, where every vertex either has no children, or at least i children.

      Which ones are in the OEIS? (indicate the A numbers) SeqManyCV(1,30);SeqManyCV(2,30);SeqManyCV(3,30); SeqManyCV(4,30);

    3. Using GP1 (as we did in class), conjecture an explicit expression for

      baS(h,d) (where h ≥ d)

      Prove it my induction, using the recurrence used to in baS(h,D) to get the numbers in the first place, and checking the initial conditions and boundary condition when d=h+1.

      Deduce the fact that baS(n,n)=C(n), the Catalan number.

    4. [Challenge, 4 dollars to be divided, corrected Oct. 7, 2016 (thanks to Jinyoung Park)]

      Find a bijection between the set of COMPLETE BINARY TREES on n leaves and the set of ballot sequences with n-1 H's and n-1 D's . Program both directions in Maple.

      [Hint: for us humans, it is helpful to visualize a ballot sequence as a walk in the 2D plane, starting with [0,0] and H=[1,1], D=[1,-1]. Note that these walks never venture below the x-axis]

    5. [Challenge, 10 dollars to be divided]

      Give a bijective proof of the fact that the number of complete binary trees on n leaves is

      a(n):=binomial(2n-2,n-1)/n

      By giving a bijective proof of the recurrence

      na(n)= 2 (2n-3) a(n-1)

      Implement both directions in Maple, and make sure that their composition is the identity (in both directions).

      [Very slight Hint: the left side counts complete binary trees with one of the leaves marked (that's the input set). The right side counts the number of elements in the Cartesian product of a two-element set (perhaps {Left, Right}), a "natural" set of cardinality 2n-3, and the set of complete binary trees with n-1 leaves.

    Added Oct. 10, 2016: See the students' nice solutions.


    Programs done on Monday, Oct. 10, 2016

    C10.txt, Contains procedures

    Homework for Monday Oct. 10 class (due Sunday Oct. 16, 10: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 in the second line
    #YourName, Math 640 (Fall 2016) homework assignment 10

    1. Complete procedure SP1(n) that we started in class, to generate the set of set-partitions of {1, ..., n}. Make sure that you get the same output as SP(n)

    2. Write a short recursive procedure,
      Str2(n,k)
      to find the number of set-partitions of {1, ...,n} with exactly k sets, mimicking SPnk(n,k). Also use it to write a procedure, Bell2(N), to find the first N Bell numbers. Make sure that it agrees with Bell1(N)

    3. Read and understand the proof of the Lagrange Inversion Formula as described here

    4. Generalize procedure LId(P,z,N) and LI(P,z,N) to write procedures

      LId(P,G,z,N) and LI(P,G,z,N)

      implementing the Generalized Lagrange Inversion Formula as described in the above-mentioned writeup.

    5. [Optional Challenges] Solve, as many problem as you can from American Mathematical Monthly Problems for Oct. 2016

    Added Oct. 17, 2016: See the students' nice solutions.


    Programs done on Thurs., Oct. 13, 2016

    C11.txt,

    Contains procedures

    Homework for Thursday Oct. 13 class (due Sunday Oct. 16, 10: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 in the second line
    #YourName, Math 640 (Fall 2016) homework assignment 11

    1. Using procedure RSPnk(n,k), and yet-another roulette with [Snk(n,1), ..., Snk(n,n)], write a procedure

      RSPn(n)

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

    2. Using the recurrence

      B(n)=Sum(binomial(n-1,k-1)*B(n-k),k=1..n) ,

      (proved by deciding who would be the set-mates of element n), write an alternative procedure

      RSPnNew(n)

      that outputs a random set-partition.

      Hint: you first need to write a subroutine, RSubSetnk(n,k) that picks a uniform-at-random k-subset of an n-element set {1, ..,n} .

    3. Write a procedure

      RandomBallotSequence(m,n)

      that inputs non-neg. integers, m, n, such that m ≥ n, and outputs a (uniformly-at) random ballot sequence with m Hillarys and n Donalds, i.e. where Donald was NEVER ahead of Hillary

    4. Read and understand, Andre Joyal's goregous proof of Cayley's nn-2 formula for the number of labelled trees on n vertices, by reading this nice write-up

    Added Oct. 17, 2016: See the students' nice solutions.


    Programs done on Monday, Oct. 17, 2016

    C12.txt,

    Contains procedures