Math 640: EXPERIMENTAL MATHEMATICS Spring 2008 (Rutgers University) Webpage

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

Last Update: Oct. 11, 2008.

Added Oct. 11, 2008: Here are the awsome final projects done by the students

Description

Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in this 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'll decide to do research in.

We will first learn Maple, and how to program in it. This semester we will explore Automated (symbolic!) Enumeration, that consists of teaching the computer how to find explicit formulas, and/or general algorithms, for enumerating combinatorial objects. But the actual content is not that important, it is mastering the methodology of computer-generated and computer-assisted research that is so crucial for your future.

There are no prerequisites, and no previous programming knowledge is assumed. Also, very little overlap with previous years. The final projects for this class may lead to journal publications.

Here are the suggested final projects .

Diary and Homework

Programs done on Thurs., Jan. 24, 2008

Homework for Thurs., Jan. 24, class (due Jan. 28, 2008)

  1. Read and do all the examples, plus make up similar ones, in the first 30 pages of Frank Garvan's awesome Maple booklet.
  2. Write a Maple program that inputs positive integers a and K and prints out all the integers n, less than K that are not prime, yet satisfy an mod n = a .

Programs done on Mon., Jan. 28, 2008

Homework for Mon., Jan. 28, class (due Thurs., Jan. 31, 2008)

Programs done on Thurs., Jan. 31, 2008

Homework for Thurs. Jan. 31, class (due Mon., Feb. 4, 2008)

Programs done on Feb. 4

Homework for Feb. 4 class (due Feb. 7)

Programs done on Feb. 7 class

Homework for the Feb. 8, class (due Feb. 11, 2008)

Programs done on Feb 11 class

Homework for Feb 11 class (due Feb 14)

Programs done on Feb. 14, 2008, class

Homework for Feb 14 class (due Feb. 21)

Programs done on Feb 18, 2008

(Guest Lecturer: Eric Rowland, made a comparative study of Maple vs. Mathematica)

feb18.nb

Homework (To be handed-in to Eric, due Feb. 25, 2008)

  1. Take a simple function that you've written recently, and rewrite it (in your language of choice) using functional (rather than procedural) constructs.
  2. At 3am early Monday morning you discover that the Riemann hypothesis reduces to the statement that all triangle-free Hamilton-connected graphs with 7 vertices satisfy a certain simple condition. Use GraphData[ ] to find all graphs that you need to check. Will you be able to get eight hours of sleep and still make it to Experimental Math on time?
  3. Make something cool with Manipulate[ ], and if it's sufficiently cool then upload it to the Demonstrations Project.

Program done in Feb. 21, 2008 class

feb21.txt (Under construction, to be completed next time)

Homework for Feb 21, 2008 (due Feb. 25, 2008)

Program done on Feb. 25, 2008 class

Recommended Reading: Enumerating Totally Clean Words by Dr. Z., that outlines the algorithm for counting words that omit (as subwords) a given set of "dirty" words.

feb25.txt, contains

Homework for Feb. 25, 2008 (due Feb. 28, 2008)

Program done on Feb. 28, 2008, class

feb28.txt, contains

Homework for Feb. 28, 2008 (due March 3, 2008)

