Last Update: March 21, 2017.

• Teacher: Dr. Doron ZEILBERGER ("Dr. Z")
• Classroom: Allison Road Classroom Building [Busch Campus], IML Room 121.
• Time: Mondays and Thursdays , period 3 (12:00noon-1:20pm)
• "Textbooks": Online sources, and texts supplied by instructor.
• Dr. Zeilberger's Office: Hill Center 704
• Dr. Zeilberger's Email: DoronZeil at gmail dot com
  [Please don't use the official email address posted in the department's directory, I check is much less often, and I hate it, since it uses Microsoft software.]
• Dr. Zeilberger's Office Hours (Fall 2016): MTh 10:30am-11:30am and by appointment

Description

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

• Dr. Z.'s terse yet brilliant introduction to Enumerative and Algebraic Combinatorics
  (published in the Princeton Companion of Mathematics, W.T. Gowers, ed.)

• Ian Macdonald's classic book on Symmetric Functions
  [don't be scared about its length, we will focus on the most important chapter 1.]

• [Needed for the homework for C6.txt] pp. 74-76 of Ariel Rubinstein's fascinating Economic Fables.

• [Needed for Class 10, C10.txt] Lagrange Inversion

• [Needed for Optional (and mandatory) Challenge homework for Class 10 (and later)] American Mathematical Monthly Problems for Oct. 2016

• [Win the SCM prize!] SCM prize on random walks

• Guru Donald Knuth's legenedary Section 5.1.4 from the Art of Computer Programming, v. 3.

• Yusra Naqvi's fascinating article ("officially" published rececntly in the print-journal, J. of Algebaric Combinatorics, but already published two years ago in arxiv.org)
  [Note: Yusra Naqvi is an an alumnae, of this class having taken the2012 edition ]

• The Greene-Nijenhuis-Wilf gorgeous proof of the hook-length formula and the even more gorgeous algorithm to generate a random Standard Young Tableau of a given shape.

• Yuefei Zhao's nice article about Young Tableaux and the Representations of the Symmetric Group.

Optional (but Highly recommended) Getting Started Homework

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 Anthony Zaleski 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 #)

  hw2AnthonyZaleski.txt and hw3AnthonyZaleski.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

Diary and Homework assignments

Programs done on Thurs., Sept. 8, 2016

• W(n): Inputs a non-negative integer n, and outputs the set of Lattice walks with n steps in the 2D lattice with units steps in each direction, where
  1:East, -1:West 2:North -2: South

• w(n): inputs a non-negative integer n, and outputs the NUMBER of Lattice walks with n steps in the 2D lattice, using a very clever and sophisticated recurrence: w(n)=4w(n-1).

• SW(n): the set of Self-Avoiding Lattice walks with n steps in the 2D lattice
  [the error we found in class has been corrected]

Homework for Thurs., Sept. 8, class (due Sunday Sept. 11, 10: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 .
   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

   • SeqGSW(8,{[1,0],[-1,0],[0,1],[0,-1]});
   • SeqGSW(10,{[1,0],[-1,0],[0,1]});
   • SeqGSW(8,{[-1,0],[1,0],[1,1]});

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

   • SeqSWfm(8,2);
   • SeqSWfm(8,4);
   • SeqSWfm(8,6);

Programs done on Monday, Sept. 12, 2016

• Comp(n,S): inputs a non-neg. integer n, and a finite set of POS. integers, S and outputs the SET of lists whose entries are from S and that add-up to n

• NuC(n,S): inputs a non-neg. integer n, and a finite set of POS. integers, S and outputs the NUMBER of lists whose entries are from S and that add-up to n, in other words, the output is the same as nops(Comp(n,S)), but of course much faster.

• SeqNuC(N,S): The sequence of values of NuC(n,S) from n=0 to n=N

• GFS(S,t): inputs a set of positive integers and a variable name t, outputs a rational function of t whose Maclaurin expansion is such that the coeff. of t^n is NuC(n,S) , in other words, the weight-enumerator of the (infinite) set of all words in the alphabet S with weight(word):=t^sum(word).

• CompC(n,C): inputs a non-neg. integer n, and a function that maps an integer to a condition and outputs the SET of lists whose entries satisfy the same condition phrased in terms of the symbol m, and add-up to n. Using an idea of Andrew Lohr For example CompC(6, m->evalb(m mod 2=1));

• NuCompC(n,C): same input as before, but outputs the cardinality of CompC(n,C) instead

• SeqNuCompC(N,C): the first N+1 terms in the sequence NuComp(n,C)

Homework for Monday Sept. 12, class (due Sunday Sept. 18, 10: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. 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
   • SeqNuPartitionsC(30,m->m mod 5=1 or m mod 5=4)

   • SeqNuPartitionsC(30,m->m mod 5=2 or m mod 5=3)

   • SeqNuPartitionsC(30,m->m mod 7=1 or m mod 7=2 or m mod 7=4)

Programs done on Thurs., Sept. 15, 2016

Homework for Thurs. Sept. 15, class (due Sunday Sept. 18, 10: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 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.

Programs done on Monday, Sept. 19, 2016

Homework for Monday Sept. 19, class (due Sunday Sept. 25, 10:00pm)

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.

Programs done on Thursday, Sept. 22, 2016

• GJ(A,BadW,t): inputs a finite alphabet A, and a set of words in A , "the bad words" and a variable t, outputs a rational function in t whose Maclaurin coef. of t^n is the number of n-letter words in the alphabet A, AVOIDING (as consecutive subwords) ANY bad words

• Clu(A,BadW,t): inputs a finite alphabet A, and a set of words in A , "the bad words" and a variable t, outputs the cluster generating function in the variable t.

Homework for Thursday Sept. 22, class (due Sunday Sept. 25, 10:00pm)

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

   • A: an alphabet (set of letters)
   • BadW: a set of words in A
   • n: a non-negative integer
   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 s^{NumberOfBadSubWords}. 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.

Programs done on Monday, Sept. 26, 2016

• GJz(A,BadW,z,t): inputs a finite alphabet A, and a set of words in A , "the bad words" and a variable t, outputs a rational function in t whose Maclaurin coef. of t^n is the weight-enumerator according to the weightmul(z[w[i]],i=1..nops(w)) n-letter words in A AVOIDING (as consecutive subwords) ANY bad words

  ArielR(A,Pr,BadW,t): [Inspired by pp. 74ff of Ariel Rubinstein's masterpiece Economic Fables (highly recommended), (BTW, Ariel Rubinstein was Dr. Z.'s army buddy)]
  Inputs a list of letters, A, the "alpbhabet" (think of a die with any number of faces ) with a prob. dist. Pr (prob. of the die lending on A[i] os Pr[i]), a set of words in A and outputs a rational generating function whose coeff. of t^n (in its Maclaurin expansion) is the Exact prob. of rolling the die n times and getting NO occurrence of BadW (thereby winning 25 dollars)

• ArielRc(A,Pr,BadW,t) the complementary probability of getting at least one occurrence, i.e. 1/(1-t)-ArielR(A,Pr,BadW,t):

• ArielRu(A,Pr,BadW,n): the prob. of getting at least one occurrence of member of BadW upon rolling the A-die (with loaded Pr) n times

Homework for Monday Sept. 26, class (due Sunday Oct. 2, 10:00pm)

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)ⁿ 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.

Programs done on Thurs., Sept. 29, 2016

• BT(n): the SET of complete binary trees on n leaves.

• bt(n): nops(BT(n)) (w/o computing BT(n)).

• De(T): the depth of the complete binary tree T.

• PlotT(T,Rx,Ry,dx,dy,eps): inputs a complete binary tree T and numbers Rx,Ry,dx,dy, and eps displayes the complete binary tree T, whose coordinates of the root are [Rx,Ry], and dx is the horizntal distance to the left and right of the two branches, and eps is a small parameter ensuring that these two branches do not meet.

Homework for Thurs. Sept. 29, class (due Sunday Oct. 2, 10:00pm)

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
   • TseqL(S,N): the first N terms from n=1 to n=N for the number of ORDERED TREES with n LEAVES, where any vertex can have either zero children or a number of children in S
     (Using the algebraic equation f=x+add(f^s, s in S))

     TseqV(S,N): the first N terms from n=1 to n=N for the number of ORDERED TREES with n VERTICES, where any vertex can have either zero children or a number of children in S
     (Using the algebraic equation f=x+x*add(f^s, s in S))

   • BaS(H,D,h,d): the SET of Ballot sequences in {H,D} with h H's and d D's (sequeces where every prefix has at least as many H's thanD's)

   • baS(h,d): the NUMBER of Ballot sequences in {H,D} with h H's and d D's (sequeces where every prefix has at least as many H's thanD's) [In other words, nops(BaS(H,D,h,d)), bt much faster]

   • GP1(L,n,d): inputs a list of pairs [input,output], and a variable n and outputs a polynomial of degree d such P(input)=output, or FAIL (if none exists)

   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
   • LId(P,z,N): the first N coefficients of the f.p.s. u(t) safisfying u(t)=t*P(u(t)) using u(t)->t*P(u(t))

   • LI(P,z,N): the first N coefficients of the f.p.s. u(t) safisfying u(t)=t*P(u(t)) using the famous Lagrange Inversion Formula

   • SP(n,k): the set of set-partitions of {1,.., n} into exactly k sets

   • SPn(n): The set of set partitions of {1,...,n}

   • Bell1(N): the list consisting of the N first Bell numbers

   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

   • Roulette(L):Inputs a list of pos. integers L, and outputs an integer from 1 to nops(L) such that the prob. of getting i is L[i]/convert(L,`+`):

   • RSPnk(n,k): generates a (uniformly-at) random set partition of {1,..,n} into k sets

   • Grab(pi,i): inputs a permutation pi of {1,..n} and i from 1 to n outputs the the cycle beloning to i

   • PtoC(pi): inputs a permutation in one-line notation outputs the set of cycles

   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 n^n-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

   • MTTn(A): inputs the (0-1) adjacency matrix of a simple graph, and outputs the number of spanning trees, using the Matrix Tree Theorem

   • MTT(A,n): inputs a letter A and outputs the "generating funtions" of all labeled trees

     LT(n): inputs a pos. integer n and outputs the set of labeled trees on n vertices

   • PC(f,i): inputs a function, f, from {1,...,n}->{1,...n} (n=nops(f)) and i from 1 to n, outputs the path leading from i to a cycle, followed by the cycle

   • [Finsihed by Dr. Z. after class]

     AJ(f): inputs a list of length n, say, consisting of {1,...,n} such that i goes to f[i] (representing a function from {1, ...,n} to {1, ...,n} (n^n of them), outputs the DOUBLY-ROUTED tree given by Joyal's bijection. The format of the output is [LabeledTreeGivenAsASetOfEdges, [FirstRoot, SecondRoot]]

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

     1. Read and understand the proof of the Matrix Tree Theorem as given here

     2. Read again this nice write-up about Joyal's mapping, and then carefully read procedure AJ(f) in today's code, finished after class by Dr. Z., and convince yourself that it is correct.

     3. By first writing an (easy) procedure

        Rfun(n)

        that inputs a positive integer n, and outputs one of the nⁿ lists of length n with entries from {1, ...,n}, each with the same probability, use procedure AJ(f), to write a (short!) procedure

        RLT(n)

        that inputs a positive integer n, and outputs one of the n^n-2 labeled trees, each with the same probability.

        ( Hint, apply AJ, and then discard the second component [FirstRoot,SecondRoot] )

     4. Write a procedures

        NuLeaves(T)

        that inputs a labeled tree on {1, ...,n}, say, given as a set of n-1 edges, and outputs the number of vertices that are leaves (have degree 1)

     5. By using RLT(n) and NuLeaves(T), write a procedure

        AveNuLeaves(n,K)

        that inputs a positive integer n, and a fairly large positive integer K, and finds the average number of leaves in a random sample of K labeled trees with n vertices, and hence forms an approximation for the real average.

        What did you get for

        AveNuLeaves(50,1000)? AveNuLeaves(100,1000)? AveNuLeaves(150,1000)? AveNuLeaves(200,1000)?

        Is it reasonable to conjecture, that as n goes to infinity, the average/n tends to a fixed number? Can you guess that number.

     6. [Optional Challenge, I don't know the answer off hand, it is probably well-known, so don't peek] Find an exact expression for the above mentioned average in terms of n.

        [Added Oct. 20, 2016. In fact, there is a nice very closed-form solution for the average number of leaves. You can get it as follows. Let f(s,t) be the exponential generating function for the sequence of Leaf polynomials, let's call is L_n(s), whose coefficient of s^i is the number of ROOTED labeled trees with i leaves. Then instead of the equation

        f(1,t)=t*exp(f(1,t))

        for straight enumeration, you have

        f(s,t)=t*(s-1+exp(f(s,t))

        Now use Lagrange inversion to express L_n(s) as (n-1)! times the coefficient of z^(n-1) in ((s-1)+exp(z))^n. From this you should get L_n'(1) and hence the average L_n'(1)/n^(n-1) , that happens to be a nice closed form]

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

     ---

     Programs done on Thursday, Oct 20, 2016

     C13.txt,

     Contains procedures

     • Pnk(n,k): the set of partitions of n with largest part k

     • Pn(n): the set of integer partitions of n

     • pn(n): nops(Pn(n)) via an enumeration procedure

     • SeqPd(N): the list of the first N p(n), via procedure pn(n)

     • SeqPe(N): the list of the first N p(n), via Euler's famous generating function

     • pnF(N): p(n), using the recurrence implied by Euler's Pentagonal Theorem (famously used by Major Percy MacMahon to compile a table up to N=200, and Ramanujan uused them to conjecture his famous congruences

     • SeqPnF(N): The sequence p(n), using the recurrence implied by Euler's Pentagonal Theorem (famously used by Major Percy MacMahon to compile a table up to N=200, and Ramanujan used them to conjecture his famous congruences

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

     1. Completely solve, using Maple to first experiment, and then prove, American Mathematical Monthly problem 11930 (proposed by Cornel Ioan Valean) in American Mathematical Monthly Problems for Oct. 2016, by conjecturing (using evalf and identify) an exact expression for the partial sum up to n minus arcsinh(sqrt(2)/2), and then using telescoping to prove it rigorously.

     2. Generalize procedures pnk(n,k) and pn(n) to write procedures

        pnkC(n,k,CongrConditions, DifferenceCondition) and pnC(n,CongrConditions, DifferenceCondition)

        where the additional inputs, CongrConditions is a set of congruences where "a mod b" is written [a,b], and DiffCondition is a positive integer. The output of pnC(n,CongrConditions, DifferenceCondition) should be the number of partitions of n whose parts satsifies one of the congruences, and the difference between consecutive parts is ≥ d. For example

        pn(n)=pnC(n,{[1,1]},0)

        pnC(n,{[1,2]},0) is the number of partitions of n into odd parts, and pnC(n,{[1,1]},1) is the number of partitions into distinct parts.

     3. Using pnC, prove empirically that the number of partitions of n into odd parts equals the number of partitions of n into distinct parts, for n between 1 and 200.

     4. Using pnC, prove empirically that the number of partitions of n into parts that are 1(mod 5) or 4(mod 5) equals the number of partitions of n where the difference between consecutive parts is at least 2, for n between 1 and 200, thereby confirming the first Rogers-Ramanujan identity

     5. Read (and understand!) the proof from book of Euler's Partitions Recurrence, used above in procedure pnF(n), and also by Major Percy MacMahon

     6. Write two Maple procedures, one for each direction of the gorgeos Bressoud-Zeilberger bijection, and make sure that they are indeed inverses of each other.

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

     ---

     Programs done on Monday, Oct. 24, 2016

     C14.txt,

     Contains procedures:

     • P(n): the list of (integer) partitons of n in non-increasing order

     • SYT(L): inputs a partition L and outputs the SET of all Standard Young Tableaux of shape L

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

     1. Using the identity

        arctan(x) -arctan(y)=arctan( (x-y)/(1+x*y))    (corrected Oct. 24, 9:26pm, the previous version had a sign error, pointed out by Anthony Zalelski.)

        Write a procedure

        MakeMonthlyProblem(R,n)

        that inputs an expression R in the variable n, computes the simplified version of tan(arctan(R(n))-arctan(R(n-1))), and then poses a problem in the style of Problem 11930 in American Mathematical Monthly Problems for Oct. 2016. It should be written in a style ready to be submitted.

        What are

        • MakeMonthlyProblem(1/(2^n+1),n);
        • MakeMonthlyProblem(1/( 1+ sqrt(2^n+3)),n);
        • MakeMonthlyProblem(1/(n^3+1)),n);

     2. Write an enumeration analog of SYT(L), call it, NuSYT(L), that inputs a partition L (written as a weakly-inreasing list of POSITIVE integers), and outputs the nops(SYT(L)) (but running much faster, of course, so don't write a one-liner:

        nuSYT:=proc(L): nops(SYT(L)):end )

     3. Without peeking at the OEIS, conjecture closed-form expressions (in n) for

        nuSYT([n,n])   ,   nuSYT([n,n,n])   ,   nuSYT([n,n,n,n])   ,

        then check them out in the OEIS.

     4. Using P(n) and the above mentioned nuSYT(L), write a procedure

        SumSYTpower(n,k) ,

        that inputs positive integers n and k, and outputs the integer

        a_k(n):=Sum(NuSYT(L)^k, L in P(n)) ,

        Can you conjecture an explicit expression, in n, for a_1(n)?, a_2(n)?, a_3(n)? Are any of them in the OEIS?

     5. Read and understand pp. 1-5 of Ian Macdonald's classic book

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

     ---

     Programs done on Thursday, Oct. 27, 2016

     C15.txt   .

     Contains procedures:

     • P(n): the list of (integer) partitons of n in non-increasing order

     • ApplyPi(f,x,n,pi): inputs f, x, n, pi, where f is an expression in x[1],...,x[n] pos. integer n, letter x, and a permutation pi of {1, ...,n}, applies x[i]->x[pi[i]] to f

     • Sym(f,x,n): inputs an expression f in the indexed variables x[1], ..., x[n], a letter x, and a positive integer n, outputs the symmetrizer

     • mL(x,L,n): inputs a letter x, a partition L, and a positive integer n (≤ nops(L)), outputs the monomial symmetric function m_L(x1, ..., xn)

     • IsSym(f,x,n): inputs f and x (a lettter), where f is an expression in x[1],..., x[n], n pos.int. outputs true iff f is symmetric

     • ToM(f,x,n,M): inputs a symmetric polynomial f in x[1]..., x[n] outputs it as a linear combination of M[L], where M is a symbol
       [finished after class to account for the case when f is a monomial]

     • eL(x,L,n): the symmetric function mul(e_L[i], i=1..nops(L))

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

     1. Write a procedure

        Conj(L)

        that inputs a partition, L, and outputs its conjugate partition. For example, "Conj([3,2]);" should return [2,2,1]

     2. Write a procedure

        Check17(L,m,n)

        that confirms Statement (1.7) on p.3 of Ian Macdonald's book, for a partition L and integers m ≥ L[1], and n ≥ nops(L) (alias L'[1])

     3. Write a procedure

        eTomMatrix(n)

        that inputs a positive integer n, and outputs a nops(P(n)) by nops(P(n)) matrix, represented as a list of lists, let's call it MAT, such that MAT[i][j] is the coefficient of mL[P[j]] in eL(x,P[i],n).

        What are: eTomMatrix(n1), n1=1..7 ?

        [Warning: Please use the current version of C15.txt that has been modified after class, or else ToM will not run properly]

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

     ---

     Programs done on Monday, Oct. 31, 2016

     C16.txt

     Contains procedures:

     • IaB(L,a): inputs a (weakly) increasing sequence of positive integers, L, and another integer a, places a in its right place,and outputs the bumped entry or 0 (if a>=max(L)) [NewRow,BumpedEntry]

     • OneStepRS(T,a): One step of the famous Robinson-Schensted(-Knuth) algorithm. Inputs a tableau with positive integers and a another positive integer, inserts a in its proper place (getting a tableau of a larger shape) it also returns the index of the row that got larger by one box

     • RSK(pi): applies the famous Robinson-Schensted (Knuth) correspondence to to the perm. pi. The output is a pair [T1,T2] of Standard Young Tableaux of the same shape

     • RSKv(pi): Verbose version of RSK(pi)

     • Shape(T):The shape of the tableau T

       Shape:=proc(T) local i: [seq(nops(T[i]),i=1..nops(T))]: end:

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

     1. Using procedure SYT(L) and P(n) from C14.txt, write a procedure

        SameShapePairs(n)

        that inputs a positive integer, n, and outputs the set of all pairs of standard Young Tableaux of the same shape.

        Write a one-line procedure

        VerifyRSK(n)

        that verifies that the range of the Robinson-Schensted Correspondence is indeed SameShapePairs(n). Check it up to n=8.

     2. Write a procedure

        Invert1(pi)

        that inputs a permutation pi and outputs its inverse.

     3. Verify empirically that if RSK(pi)=[T1,T2], then RSK(pi^(-1))=[T2,T1] for n up to 8

        Use this fact to deduce that the number of Standard Young Tableaux with n boxes equals the number of involutions (permutations that are equal to their inverse) of n.

     4. [Human Challenge] Prove, by human means that indeed

        RSK(pi)=[T1,T2] iff RSK(pi^(-1))=[T2,T1]

     5. [Programming and Algorithmic Challenge] Write a procedure

        iRSK(TableuxPair)

        tnat inputs a pair of Standard Young Tableaux of the same shape TableuxPair=[T1,T2] and outputs a permutation pi such that iRSK(RSK(pi))=pi

        Verify that both RSK(iRSK) and iRSK(RSK) are the identity mappings on their respective domains (i.e. SameShapePairs(n) and permute(n), respectively, for n ≤ 8

     Added Nov. 7 2016: See the students' nice solutions.

     ---

     Programs done on Thurs., Nov. 3, 2016

     C17.txt

     Contains procedures:

     • Com(n,k): the set of lists of length k of non-neg. integer that add-up to n

     • Con(L): inputs a list of non-neg. integers L, of length 6, indicating how many voters voted ranked candidates 1,2,3,
       123,132, 213,231,312,321
       respectively, and outputs true iff it is a (strict) Condorcet scenario 1->2->3->1 or 1->3->2->1

     • ConS(n): inputs n (the number of voters each randking three candidates) outputs the set of all vectors of length 6 that sum up to n and exhibit the Condorect paradox

     • OddSeq(N): the the sequence counting the Condorect scenarios for n=1..2*N-1 for odd n

     • RV(): generates one of [1,0$5], ..., [0$5,1] each with prob. 1/6

     • MCcon(n,N) : Simulates N elections with n voters, and outputs the ratio of those elections that ended up with a Condorcet scenario

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

     1. Write a procedure

        Con1G(L,c1,c2,c3)

        that inputs a list L of length 6 indicating how many voters vote, respectively for the rankings 123,132,213,231,312,321, and integers c1,c2,c3

        and outputs true iff
        the number of voters who prefer 1 to 2 exceeds the number of voters who prefer 2 to1 by least c1
        the number of voters who prefer 2 to 3 exceeds the number of voters who prefer 3 to 2 by at least c2
        the number of voters who prefer 3 to 1 exceeds the number of voters who prefer 1 to 3 by at least c3

        (Note that Con1G(L,1,1,1) is Con1(L) we did in class)

     2. Generalize procedures ConS(n) and OddSeq(N) to handle generalized Condorcet scenarios, call them ConSg(n,c1,c2,c3) and OddSeq(N,c1,c2,c3) to handle generalized Condorcet scenarios

     3. [I don't know the answer] Can you conjecture polynomial expressions for ConSg(2*n-1,0,0,0)?, how about some other ConSg(2*n-1,c1,c2,c3) for small values of c1,c2,c3?

     4. Generalize RV(), to write a procedure

        RVloaded(p)

        that inputs a prob. distribution [p123, ..., p321] and generates [1,0,0,0,0,0] with prob. p123, .... , [0,0,0,0,0,1] with prob. p321.

     5. Write a procedure

        MCconG(n,N,p) : that Simulates N elections with n voters, where the voters choose one of the six rankings according to p. and outputs the ratio of those elections that ended up with the Condorcet scenario.

        Note that MCconG(n,N,[(1/6)$6]) is the same MCcon(n,N).

        Play around with different choises of loaded dice. How do they differ from the outcome of the fair die?

     Added Nov. 7 2016: See the students' nice solutions.

     ---

     Programs done on Monday, Nov. 7, 2016

     C18.txt

     Contains procedures:

     • mToe(n): inputs a positive inetger n, and outputs the p(n) by p(n) transition matrix from the m-basis to the e-basis

     • Andrew(F,x,n): inputs a symmetric polynomial F, in x[1],..., x[n], and homog. of degree n, and ouputs the vector of coefficients when expressed in terms of the m's with the order given by P(n).

     • ToE(f,x,n,E): inputs a symmetric function f, homog. of total degree n, of x[1]. ..., x[n] and a positive integer n, and a symbol E, expresses it as a linear combination of the E-basis, where E[L] means e_L[1]*...e_L[nops(L)] add(v[i]*E[Pars[i]],i=1..nops(Pars)):

     • Toe(f,x,n,e): inputs a symmetric function f, homog. of total degree n, of x[1]. ..., x[n] and a positive integer n, and a symbol e, expresses it as polynomial expression in e[1],e[2],...,e[n] thereby confirming the fundamental theorem of Symmetric Functions that any summetric polynomial in x[1],..,x[n] of degree<=n can be thus expressed

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

     1. The fundamental full-homogeneous symmetric polynomial h_i (x₁,..., x_n) (where i ≤ n), may be defined as the sum of m_L(x₁, ..., x_n) over all partitions L of i . Write a procedure

        hni(n,i,x)

        that outputs h_i (x₁,..., x_n) with the above definition

     2. Another way of defining h_i (x₁,..., x_n) is as the coefficient of tⁱ in the Taylor expansion (about t=0) of 1/((1-x₁*t)*...*(1-x_n*t)). Write a procedure

        Hni(n,i,x)

        that implement this definion. Convince yourself that they are the same, first by trying out small values of n and i, and then prove it humanly.

     3. Write an "h-analog" of procedure eL(x,L,n), call it hL(x,L,n), then write "h-analogs" of eTom(n) and mToe(n), call them, hTom(n) and mToh(n) respectively.

     4. The power-function fundamental symmetric function p_i(x₁,...,x_n) is defined by

        p_i (x₁, ..., x_n)= x₁ⁱ + ... + x_nⁱ

        Write a "p-analog" of eL(x,L,n), call it pL(x,L,n), then write "p-analogs" of eTom(n) and mToe(n), call them pTom(n) and mTop(n)

     5. [Corrected Nov. 10, 2016, thanks for Jinyoung Park] Write a procedure

        TransMatrix(n,base1,base2,m,e,h,p)

        where base1, base2, are members of the set {m,e,h,p} , and outputs the transition matrix from the base1 basis to the base2 basis. Of course, if base1=base2 you would get the identity matrix, so for each n, you get 12 non-trivial matrices.

        Print out all these 12 matrices for n from 1 to 6 (in an organized manner)

     6. Read and understand Dr. Z.'s proof from the book proof of Newton's identities relating the e's and the p's. Then implement it in Maple, and check that it is indeed an involution.

     Added Nov. 14 2016: See the students' nice solutions.

     ---

     Programs done on Thurs., Nov. 10, 2016

     C19.txt

     contains procedures:

     • inv1(pi): the number of inversions of the permutation pi

     • AS(f,x,n): the anti-symmstrizer of the function f of x[1], ..., x[n]

     • sL(L,x): Inputs an integer partition L (of n, say) and a letter x outputs the Schur symmetric polynomial s_L(x1, ..., xn)

     • sLm(L,M): s_L(x) in terms of the Monomial Symmetric Functions

     • sLe(L,E): s_L(x) in terms of the e-basis

     • TabsNoGood(L,k): a failed attempt to write a procedure that inputs a partition L and a positive integer k and outputs the set of all (column-strict) tableaux of shape L using {1, ..., k}

       {DO NOT USE, FOR REFERENCE ONLY]

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

     1. [Human] Read and try to understand the proof of the surprising fact that if RSK(pi)=[T1,T2] then RSK(pi^-1)=[T2,T1] given in Guru Donald Knuth's legenedary Section 5.1.4 from the Art of Computer Programming, v. 3.

     2. [Human] Prove Netto's theorem that the weight-enumerator of the set of permutations of length n is the q-analog of n! (1)(1+q)...(1+q+...+q^(n-1)

     3. [Challenge] Write a procedure, Tabs(L,k), that inputs a parition L and a positive integer k (>=nops(L)) and outputs the set of column-strict tableaux of shape L whose largest entry is k.

        Comment: As Justin noticed the attempt in class was flawed.

     Added Nov. 14 2016: See the students' nice solutions.

     ---

     Programs done on Monday, Nov. 14, 2016

     C20.txt

     contains procedures:

     • Tabs1BE(L,k,maxLine): (written by Bryan Ek (who won a dollar in the contest for the fastest program)) Inputs partition L, positive integer k>=nops(L) and maxLine. Outputs the set of all (column-strict) tableaux of shape L using {1,..,k}. k is guaranteed to be in the tableaux but must appear at or "below" the maxLine.

     • TabsBE(L,k): (also written by Bryan Ek (who won a dollar in the contest for the fastest program)) Inputs partition L and positive integer k. k>=nops(L) otherwise you receive the emptyset. Outputs the set of all (column-strict) tableaux of shape L using {1,..,k}.

     • Wt(L,x): the weight of a tableau L (the product of x[entry] over all entries)

     • sLc(L,x): the Schur polynomial s_L(x[1], ..., x[n]) (where n=size of L) using the combinatorial definition (but first constructing the set of tableaux (with Byran Ek's efficient code) and then summing all the weights.

     • Coe(f,x,v): inputs a polynomial f, in x[1], ..., x[n] (n=nops(v))and a vector v of length n outputs the coeff. of x[1]^v[1]*... x[n]^v[n]

     • TabsBEw(L,k,x): weighted analog of TabsBE(L,k), without constucting the set, but using the same logic (using a weighted analog of Bryan Ek's code for TabsBE(L,k), guided by Andrew Lohr)

     • sLcF(L,x): inputs a partition L and a letter x, and outputs the Schur polynomial corresponding to L, S_L(x1, .., xn) (where n is the size of L) much faster then sLc(L,x), using TabsBEw(L,convert(L,`+`),x).

     ---

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

     1. Write procedures, sLd1(L,x) and sLd2(L,x), implementing the determinental equations 3.4 and 3.5 , respectively, for the Schur polynomials on p. 41 of Ian Macdonald's great book.

     2. Write procedures

        ChecksLd1(n) and ChecksLd2(n)   ,

        that checks that sLd1(L,x) and sLd2(L,x) coincide with sLcF(L,x) for all the partitions of n. What is the largest n that you could verify it for (in a reasonable amount of time)

     3. The major index of a permutation, pi, maj(pi), is the sum of the places,i, where pi[i]>pi[i+1]. For example,

        maj(4132657)=1+3+5=9   .

        Can you conjecture a nice expression for the weight-enumerator of the set of permutations of {1, ...,n} (i.e. the sum of q^maj(pi) taken over all permutations pi of {1, ..., n})?

     4. [Human Challenge (no peeking!)] Can you prove your conjecture from the above problem 3?

     Added Nov. 21 2016: See the students' nice solutions.

     ---

     Programs done on Thursday, Nov. 17, 2016

     C21.txt

     contains procedures:

     • BW2(a,b):The number of Young Tableaux of shape [a,b] (or walks from [0,0] to [a,b] always staying in x>=y

     • BW2a(m1,m2): BW2(m1+m2,m2)/binomial(m1+2*m2,m2)

     • GuessBW2(a,b): guesses a closed-form formula (from scratch) for the number of Young tableaux f shape [a,b]

     • GuessAndProveBW2(a,b): guesses a closed-form formula (from scratch) for the number of Young tableaux of shape [a,b] and then proves it

     • BW3(a,b,c) The number of Young Tableaux of shape [a,b,c] (or walks from [0,0,0] to [a,b,c] always staying in x>=y>=z>=0)

     • BW3a(m1,m2,m3): BW3(m1+m2+m3,m2+m3,m3)/((m1+m2+m3+(m2+m3)+m3)!/((m1+m2+m3)!*(m2+m3)!*m3!))

     • GuessBW3(a,b,c): guesses a closed-form formula (from scratch) for the number of Young tableaux of shape [a,b,c]

     • GuessAndProveBW3(a,b,c): guesses a closed-form formula (from scratch) for the number of Young tableaux of shape [a,b,c]

     • GR(DS,n): guesses a rational function for the data set DS {[a,b]}

     • GRm(DS,k,n): inputs a set of data of the form [pt,Value] guesses a rational function in n[1], ..., n[k] fitting the data

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

     1. Write the four-dimensional analog of GuessAndProveBW3(a,b,c), call it

        GuessAndProveBW4(a,b,c,d)

        (it may take a bit longer then GuessAndProveBW3(a,b,c))

     2. By looking at the outputs of GuessBW2(a,b),GuessBW3(a,b,c), GuessW4(a,b,c,d), guess a general formula for

        F_k(a1, ..., ak)

        for the number of Young tableaux of shape (a1, ..., ak) (where a1>=...>ak>=0) and program it into a general procedure

        Fk(k,a)

        in terms of a[1], ..., a[k]

     3. By using Fk(k,a), write a procedure

        ProveYoungFrobeniousMacMahon(k)

        that inputs a positive integer k, and outputs true iff the formula for Fk(k,a) is true (supplying a rigorous proof for this particular k). How high can you get k to be.?

     4. [Hard Human challenge (unless you peek at Knuth)] Prove it for general dimension k

     5. Look up the "Hook Length Formula", find out what "hook-length" of a cell it, and prove, humanly, that the formula that you found for Fk(k,a) is equivalent to the Hook Length Formula.

     6. [Optional challenges] Try to solve as many as possible problems from American Mathematical Monthly Problems for Nov. 2016
        [possible hint to problem 11939: Apply theorem 2, on p. 119 (or p.133 in the on-line .pdf file) Herb Wilf's masterpiece , to rigorously prove the fact that the answer is 0]

     Added Nov. 21 2016: See the students' nice solutions.

     ---

     Programs done on Monday, Nov. 21, 2016

     C22.txt ,

     contains procedures:

     • Kids(L): inputs an integer partition L (a non-increasing list of positive integers) and outputs the set of paritions obtained by (legally) decreasing one of the parts by 1. The output is a list of pairs of the form [L1,i] where L1 is the "kid" and i is the row that changed.

     • F(L): the number of Young tableaux of shape L, via the recurrence

     • LD(R): [suggested by Andrew Lohr] inputs a list of positive integers R, and outputs a random integer from 1 to nops(R), such that the prob. of getting i is R[i]/convert(R,`+`):

     • RYT(L): inputs a shape (alias partition) L, and outputs a (unfiormly at) random Standard Young Tableau of shape L

     Homework for Monday, Nov. 21, 2016, class (due Sunday Nov. 27, 10:00pm)

     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 in the second line
     #YourName, Math 640 (Fall 2016) homework assignment 22

     1. Write a procedure

        Ffast(L)

        that has the same input and output as F(L) (i.e. it inputs a shape and outputs the number of standard Young tableaux of that shape) but that uses the Young-Frobenius-MacMahon formula rather than the recurrence., and then use it to write

        RYTfast(L)

        that does the same thing as RYT(L) (i.e. it inputs a partition and outputs a random SYT of that shape), but using Ffast(L) rather than F(L). What is faster

        RYT([20$10]) or

        RYTfast([20$10])   .

     2. Use the Herbert Wilf methodology (analogous for what we did in class) to write a procedure

        RandSetnk(n,k)

        That inputs positive integers k,n (k<=n), and outputs a subset of {1,...,n} with k elements, each with prob. 1/binomial(n,k) .

     3. Use the Herbert Wilf methodology (analogous for what we did in class) to write a procedure

        RandPar(n)   ,

        that inputs a positive integer n, and outputs a random (integer) partition of n.

        [Hint, let pnk(n,k) be the number of partitions of n with largest part k, use the fact that

        p(n)=Sum(pnk(n,k),k=1..n)

        and the obvious recurrence for pnk(n,k) in terms of pnk(n-k,s) for s<=k   .

     4. Use the Herbert Wilf methodology to write a procedure

        RandSetPartition(n)

        that inputs a positive integer n, and outputs each of the Bell(n) set-partitions of {1,..,n} with prob. 1/Bell(n)

        Hint: You may use the recurrence

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

        and use, as a subroutine RandSetnk(n,k) above (with n replaced by n-1)   .

     Added Nov. 28 2016: See the students' nice solutions.

     ---

     Programs done on Tuesday, Nov. 22, 2016

     C23.txt ,

     contains procedures:

     • Conj(L): the conjugate partition of L (due to Yonah Biers-Ariel)

     • Boxes(L): inputs a partition,L, and outputs the set of boxes of L

     • Hook(L,b): inputs a shape L, and a box b and outputs the hook of b

     • GNW(L): inputs a shape L and outputs a (unifomly at) random Standard Young Tableau of shape L using the AMAZING Greene-Nijenhuis-Wilf algorithm

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

     1. Read and understand the Greene-Nijenhuis-Wilf proof (based on their algorithm) of the famous Hook-Lengths Formula.

     2. Write a procedures

        AveTimeRYTfast(L,N) , AveTimeGNW(L,N)

        that inputs a (rather large) partition L, and a (rather large integer N), runs the procedure RYTfast(L) (from hw22.txt) N times, and finds the average running time (by using the Maple command time()), and ditto for procedures GNW(L).

        What did you get for

        AveTimeRYTfast([50$50],30) and AveTimeGNW([50$50],30)?

        Who won. If these numbers are small, try to make L larger.

     3. Get ready for next class by reading pages 1-6 of Yusra Naqvi's fascinating article .

     Added Nov. 28 2016: See the students' nice solutions.

     ---

     Programs done on Monday, Nov. 28, 2016

     C24.txt ,

     contains procedures:

     • sToMvector(L):inputs a partition L and outouts a list of numbers giving the coeff. of M[P(n)[i]]:

     • sToHvector(L):inputs a partition L and outouts a list of numbers giving the coeff. of H[P(n)[i]]:

     • MonToV(Mo,H,n): inputs a monomial Mo in H[1], ..., H[n] and outputs c*H[L] where c is the coefficient and L is the decreasing degree sequence

     • PolToV(Pol,H,n): inputs a polynomial Pol in H[1], ..., H[n] outputs it as linear combination of H[L]

     • ProveOrt(n): inputs a pos. integer n and outputs true if (4.8) on p. 35 of Macdonald (1st)

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

     1. Write a procedure

        InnerProd(n)

        that inputs a positive integer n, and outputs the nops(P(n)) by nops(P(n)) matrix (expressed as a list of lists) let's call it L, such that L[i][j] is the inner product of m_P(n)[i] and m_P(n)[j] under the inner product defined by eq.(4.5) (p. 63) of Macdonald's Symmetric Functions Book .

        [Note added Dec. 1, 2016: Jinyoung Park and Yonah Biers-Ariel noticed that this matrix already exists in this class. Which one?]

     2. Yet another definition of the Schur polynomial basis is that s_L is a linear combination of m_L' for L'-s that come after it in the ordering given by P(n), and that they are an orthorormal basis with respect to the above-mentioded inner product. By using the above procedure, write a procedure

        sLA(L,M)

        that inputs a partition L and outputs s_L expressed in terms of the M's. For small n, check that it coincides with the other definitions of Schur polynomials.

        [Note added Dec. 1, 2016: You may want to use the Gram-Schmidt orthogonality algorithm]

     Added Dec. 5, 2016: See the students' nice solutions.

     ---

     Programs done on Thursday, Dec. 1, 2016

     C25.txt ,

     contains procedures:

     • aLg(L,x,m): inputs a partition L of n, say, a variable x, and m>=n outputs the numerator of the famous Schur polynomial s_L(x[1], ...., x[m])

     • sLg(L,x,m): inputs a partition L of n, say, a variable x, and m>=n outputs the famous Schur polynomial s_L(x[1], ...., x[m])

     • LWc(L,M,N): inputs partitions L,M,and N such that |N|+|M|=|L| and outputs The Littlewood-Richardon coeff., namely the coeff. of s_L in the product s_M*s_N Done directly from the definition

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

     1. [Optional, it turns out that we don't need this for the sequel]

        Modify procedure TabsBE(L,k) from C20.txt (reproduced in C25.txt) to write a procedure

        TabsBEg(L,M,k)

        that inputs partitions L and M and a positive integer k, and outputs the set of column-strict tableaux of skew-shape L\M with largest integer k.

     2. There is a trivial 1-1 correspondence between Standard Young Tableaux of shape N=[N1,N2,N3..] and words with N1 1's, N2 2's, N3 3's.. that are "ballot words", i.e. the have the property that for every prefix the number of 1's is always >= the number of 2's >= the number of 3's ...

        Write a procedure

        SYTtoBallotWord(N)

        that implments it.

     3. By using the above, or otherwise, write a procedure

        BW(N)

        that inputs a partition N and outputs the set of ballot words with N[1] 1-s., N[2] 2-s, etc.

        A Littlewood-Richrardson tableau of shape L\M and weight N is any way if filling-in a member BW(N) into the cells of the skew-shape L\M in "Arabaic" (or Hebrew), i.e. from right-to-left and from top-to-bottom such that the resulting skew-tableau is column-strict. Write a procedure

        LR(L,M,N)

        that inputs partitions L and M (where M is a sub-partition of L) and a partition N such that |N|=|L|-|M|, and outputs the subset of BW(N) such that if you fill-in L\M as above you get a Littlewood-Richardson skew-tableau of shape L\M.

     4. Write a procedure

        CheckLRrule(n)

        that inputs a positive integer l, and checks that

        nops(LR(L,M,N))=LWc(L,M,N)

        for every partition L of l, and for all partitions M and N such that |M|+|N|=l

        Thereby proving, experimentally, the famous Littlewood-Richardson rule for all partitions L of l.

        How far can you go in a reasonable ammount of time?, i.e. what is the largest l? that finishes in less than 10 minutes?

     Added Dec. 5, 2016: See the students' nice solutions.

     ---

     Programs done on Monday, Dec. 5, 2016

     C26.txt ,

     contains procedures:

     • ToMv(f,n,M):inputs a linear combination,f, of M[p] and outputs its vector of coefficients in the order given by P(n) (the list of partitions of n in reverse lex-order).

     • Da(f,x,n,a): the differential operator used to define Jack polynomials
       [see the bottom of p. 4 in Yusra Naqvi's nice article]

     • DaM(a,n): the matrix version of Da, a p(n) by p(n) matrix whose i-th row is the vector of coefficients of P(n) of Da(mL(P(n)[i]):

     • JackM(a,n): the p(n) by p(n) matrix whose i-j entry is the coeff. of M[P(n)[j]] of J[P(n)[i]]:

       [Note, right now it is not in order, one of the homework problem is to finish it up]

       [Added Dec. 7, 2016: Justin Semonsen noticed (and won a dollar), that it is even more incomplete than what I believed before. It tacitcly assumes that all the eigenvalues of the matrix DaM(a,n) have multiplicity 1. As pointed out by Andrew, this is false for n=6. I beleive that using the renormalization one can "diagonalize" the eigenspaces with dimensions larger than 1, so that's another challenge].

     • Dqt(f,x,n,q,t): the q-differential operator used to define Macdonald polynomials
       [see the top of p. 5 in Yusra Naqvi's nice article]

     • DqtM(q,t,n): the matrix version of Dqt, a p(n) by p(n) matrix whose i-th row is the vector of coefficients of P(n) of Da(mL(P(n)[i]):

       MacM(q,t,n): the p(n) by p(n) matrix whose i-j entry is the coeff. of M[P(n)[j]] of Macdonald_{q,t}[P(n)[i]]:

       [Note, right now it is not in order, one of the homework problem is to finish it up]

       [Added Dec. 7, 2016: The above phenomenon, noticed by Justin Semonsen does not occur for n=6, but I am not sure whether it starts showing up for larger n].

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

     1. Finish up procedures JackM(a,n) and MacM(q,t,n), so that the output is the upper-triangular matrix that we really want PLUS, with the normalization where the diagonal entries are all 1. (the so-called monic Jack polynomials).

        Added Dec. 7, 2016 (as pointed out above, you first have to correct the error we did in class where we tacitly assumed that all the eigenspaces are one-dimensional, so this problem is more challenging than I thought.

     2. Verify for all Jack polynomials for all partitions L with |L|<=7 that indeed the limit of P_L(t^a,t) at t goes to 1 is the monic Jack polynomial.

     3. [Human Challenge, five dollars to be divided, NO PEEKING]
        Prove that the number of permutations of {1, ..., n} that avoid the pattern acb is given by the Catalan number (2n)!/(n!(n+1)!).

     4. [Human Challenge, ten dollars to be divided, NO PEEKING]
        Find a nice bijection between abc-avoiding permutations of length n and acb-avoiding permutations of length n.

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

     ---

     Programs done on Thurs., Dec. 8, 2016

     C27.txt ,

     contains procedures:

     • redu(L): inputs a list of numbers, and outputs the reduction as a permutation of nops(L)

     • IV(n,k): the set of increasing vectors of length k in {1, ...,n} ending in n

     • IsBad1(pi,p): inputs a perm. pi and a pattern p outputs true iff pi contains the pattern p where the last entry of pi participates

     • IsBad(pi,P): inputs a permutation pi and a set of patterns P and outputs true if it contains at least one member of P

     • GG(n,P):inputs a non-neg. integer n and a set of patterns P and outputs the set of permutations avoiding the patterns of P

     • SeqGG(P,N): inputs a set of patterns P, and a positive integer N returns the list of length N whose i-th entry is the NUMBER of permutations of length i NOT containing any of the patterns in P

     • GP1(L,n,d): inputs a list of pairs [input,output], and a variable n and outputs a polynomial of degree d such P(input)=output (from C9.txt)

     • [Added after class] GP(L,n): inputs a list of pairs [input,output], and a variable n and outputs a polynomial of degree <=nops(L)-2 such P(input)=output (or returns FAIL, if none exists)

     Homework for Thurs., Dec. 8, 2016, class (due Sunday Dec. 11, 10:00pm)

     Please email ShaloshBEkhad at gmail dot com an email with

     Subject: hw#27

     and an attachment

     hw27FirstNameLastName.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 27

     1. Write a procedure

        HowMany(pi,p)

        that inputs a permutation pi and a pattern, p, and outputs the number of occurrences the pattern p occurs in pi. Note that if Howmany(pi,p)=0 then pi avoids p.

     2. Write a procedure

        GGgen(Pset,n)

        that inputs a set of pairs, Pset, where each member is a pair [p,a_p], where a_p is a nonnegative integer, and a positive integer n, and outputs the set of permutations of length n such that for each member [p,a_p] of Pset, the number of occurrences of the patter p is <=a_p. If all the a_p=0 then we are back to pattern-avoidance.

     3. Write a procedure

        SeqGGgen(P,N), where P is as above, and N is a positive integer, and outputs the list of cardinalities of GGgen(Pset,i) for i from 1 to N.

     4. Which of the following ones are already in the OEIS?
        • SeqGGgen({[[1,2,3],1]},8);

          [i.e. the number of permutations of n with at most one occurence of the pattern 123]. What about SeqGGgen({[[1,2,3],1]},8)-SeqGGgen({[[1,2,3],0]},8), the number of permutations of n with EXACTLY one occurence of the pattern 123].

        • SeqGGgen({[[1,2,3],2]},8);

          [i.e. the number of permutations of n with at most two occurence of the pattern 123]. What about SeqGGgen({[[1,2,3],2]},8)-SeqGGgen({[[1,2,3],1]},8), the number of permutations of n with EXACTLY two occurence of the pattern 123].

        • SeqGGgen({[[1,3,2],1]},8);

        • SeqGGgen({[[1,3,2],2]},8);

        • SeqGGgen({[[1,3,2],1],[[1,2,3],1]},8);

        • SeqGGgen({[[1,2,3,4],1]},8);

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

     ---

     Programs done on Monday, Dec. 12, 2016

     C28.txt ,

     contains procedures:

     • An(n): The set of permutations of {1...n} defined by

       Big(i-1) n Small(n-i)

     • PatA1(pi,k): all the patterns of size k avoided in the permutation pi

     • PatA(S,k): the set of patterns of length k avoided by ALL the members of S

     Class Project, due Jan. 15, 2017

     Added March 21, 2017: Here is the joint paper the whole class wrote as a final project.

     Every team sent their part of the paper, and their part of the Maple code to the coordinating author, Richard Voepel, who comined them into a coherent paper, and a coherent website.

     It is also available from arxiv.org, so it it for ever part of the eternal corpus of mathematical knowledge, and the students whose Erdos number was previously either infinite, or larger than three, has now Erdos number three.

     ---

     Added Jan. 8, 2017: Read the students' evaluations.

     ---

     Dr. Z.'s teaching page