Minutes for 2/20/03 (prepared by Ian Le, with revisions by Jim Propp)

We went around with names and each talked about what we were working on
or interested in working on.

Jim asked what people thought about the previews posted on the REACH
website.  Gabriel mentioned that in D1, parts a and b were equivalent
under the change of variables z-->iz.

We went to the Science Center were Jim discussed "urban renewal," a method
for counting weighted matchings in graphs by simplifying the graph at each
step.
--we started out with some simple examples--a chain of edges could be
replaced by either one or 0 edges (depending on parity) without changing
the number of matchings:

O----O----O----O----O         ----> O          

or

O----O----O----O----O----O    ----> O----O

--replacing each edge incident to a vertex by double edges doubles the
number of matchings.

--replacing each edge in a graph by two edges multiplies the number of
matchings by 2^(V/2), where V is the number of vertices in the graph.

--Jim then showed how the graph with weights

  O           O
   \         /
    \       /
     O--a--O
     |     |
     b     c
     |     |
     O--d--O
    /       \
   /         \
  O           O

could be replaced by the graph with weights

  O-----d'----O
  |           |
  |           |
  |           |
  |           |
  c'          b'
  |           |
  |           |
  |           |
  |           |
  O-----a'----O

where a'=a/(ad+bc), b'=b/(ad+bc), etc.  The total of the weights of 
the matchings of the second graph equals the total of the weights 
of the matchings of the first graph divided by (ad+bc).

--we then used this technique to show that the number of matchings in the
following graph is 5.


             O----O
             |    |
             |    |
  O          O----O          O
   \        /      \        /
    \      /        \      /
     O----O          O----O
     |    |          |    |
     |    |          |    |
     O----O          O----O
    /      \        /      \
   /        \      /        \
  O          O----O          O
             |    |
             |    |
             O----O


We had a five minute break then proceeded to the computer lab.  Jim
gave a quick tour of the Reach sites (public and private).

Jim demonstrated the probrams graph.tcl (spanning trees of bow-ties),
and tiling.exe (ribbon tilings)

Jim showed how to enter in the following recurrence (from topic
C4) into Maple:
        f := proc(n,i,j) option remember; if n<2 then x(i,j) else simplify(
        (f(n-1,i-1,j)*f(n-1,i+1,j)+ f(n-1,i,j-1)*f(n-1,i,j+1))/f(n-2,i,j) );
        fi; end;
        mincount := proc(e) local i,least,new,count;
            least := nops(op(1,e)); count := 1; 
            if nops(e)>1 then for i from 2 to nops(e) do
                new := nops(op(i,e)); 
                if new < least then least := new; count := 1;
                elif new = least then count := count+1; fi; 
            od; fi; count; end;

Then the command
        seq(mincount(expand(f(n,0,0))),n=2..5);
gave us the number of simplest terms in the nth polynomial given by
the recurrence, for n going from 2 to 5: 
        2, 6, 22, 92.
We entered the number of simplest terms in each step of the recurrence
into the Online Encyclopedia of Integer Sequences, which told us that 
these numbers appear to count something called "Baxter permutations".

In fact, this is true for all n, but it took a bit of work to prove.
(This is work of Hal Canary, which hasn't been written up yet; Jim
invited people to get involved with writing up and continuing this
work.)

Jim then entered the recurrence from topic D1 into MAPLE:
        M := proc(n) option remember; 
        if n=0 then x elif n=1 then y elif n=2 then z else
        simplify( (M(n-1)^2-M(n-2)^2)/M(n-3) ); fi; end;
Then the command
        seq(nops(expand(numer(M(n)))),n=3..10);
tells us that the number of terms in the Laurent polynomial M(n)
grows like 2, 4, 9, 21, 51, 127, 322, 826, ... .  We gave this
sequence to the Online Encyclopedia of Integer Sequences and
learned that its nth term is given by (F_(2n+1)+F_(n+1))/2.

Jim mentioned that we could learn Maple by using Herbert Wilf's "East
Side, West Side."

Kyle demonstrated his program for generating groves (with pretty colors).