EXPERIMENTAL MATHEMATICS – TUTORIAL 1
1. Lines in the plane
What is the maximal number of regions R(n) that you can obtain by drawing n lines in
the plane R2?
We’ll explore this by hand first. Clearly
R(0) = 1, R(1) = 2, R(2) = 4.
Compute R(3).
Convince yourself that the following recurrence relation holds:
R(0) = 1
R(n) = R(n− 1) + n if n ≥ 1
Now implement it in either Macaulay2 or Mathematica! If your function is called R, then
you should be able to display the first few terms using
L=apply(20,R)
or
L=Table[R[n], {n, 0, 19}]
and check that it matches the terms we already knew.
Very satisfying. How about a formula for R(n) though? We could think about it and
figure it out fairly quickly in this example, but let’s instead search for the first few terms
in the Online Encyclopedia of Integer Sequences (OEIS), either directly at oeis.org or using
Macaulay2’s built-in oeis.
Check that the closed form given by OEIS for R(n) matches the recurrence relation. Go one dimension up and play with it: what is the maximal number of regions
that can be obtained from n planes in R3?
As frivolous as the topic may seem (slicing a pancake with n cuts, indeed), it is an active
area of research. Look up hyperplane arrangements on the web, or [Stanley, EC1, Section
3.11].
1
2 EXPERIMENTAL MATHEMATICS – TUTORIAL 1
2. The Fibonacci sequence
The famous Fibonacci sequence is given by the recurrence relation
F0 = 1
F1 = 1
Fn = Fn−1 + Fn−2
We’ve learned in the previous exercise how to implement recurrence relations; define a func-
tion F that does that for the Fibanacci sequence.
Now try to run it to compute say the first 35 terms, and let’s time the result using
time apply(35,F) or Timing[Table[F[n],{n,0,34}]].
Can you figure out why it is so slow? If you did, then you realize you need to modify your
program so it doesn’t keep recomputing the same entries of Fn! In Macaulay2, all you need
to do is to add memoize in front of the definition of F (or you can do it after the fact by
writing F=memoize F); in Mathematica, by writing F[n_]:=F[n]=... where the dots stand
for your previous definition of F. Try that and time again your calculation of F (0), . . . , F (34);
is it better now?
It is well-known that the following formula holds
(1) Fn =
φn+1+ − φn+1−
φ+ − φ− φ± =
1±√5
2
Check that the expression in the r.h.s. satisfies the recurrence above, thus proving the equal-
ity. Then implement this new formula for Fn by replacing φ± with their numerical values.
Check that it agrees with the old one on examples. Implement (1) exactly rather than numerically. Show that you have exact equal-
ity between the two different definitions of Fn. Hint: in Macaulay2, define the
ring R=ZZ[phi]/(phi^2-phi-1).
It is known that a positive integer m is part of the Fibonacci sequence if and only if at
least one of 5m2 + 4 or 5m2− 4 is a perfect square. Implement two functions that take m as
input: one that directly checks if m = Fn for some n, and one that uses the condition above.
Check that they agree.
EXPERIMENTAL MATHEMATICS – TUTORIAL 1 3
3. The number of Alternating Sign Matrices
Alternating Sign Matrices (ASMs) are matrices with
(i) entries taken from {−1, 0, 1},
(ii) row- and column-sums are equal to 1,
(iii) in each row and each column, the non-zero entries alternate in sign.
For example, there are seven 3× 3 ASMs1 0 00 1 0
0 0 1
 ,
0 1 01 0 0
0 0 1
 ,
1 0 00 0 1
0 1 0
 ,
0 1 00 0 1
1 0 0
 ,
0 0 11 0 0
0 1 0
 ,
0 0 10 1 0
1 0 0
 ,
0 1 01 −1 1
0 1 0

We want to know how many ASMs of a given size there are. In order to enumerate ASMs
efficiently, we first transform them by taking partial column sums for each column yielding,
e.g., 
0 0 1 0 0
0 0 0 1 0
1 0 0 −1 1
0 1 −1 1 0
0 0 1 0 0
 →

0 0 1 0 0
0 0 1 1 0
1 0 1 0 1
1 1 0 1 1
1 1 1 1 1

Because of the alternating condition, the new matrix has only 0’s and 1’s, and because each
columns starts and ends with a 1, the bottom row has all ones. Next we record for each row
the location of the 1’s. In the example above we get
3
3 4
1 3 5
1 2 4 5
1 2 3 4 5
These triangles are called monotone triangles, and are defined by the properties that
entries in each row are strictly increasing, and every entry is weakly between the two entries
right below it.
Monotone triangles are easy to enumerate using a recurrence scheme. Let us consider
the slightly more general problem of finding the number F (a1, . . . , an) of monotone triangles
whose bottom row is a1, . . . , an. Given the bottom row, it follows from the conditions above
that the second-row from the bottom, let’s call it b1, . . . , bn−1, has to satisfy the following
restrictions:
a1 ≤ b1 ≤ a2 ≤ b2 ≤ . . . ≤ bn−1 ≤ an,(2)
b1 < b2 < . . . bn−1.(3)
The number F (a1, . . . , an) is then recursively given by
(4) F (a1, . . . , an) =
∑
(b1,...,bn−1)
F (b1, . . . , bn−1),
where the summation is over all b’s that satisfy (2) and (3).
4 EXPERIMENTAL MATHEMATICS – TUTORIAL 1
After this lengthy introduction, let’s implement all this.
First, write a function, that, given an input a = (a1, . . . , an), generates all possible config-
urations of b = (b1, . . . , bn−1) satisfying (2) and (3). If this is too hard, you can look at the
suggested solutions in tutorial1.m2 or tutorial1.nb, and try to understand them.
Next, implement (4) and compute F (1, 2, . . . , n), the number of n × n ASMs. Compare
your answer with the sequence given in the lectures. If you’re more ambitious, you can write a function that generates (rather than
enumerates) all the ASMs (or monotone triangles) of a given size!
Horizontally symmetric ASMs. Horizontally symmetric ASMs (HSASMs) of size (2n +
1) × (2n + 1) are ASMs which are symmetric with respect to reflection in the horizontal
symmetry axis. There is, for example, only one HSASM of size 3. Show that HSASMs of
size (2n + 1) × (2n + 1) are enumerated by F (1, 3, 5, . . . , 2n + 1). Compute the number of
HSASMs and derive a closed form formula following the same steps as in the lecture.
EXPERIMENTAL MATHEMATICS – TUTORIAL 1 5
4. Pascal mod 2
The Pascal triangle is the triangle of binomial coefficients. We’re not going to bother to
define binomials inductively, but rather use the built-in functions binomial or Binomial.
We’re interested in these coefficients mod 2; something like
binomial(6,4)%2
or
Mod[Binomial[6,4],2]
Now create a nested list L of binomials mod 2 (let’s say, up to n = 31); the output should
look something like
{{1}, {1, 1}, {1, 0, 1}, {1, 1, 1, 1}, . . .}
Finally, draw the triangle as a picture where black/white squares represent 0s and 1s. In
Macaulay2, this can be achieved with
needsPackage "VectorGraphics"; matrixPlot L
Mathematica has fancier drawing abilities, and there are quite a few options to produce the
picture, see e.g.
https://www.wolfram.com/language/fast-introduction-for-math-students/en/plots-in-2d/
and
https://www.wolfram.com/language/fast-introduction-for-math-students/en/more-plots-in-2d/.
You can for example use Image or ArrayPlot.
In any case, does the picture look familiar? Try again with other values of the modulo,
e.g., mod 3.