For everyone (Note: from now on everybody has the same homework, but I will understand if new-comers won't do everything).
  1. Adapt gAFt(A,F,t) to write a program gAFtx(A,F,t,x) that has the same input as gAFt(A,F,t) and in addition another symbol x, and outputs the rational function in (t,x[A[1]],x[A[2]], ... ) whose Maclaurin expansion in t has for its coefficient of tn the POLYNOMIAL in (x[A[1]],x[A[2]], ...) that is the weight-enumerator of the set of n-letter words in A, avoiding F, where the weight of a word w is x[w[1]]x[w[2]]... (for example, the weight of ESSEX is x[E]x[S]x[S]x[E]x[X]= x[E]2x[S]2x[X]).
    For example, gAFtx({1,2},{},t,x); should be 1/(1-t*(x[1]+x[2]));
  2. Adapt gAFt(A,F,t) to write a program gAFts(A,F,t,s) that has the same input as gAFt(A,F,t) and in addition another symbol s, and outputs the rational function in (t,s ) whose Maclaurin expansion in (t,s) has for its coefficient of tnsm the number of n-letter words in the alphabet A, that have exactly m mistakes. Note that gAFts(A,F,t,0) should equal gAFt(A,F,t).
    For example, gAFts({1,2},{[1,2]},t,s); should be 1/(1-2*t-(s-1)*t^2);
    Hint: replace -1 by (s-1) in gAFt(A,F,t) (and/or its subroutines)
  3. Write a test program Test(r,m,k), that inputs integers r and m and k, that verifies that fAFt and gAFt yield the same output, for A={1,2,...,r}, and for EVERY possible k-element set of m-lettered "dirty words" and see who is faster
    For A={1,...,r} each such F
    t0:=time(): read `feb25.txt`: a:=fAFt(A,F,t); time()-t0;
    t0:=time(): read `feb28.txt`: b:=gAFt(A,F,t); time()-t0; evalb(a=b);
    Actually run Test(2,3,3); and if you can Test(2,3,4);
  4. Adapt gAFt(A,F,t), to write a program gPFt(P,F,t), that inputs a probability vector P (whose length is the length of the alphabet) and where P[i] is the prob. that the ith letter shows up, and outputs the rational function whose Maclaurin expansion, yields, as coeff. of tn, the prob. that a random n-letter word will not contain any occurrence of the "dirty words" of F.
  5. Look up the frequencies of English letters, and determine the probability that a 200-letter random "word" in English is SEX-less.
  6. (5 dollar reward for the champion). Find an example of A and F where gAFt(A,F,t) beats, in running time fAFt(A,F,t) by as big a factor as possible (or vice versa).

Programs done on March 3, 2008, class

mar3.txt, contains

Homework for March 3, 2008 (due March 6, 2008)

  1. Print out, and carefully read Dr. Z.'s crash course on enumerative combinatorics
  2. Modify G(n) to write a program Gnk(n,k), that inputs pos. integers n and k, and outputs the set of simple labelled graphs on {1, ..., n} with exactly k edges.
  3. Modify CG(n) to write a program CGnk(n,k), that inputs pos. integers n and k, and outputs the set of simple connected labelled graphs on {1, ..., n} with exactly k edges.
  4. Compute [seq(nops(CGnk(n,n-1)),n=1..7)], and conjecture an explicit expression for the number of connected labelled graphs with n vertices and n-1 edges.
  5. Write a program, called Image(G,n,pi) that inputs a labelled grap G on the set of vertices {1, ..., n} and a permutation pi on {1, ..., n} and outputs the graph on {1, ..., n} obtained by renaming i by pi[i] (for all i=1...n).
  6. Using permute(n) of the combinat package, write a program Images(G,n), that inputs a labelled graph G on {1, ..., n} and outputs the set of all images of G under permutations of {1, ..., n}
  7. An unlabeled graph on n vertices may be viewed as an equivalence class of labelled graphs on {1, ..., n} under the equivalence relation "being an image under a permutation". So you can represent an unlabeled graph as a set of labelled graphs. For example the equivalence class of
    {[1,2],[1,3}} is
    {{[1,2],[1,3}}, {[1,2],[2,3}}, {[1,3],[2,3}}} .
    Write a program ULCGnk(n,k), the inputs pos. integers n and k, and outputs all unlabeled connected graphs on n vertices and k edges.
  8. Compute [seq(nops(ULGCnk(n,n-1)),n=1..7)]: and search for it in Sloane.
Congratulations to Eric Rowland for winning the $10 prize for the longest Goulden-Jackson-style cluster

Programs done on March 6, 2008, class

Homework for March 6, 2008 (due March 10, 2008)

  1. Modify UCG(n) of mar6.txt, to write a program UCGe(n,e) that inputs pos. integers n and e, and outputs the "set" of unlabeled graphs on n vertices and n-1+e edges. For example, UCGe(n,0) should give the set of unlabeled trees on n vertices (or rather one representative labelled tree from each equivalence class)
  2. Modify NuUCGs(n) in mar6.txt, to write a program NuUCGse(n,e) that inputs pos. integers n and e, and outputs the counting sequence, from i=1 to i=n for the number of unlabeled trees on n vertices and n-1+e edges. For example, NuUCGse(n,0) should give the sequence for the number of unlabeled trees on i vertices for i from 1 to n .
    Look up NuCGse(6,0); in Sloane
  3. Finish up RT(S) of mar6a.txt, as follows.
  4. Write a procedure, SetPartition(S, i), that inputs a set S and a pos. integer i, and outputs the set of set-partitions of S into i disjoint (non-empty sets). For example, SetPartition({a,b,c},1); should give {{{a,b,c}}}, SetPartition({a,b,c},2); should give { {{a,b},{c}},{{a,c},{b}},{{b,c},{a}} }, while SetPartition({a,b,c},3); should give { {{a},{b},{c}} }.
    Hint: As usual, use recursion, (with option remember!) Look at the largest element (n:=max(op(S))). It is either a singleton, so you take a member of SetPartition(S\n,i-1) and add to it the singleton {n}, or it can be joined to one of the already existing sets of any set-partition in SetPartion(S\n,i);
  5. Write a program Combine(L) that inputs a list of "sets of sets" L=[S1,S2, ..., Sk] and outputs the set of all possible sets of the form
    s1 union s2 union ... union sk
    for all possible s1 in S1, s2 in S2, ..., sk in Sk
    For example Combine([{{a,b},{c,d}},{{e,f},{g,h}}]) should output { {a,b,e,f},{a,b,g,h},{c,d,e,f},{c,d,g,h}}
    Hint: Use recursion, i.e. do Combine([S1,S2,...,Sk]) by using Combine([S1,S2,...,S(k-1)]) and combining with Sk.
  6. Use the above to write RT(S)
  7. Write a procedure RTn(n) that inputs a pos. integer n and outputs all the rooted labelled trees on {1, ..., n}
  8. Find
    [seq(nops(TRn(n),n=1..7))];

Programs done on March 10, 2008, class

mar10.txt, contains RT(S): a program that inputs a set S and outputs the set of rooted trees on S (completed by Dr. Z. after class).

Homework for March 10, 2008 (due March 13, 2008)

Note: This is the version of 9:55am, March 11, 2008. (thanks to Paul Raff for pointing an error in the previous version). Please discard the previous version of the homework (in case you already downloaded it).
  1. Very Important: Read carefully Dr. Z's masterpiece, especially the introduction, section 1 and section 4.
  2. Look carefully at Combine(L,r) of mar10.txt, (finished by me after class), and convince yourself that it indeed does what it is supposed to do, and hence that RT(S) gives all rooted labelled trees on S. Note that the edges are now lists of length 2, and we consider them directed edges so [i,j] means i->j and [j,i] means j->i. By convention, in a rooted tree, all the edges point towards the root.
  3. Write a procedure Weight(a,T) that inputs a tree, and a letter a, outputs the product of a[op(edge)] over all the edges of T. For example,
    Weight(a,{[1,2],[2,3]});
    should yield
    a[1,2]a[2,3]
    (Hint: use mul):
  4. Write a program TW(n,i,a) that inputs a pos. integer n, another pos. integer i in {1,2, ..., n}, and a letter a, and outputs the sum of Weight(a,t) over all rooted trees [i,t], rooted at i. For example,
    TW(2,1,a);
    should yield a[2,1],
    while TW(2,2,a);
    should yield a[1,2],
    TW(3,1,a) should yield
    a[2,1]a[3,1]+a[3,2]a[2,1]+a[2,3]a[3,1]   ;
  5. (Correcting an error pointed out by Paul Raff, this is the corrected version of 3/11/08, 9:55am) Write a program P(n,i,a): that inputs pos. integers n, and i, with i ≤ n, and a synbol (letter) a, and outputs the polynomial (in the a[i,j]'s)

    (a[i,1]+a[i,2]+ ... +a[i,n])*TW(n,i,a)-
    (a[1,i]*TW(n,1,a)+a[2,i]*TW(n,2,a)+ ... + a[n,i]*TW(n,n))

    (Note that in the ... there is no a[i,i]), Don't forget to expand at the end.

  6. Using the methodogy of experimental math, of generating data, looking for patterns, and making a conjecture, Conjecture an explicit expression for P(n,i,a).
  7. ($5 prize, to be divided among all solvers by March 13, 2008) Prove your conjectured expression for P(n,i,a), using combinatorics! (no money for other methods).
    [Added March 13, 2008: Congratulations to Lara Pudwell, Andrew Baxter, Paul Raff, Beth Kupin, Emilie Hogan, and Brian Nakamura for sharing the $5 prize. They all got it right!. Here are Lara's solution and Baxter's solution .

Programs done on March 13, 2008, class

mar13.txt, contains the following nifty programs

Homework for March 13, 2008 (due March 24, 2008)

  1. Find and a prove a closed-form expression, in n and x, for Cayleynx(n,x). Then plug-in x=n and deduce Cayley's formual.
  2. Use the Matrix Tree Theorem to write a short program SPBP(m,n), that inputs two integers m and n, and outputs the number of spanning trees for the complete bi-partite graph Km,n (this is a graph with m+n vertices, m of which are called men, and n of which are called women, and there are all the possible mn edges between men and women, but no edges between men and no edges between women).
  3. [I don't the answer for that one, I didn't try] Output many values for different m and n for SPBP(m,n) and see if they happen to be in Sloane. Try to conjecture a closed form formula for SPBP(m,n), if possible, or at least for SPBP(m,1),SPBP(m,2),SPBP(m,3), ... as far as you can.
  4. Consider the graph G(n,i) whose vertices are {0, ..., n-1} and any vertex v is connected to v+1, v+2, ..., v+i, v-1, .., v-i (mod n) (so there are ni edges). Write a program,SPW(n,i), that finds the number of spanning trees of G(n,i).
  5. [I don't the answer for that one, I didn't try] Output many values for different m and n for SPW(n,i) and see if they happen to be in Sloane. Try to conjecture a closed form formula for SPW(n,i), if possible, or at least for SPW(n,1),SPW(n,2),SPW(n,3), ... as far as you can.
  6. Carefully read my writeup on the Lagrange Inversion Formula
  7. Write a Maple program LIF(PHI,t,N) that inputs a function Φ of t, and outputs the first N coefficients of the formal power series that satisfies the functional equation:

    u(t)=t Φ(u(t))

  8. Using Generatingfunctionology, convince yourself that the exponential generating function, T(t), for labelled rooted trees satisfies the functional equation

    T(t)=t eT(t) .

    Use the Lagrange Inversion Formula (by purely human means) to give yet another proof of Cayley's nn-2 formula.

  9. Use Generatingfunctionology to find the number of ways of partitioning {1, ..., 100} into a disjoint union of sets, each of which has a size that is a perfect square.
  10. Use the Lagrange Inversion Formula to find the number of labelled rooted trees on 100 vertices where the root has two neighbors, and each other vertex has exactly three neighbors, or exactly one neighbor.
  11. Enjoy the Spring Break, but don't forget to do the homework!

Added March 17, 2008: Pick a final project ,

March 17, and March 20 2008

Spring Break.

Programs done on March 24, 2008, class

  1. mar24.txt, implements the Lagrange Inversion Formula. It contains the following nifty programs
  2. mar24a.txt, Uses the symbolic (and numeric) Matrix Tree Theorem. It contains the following nifty programs

Homework for March 24, 2008 (due March 27, 2008)

  1. Write a program a(r,N), that inputs pos. integers r and N and outputs the first N terms of the counting sequence for labelled rooted trees where the root has degree ≤ r and every other vertex had degree ≤ r+1 (i.e., viewed from the top, it has ≤ r children). Look at the sequences for r=1,2,3, ... in Sloane, and see which exist.
  2. An ordered tree is an unlabelled tree where there is a distinguished vertex r, and it has children, ordered from left to right, each of whom may have no children, or start its own dynasty.
    Write a program b(r,N), that inputs pos. integers r and N and outputs the first N terms of the counting sequence (i.e. the list whose n-th term is the number of such trees with n vertices) for ordered trees where every vertex has ≤ r children. Look at the sequences for r=1,2,3, ... in Sloane, and see which exist.
  3. Write a program c(r,N), that inputs pos. integers r and N and outputs the N-term sequence (list) whose n-th entry is the number of ordered trees with n vertices, and where every vertex has either no children (i.e. is a leaf) or has exactly r children. Can you conjecture a closed-form formula for c(r,N)? Can you prove it? (using the Lagrange Inversion Formula or otherwise).
  4. Conjecture a closed-form expression for NuST(n+1,Wheel(n));
  5. Define a generalized wheel, Gwheel(n,r), with rn+1 vertices where
    the outer rim is labelled 1...n,
    the next inner rim is labelled n+1, ..., 2n
    ...
    the innermost rim is labelled (r-1)n+1, ..., rn
    the center is labelled rn+1.
    Assume that within each rim, m has an edge to its immediate neighbors (so there is an edge between m and m+1 if m is not a multiple of n and an edge between jn+n and jn+1), and in addition, the center has an edge to each the innermost rim, and each other vertex ,m, not on the inner rim is connected to m+n. Write a program Gwheel(n,r) that outputs this graph as a set of edges.
  6. For r=1,2,3, ... (as far as you can go), compute sequences for the number of spanning trees of Gwheel(n,r) and look them up in Sloane. If possible, conjecture "nice" expressions for them and prove them.
  7. Read about Prüfer's bijection in Dr. Z.'s crash course on enumerative combinatorics, or Wikipedia, or, in more detail, in almost any combinatorics text, and program it, first the "easy" direction (from labelled trees to codes), and then the reverse. Call them S, and T resp .. Check empirically that ST and TS are the identity mappings on their respective domains.

Programs done on March 27, 2008, class

mar27.txt, to construct and count integer partitions. It contains the following procedures.
  1. Par(n): the set of integer-partitions of n
  2. Par1(n,k): the set of partitions of n whose largest part is k
  3. par1(n,k): the number of partitions of n whose largest part is k
  4. par(n): the number of integer-partitions of n, using a 2-parameter recurrence (i.e. adding up par1(n,k) for k from 1 to n)
  5. P(N): the first N terms of the partition function (the stupid way, using par(n))
  6. Pf(N):the first N terms of the partition function (using the generating function 1/(1-q)/(1-q2 )/(1-q3)/...)
  7. p(n): the number of partitions of n using the Euler-Pentagonal recurrence
  8. Pff(N):the first N terms of the partition function (using the Euler-pentagonal recurrence)

Homework for March 27, 2008 (due March 31, 2008)

  1. Write a program, call it Par2(n,k), that inputs pos. integers n and k and outputs the set of integer partitions with exactly k parts.
  2. Write a program, call it par2(n,k), that inputs pos. integers n and k and outputs the number of integer partitions with exactly k parts.
  3. Prove that par1(n,k) is always equal to par2(n,k). Construct an explicit bijection between Par1(n,k) and Par2(n,k), and vice versa.
  4. Modify Par(n) to write a program cPar(n,d,S) that inputs a pos. integer n, a pos. integer d, and a set S of integers between 0 and d-1 and outputs the set of partitions of n all of whose parts are congruent to some element s in S modulo d. For example cPar(n,2,{1}); is the set of partitions of n all whose parts are odd, cPar(n,5,{1,4}); is the set of partitions of n all whose parts are congruent to 1 or 4 modulo 5.
  5. Modify par(n) to write a program cpar(n,d,S) that inputs a pos. integer n, a pos. integer d, and a set S of integers between 0 and d-1 and outputs the number of partitions of n all of whose parts are congruent to some element s in S modulo d. For example cpar(n,2,{1}); is the number of partitions of n all whose parts are odd, cpar(n,5,{1,4}); is the number of partitions of n all whose parts are congruent to 1 or 4 modulo 5.
    (In other words, cpar(n,d,S) is the number of elements of cPar(n,d,S).)
  6. Modify Par(n) to write a program dPar(n,d) that inputs a pos. integer n, a pos. integer d, and outputs the set of partitions of n where the difference between consecutive (and hence any) two parts is ≥ d. For example, dPar(n,0) is just Par(n), while dPar(n,1) is the set of partitions of n into distinct parts.
  7. Modify par(n) to write a program dpar(n,d) that inputs a pos. integer n, a pos. integer d, and outputs the number of partitions of n where the difference between consecutive (and hence any) two parts is ≥ d. For example, dpar(n,0) is just par(n), while dpar(n,1) is the number of partitions of n into distinct parts.
    (In other words, dpar(n,d,S) is the number of elements of dPar(n,d,S).)
  8. Prove, empirically, for 0 ≤ n ≤ 200, that
    cpar(n,2,{1})=dpart(n,1)
  9. (5 dollars to be divided between all those who get it right by March 31, 2008, 12:00noon, and who have not seen it before). Find a bijective proof of the above fact, and program it. In other words find two mappings
    S: cPar(n,2,{1})->dPar(n,1)
    T: dPar(n,1)-> cPar(n,2,{1})
    such that ST and TS are both the identity mappings.
  10. Prove, empirically, for 0 ≤ n ≤ 200, that
    cpar(n,5,{1,4})=dpart(n,2)
  11. (100 dollars to the first person to get it, offer expires last day of classes). Find a nice bijective proof of the above fact, and program it. In other words find two mappings
    S: cPar(n,5,{1,4})->dPar(n,2)
    T: dPar(n,2)-> cPar(n,5,{1,4})
    such that ST and TS are both the identity mappings.

Handout and Programs given on March 31, 2008, class

First Homework Set for March 31, 2008 class, Due April 1, 2008 [No extensions!]

Second Homework Set for March 31, 2008 class, Due April 3, 2008

  1. Write a Maple implementation of the Bressoud-Z involution from the book.
  2. Write a procedure, PP2a(a1,a2,N,q), that inputs two non.neg. integers a1,a2 such that a1 ≥ a2 ≥ 0, and outputs the generating function for N-columned and 2-rowed plane partitions whose left-most column is [a1,a2].
  3. Write a procedure, PP2(M,N,q), that inputs two non.neg. integers M and N and outputs the generating function for all 2-rowed and N-columned plane partitions, all of whose parts are ≤ M.
  4. Write a procedure, PP3a(a1,a2,a3, N,q), that inputs three non.neg. integers a1,a2,a3, such that a1 ≥ a2 ≥ a3 ≥ 0, and outputs the generating function for N-columned and 3-rowed plane partitions whose left-most column is [a1,a2,a3].
  5. Write a procedure, PP3(M,N,q), that inputs two non.neg. integers M and N and outputs the generating function for all 3-rowed and N-columned plane partitions, all of whose parts are ≤ M.
  6. Conjecture explicit expressions for PP2(M,N,q) and PP3(M,N,q) .
  7. (5 dollars to be divided among the people who would get it right). Conjecture an explicit expression for PPK(M,N,q), the generating function for K-rowed, N-columned Plane Partitions each of whose parts is ≤ M .

Programs done on April 3, 2008, class

apr3.txt contains the following procedures:

Homework for April 3, 2008 class, Due April 7, 2008

  1. Using GuessPolq, conjecture a closed form formula (as a product) for PP2(M,N,q) and PP3(M,N,q). Generalize this to conjecture the generating function for "PPK(M,N,q)", i.e. the weight-enumerator for plane partitions whose 3D Ferrers diagram is inside an M by N by K box. formula (as some kind of product)
  2. Write PPK(M,N,K,q) that generalizes PP2 and PP3 to plane partitions with K rows. Check its output for K=4,5 against your conjecture.
  3. Plug-in M=N=K=infinity in the above prodcut-formula and deduce MacMahon's expression for ALL plane partitions
    1/[(1-q)(1-q2)2(1-q3)3 ... ]
  4. Write a program Solid22(N,M,q) that inputs integers M and N and outputs the generating function for all solid partitions whose 4D Ferrers graph fits inside a 2x2xMxN (four-dimensiona) box. In other words, all 3D 2x2xM arrays
    a[i,j,k], 1 ≤ i,j ≤ 2, 1 ≤ k ≤ M
    with 0 ≤ a[i,j,k] ≤ N such that a[i,j,k] is weakly decreasing in every one of the three direction.
    Hint: First write a program Soild22a(a11,a12,a21,a22,M,q) that computes the generating function according to the information about the top layer, and then, to get Solid22(N,M,q) simply do
    Soild22a(N,N,N,N,M+1,q)/q4N
    Note that a11 ≥ a12, a11 ≥ a21, a21 ≥ a22 in addition to them being between 0 and N.

Programs done on April 7, 2008, class

apr7.txt contains the following procedures:

Homework for April 7, 2008 class, Due April 10, 2008

  1. Prove rigorously (but humanly) that |A(n,{[1,2,3],[1,3,2]})|=2n-1 .
  2. Try to prove that both |A(n,{[1,2,3]})| and |A(n,{[1,3,2]})| are given by the Catalan numbers Cn=(2n)!/(n!(n+1)!) .
  3. Look at all the binomial(6,3)=20 sets that have exactly three patterns of length three . try to conjecture expressions for A(n,S) for as many S as you can.
  4. Extend A(n,S) and write a procedure B(L,S) that inputs a list L of non-neg. integers and outputs all words (i.e. lists ) with L[1] 1's, L[2] 2's, ... L[n] n's that avoid the set of patterns S. Note that B([1$n],S) should equal A(n,S).
    Warning, this is very slow, so only try it for L whose sum is ≤ 7 .

Programs done on April 10, 2008, class

Today was such a nice day, so the class was on the lawn, using our biological computers between our shoulders, aided by memory-storage device called pencil-and-paper. We talked about Young tableaux and how to count them. The following short program: apr10.txt, contains programs Par(n) to generate all integer-partitions of n, and GuessPol(L,n) that inputs a list L of numbers and a symbol n, and outputs a polynomial P, of degree nops(L)-4, if it exists, such that P(i)=L[i], for i=1..nops(L) (or returns FAIL). These are needed for the homework problems.

Homework for April 10, 2008 class, Due April 14, 2008

  1. Write a program: Children(L) that inputs a partition of L, and outputs the of partitions obtained by reducing by one any of its parts, such that the remaining list is still a partition. For example, Children([3,2,2,1]); should give the set {[2,2,2,1],[3,2,2]}, but does not include [3,1,2,1]). Rememeber that if you get [3,2,2,0] you must kick out the 0 at the end.
  2. Write a program f(L) that inputs a partition L and outputs the number of Standard Young tableaux of shape L.
    Hint: Using the "going down" recurrence f(L)=Sum(f(L-), L- in Children(L));, together with the the initial condition f([])=1 .
  3. Verify up to n=13, the Humberto conjecture that
    Sum(f(L)^2, L in Par(n)) =n!
  4. Write a procedure for
    a(n):=Sum(f(L), L in Par(n))
    and look up
    seq(a(n),n=1..9)
    in Sloane.
  5. Using GuessPol in apr10.txt, conjecture explicit expressions for (Warning: the lists that GuessPol takes start at the argument being 1, here the argument starts later.
  6. Glancing at the above output, conjecture an explicit expression for f([a,b]), with a ≥ b ≥ 0.
  7. (5 dollars to be divided among all correct solvers). Using the same methodololgy as above conjecture an explicit expression for f([a,b,c]) for a ≥ b ≥ c ≥ 0 . Then Rigorously prove it!
  8. (6 dollars to be divided among all correct solvers). Conjecture an expression for f([a1,a2, ..., ak]) for arbitrary k.
  9. (7 dollars to be divided among all correct solvers) Prove the above conjecture.

Programs done on April 14, 2008, class

apr14.txt, contains the following procedurs (in addition to Par(n) from last time and GuessPol(L,n) described last time)

Homework for April 14, 2008 class, Due April 17, 2008

  1. Recall that a rational function f(x) is a quotient of polynomials f(x)=P(x)/Q(x). Write a program GuessRat1(L,x,d) that inputs a list L, a variable x, and a non.neg. integer d such that 2*d+5 ≤ nops(L), and outputs a rational function P(x)/Q(x) with degree(P,x), degree(Q,x) ≤ d, such that P(i)/Q(i)=L[i] for all i from 1 to nops(L), if one exist, and FAIL otherwise.
  2. By trying d=1..(nops(L)-5)/2, write a program GuessRat(L,x) that guesses a rational function P(x)/Q(x) that fits L.
  3. By using GuessRat, conjecture a rational function for g2(a,b):=f([a,b])/((a+b)!/(a!b!)) .
    Hint, first, freeze b, and get rational functions g(a,b1) for various b, and then use GuessRat with respect to that list to conjecture an expression for g(a,b).
  4. By using GuessRat, conjecture a rational function for g3(a,b,c):=f([a,b,c])/((a+b+c)!/(a!b!c!)) .
    Hint, first, freeze c, and b, to get rational functions g(a,b1,c1) for various b1, and c1. etc.
  5. Write a procedure Children(L) (with the new meaning of children), that inputs the set of partiotions obtained from L by legally adding one box (i.e. the set of partitions L1 such that L is a member of Mamas(L1)).
  6. What can use say about
    h(L):=Sum(f(L1), L1 in Children(L))/f(L) .

    Programs done on April 17, 2008, class

    apr17.txt, contains the following procedurs (in addition to those of apr14.txt described above)

    Homework for April 17, 2008 class, Due April 21, 2008

    1. Write a procedure, SYT(L), that inputs a partition L, and outputs the set of Standard Young Tableaux of shape L. For example Y([2,2]); should yield {[[1,2],[3,4]],[1,3],[2,4]]}.
    2. A Semi-Standard tableau of shape L is a way of filling-in L with positive integers such that it is strictly increasing along the columns but only weakly increasing along the rows. Write a program SSYT(L,r) that inputs a shape L and a pos. integer r, and outputs the set of Semi-Standard Young tableaux of that shape that only uses the integers {1, ..., r}. For example SSYT([2],2); should return {[1,1],[1,2],[2,2]}; while SSYT([1,1],2); should return {[1,2]};
      Hint: write the analog of Mamas, by considering those tableaux obtained by deleting the largest integer, r.
    3. (10 dollars to be divided among those that get it right). Use human ingenuity to prove the "Going-Up recurrence",
      (n+1)f(L)=Sum(f(L1), L1 in Children(L)) by using induction, together with the "Going-Down recurrence" (that is obvious):
      f(L)=Sum(f(L1), L1 in Mamas(L))

    Programs done on April 21, 2008, class

    apr21.txt, contains the following procedurs (in addition to those of apr17.txt described above)

    Homework for April 21, 2008 class, Due April 24, 2008

    1. A skew-shape is a pair of partions [L1,L2] such that the Young diagram of L1 is a subset of the Young diagram of L2. A skew-standard-Young tableau, is a way of filling-in the integers 1 through nops(L2)-nops(L1) such that they are increasing along rows and along columns. Modify f(L) and F(L) to write procedures fSkew(L1,L2) and FSkew(L1,L2) that computes their numbers and the set itself, respectively.
    2. Given a partition (shape) L, label its boxes like you would the entries of a matrix, i.e. box (i,j) is the j-th box of the i-th row. The hook-length of a box (i,j) in a shape L, is the number of boxes to its right (in the i-th row) plus the number of boxes below it (in the j-th column) plus 1 (for itself). For example, the hook length of box (2,3) in the shape [6,5,4,3,3,3] is 7. Write a procedure Hook(L,i,j) that inputs a partition L and pos. integers i and j, and outputs the hook-length of box (i,j) in the shape L. For example,
      Hook([6,5,4,3,3,3],2,3);
      should return 7. It should return FAIL if box (i,j) is not a member of the shape L.
    3. Write a prodedure HLF(L), that inputs a partition L and outputs n! divided by the product of all the hook-lengths. (where n is the number of boxes in L (i.e. L[1]+L[2]+ ...+L[nops(L)]).
    4. Verify empirically that HLF(L)=YFF(L) for all partions L of n ≤ 10 .
    5. [5 dollars to be divided between all correct answers]. Prove that HLF(L)=YFF(L) for every shape.
    6. [7 dollars to be divided between all correct answers] Prove that f(L)=YFF(L) for shape with k rows, with k arbitrary.
      Hint: You may want to use a variant of the Lagrange Interpolation Formula.

      Programs done on April 24, 2008, class

      apr24.txt, contains the following procedurs (in addition to those of apr21.txt and sooner described above)
      • HL(L,i,j): inputs a partition L and pos. integers i and j and outputs the hooklengths of box (i,j) in L
      • HLF(L): The hooklength formula for the number of Standard Young Tableaux of shape L (equals YFF(L)).
      • Ins1(Y,i,row1): one step of one step of the Robinson-Schenstead algorithm. Inputs a Young tableau Y, and an integer i, and a row number row1, and outputs another Young tableau and a bumpee.
      • Ins(Y,i): one step of the Robinson-Schenstead algorithm. Inputs a Young tableau Y, and an integer i, not in Y, and outputs another Young tableau with one extra box added, and the row-number of that added box. [corrected, 4/25/08 by Slava and Humberto]

      Homework for April 24, 2008 class, Due April 28, 2008

      1. Complete the Robinson-Schenstead algorithm, writing a procedure, RS(pi), that inputs a permutation pi of {1, ..., n} and outputs a pair of Standard Young Tableaux of the same shape (each with n boxes). Do it by setting Y:=[[pi[1]]], and then doing for each i=2..n, in turn, Y1:=Ins(Y1,pi[i]). The final tableau is the Insertion tableau. To get the second tableau (the so-called template tableau) keep inserting, in, turn, 1, 2, 3, ..., n, where i goes to the box that was added right after the insertion of pi[i].
      2. Write the inverse of Ins(Y,i), call it Del(Y,bumpee). (Hint: first write the inverse of Ins1)
      3. Using the above, write a procedure, IRS(Y1,Y2), that inputs two Standard Young tableaux Y1,Y2, of the same shape (first check that fact, and return FAIL if it fails), and outputs a permutation pi, such that RS(IRS(Y1,Y2))=(Y1,Y2).
      4. Write a procedure that inputs a permutation and outputs its inverse.
      5. How are RS(pi) and RS(inverse(pi)) related?

      Programs done on April 28, 2008, class

      apr28.txt, contains the following procedurs (in addition to those of apr24.txt and sooner described above)
      • RS(pi): performs the Robinson-Schenstead Correspondence to a permutation pi
      • TestRS(n): tests that the RS(pi) ranging over all pi, does indeed gives the set of pairs of SYT of the same shape with n boxes.

      Homework for April 28, 2008 class, due May 1, 2008

      1. A semi-standard Young tableaux (also called column-strict) is a way of filling an r-rowed shape with the integers {1, ..., n} (n ≥ r), such that the entries are weakly increasing along the rows and strictly increasing along the columns. Write a program SSYT(L,n) that inputs a shape L and a pos. integer n, and outputs the set of semi-standard Young tableaux.
      2. The weight of a tableaux (a[i,j]) is the product of x[a[i,j]] over all entries. For example, the weight of [[1,2,2,3],[2,3,3,4],[3,4,5]] is (x[1]x[2]x[2][x[3])(x[2]x[3]x[3]x[4])(x[3]x[4]x[5]). Let S(L,n,x) be the sum of the weights of all members of SSYT(L,n). Write a procedure Sslow(L,n,x) to find the polynomial (in x[1], ..., x[n]) S(L,n,x)
      3. Write a faster program . Sfast(L,n,x), with the same output as Sslow(L,n,x), but without first literally constructiong the set SSYT(L,n). Do it by establishing a recurrence that expresses S(L,n,x) in terms of S(L',n-1,x) for smaller L' s.
      4. [2 dollars to be divided by the k solvers]. Conjecture an explicit expression for S([a,b],2,x)*(x[1]-x[2]), as a polynomial in (with powers that involve a,b), for a ≥ b > 0
      5. [3 dollars to be divided by the k solvers]. Conjecture an explicit expression for S([a,b,c],3,x)*(x[1]-x[2])*(x[1]-x[3])*(x[2]-x[3]), as a polynomial in x[1],x[2],x[3] (with powers that involve a,b,c) a ≥ b ≥ c > 0
      6. [10 dollars to be divided by the k solvers]. Conjecture an explicit expression for
        S([a1,a2, ..., an],n,x)*Product(Product(x[i]-x[j], j=i+1..n),i=1..n)
        as a polynomial in x[1],x[2],x[3], ..., x[n] (with powers that involve a1,a2, ..., an) a1 ≥ a2 ≥ ... ak > 0
      7. In preparation for Polya theory, to be covered next time, carefully read pages 10 and 11 of: Dr. Z.'s Crash course on enumerative combinatorics

      Programs done on May 1, 2008, class

      may1.txt, contains the following procedurs, starting Polya-Redfield theory.
      • AvF(G): The average number of fixed points of the group of permutations G.
      • kefel(pi,sig): permutation pi times permutation sig (as permutations)
      • GenG(S): Given a set of permutations S all of the same size, outputs the group of permutations generated by them

      Homework for May 1, 2008 class, due May 5, 2008

      1. Figure out the group of rotations of the three dimensional cube that send faces to faces (hint: there 24 of them). Label the top 1, the bottom 2, the left 3, the right 4, the front 5, and the back 6.
      2. Write a procedure Necklace(n), that inputs an integer n, and that outputs the group of rotations of an n-bead necklace, as a group of permutations of 1, 2, ...,n , where the beads are arranged clockwise.
      3. Write a procedure Gp(G,n), that inputs a graph G with vertices {1, ...n}, given in terms of a set of edges, and outputs the set of permutations pi of {1,...,n} that when pi is applied to G, the set of edges remain the same. For example Gp(3,{{1,2},{1,3}}); should output {[1,2,3],[1,3,2]}.
      4. Write a procedure Cycle(pi), that inputs a permutation pi, and outputs the set of its cycles. A cycle i1->i2->i3->...->ik->i1 should be denoted by [i1,i2, ..., ik] For example Cycles([1,2,3]); should return {[1],[2],[3]}, and Cycles([3,2,1]); should return {[1,3],[2]}.

      Programs done on May 5, 2008, class

      may5.txt, Finishing Polya-Redfield theory.

      Have a great summer!

      Dr. Z.'s teaching page