Skip to main content
\( \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section3(Some) Areas of Discrete Mathematics

Subsection3.1Graph Theory

Create graphs in a natural way:

There are many pre-defined graphs (digraphs, too):

Constant time generation of free trees, by B. Richmond, A. Odlyzko, B.D. McKay

From a path to a star:

Visually:

Subsection3.2Group Theory

Prototypical use of Sage: permutation groups. Built from the mature open source package GAP (Groups, Algorithms, Programming).

Subsection3.3Put Them Together: Tower of Hanoi

  • graphs.HanoiTowerGraph(n, d)
  • Generalize to \(n\) pegs and \(d\) disks
  • State graph: intermediate configurations, edges are “one move”
  • Labels: \(d\)-tuple, large disk to small disk; entries are peg numbers
  • Example: \(n=3\text{,}\) \(d=4\text{:}\) \((2,0,2,1)\)

A solution is path between states “all the disks on one peg” and “all the disks on another peg.”

Minimum number of moves:

More general:

Forget about graphics, work with graph itself.

Code vertices to integers: \(d\)-tuples, base \(n\text{.}\) All disks on peg 0, move to all disks on peg 3.

Theorem: automorphisms of the state graph are just the obvious ones (renumber pegs)

Automorphisms are computed via Brendan McKay's nauty algorithm, once re-implemented as NICE.

Subsection3.4Linear Algebra

Subsubsection3.4.1Exact Linear Algebra

Many possible fields and rings: finite fields, field extensions, algebraic numbers. Over the integers and rationals powered by Integer Matrix Library (IML).

And it is fast. \(1000\times 1000\) matrix with single digit integer entries.

We can combine linear algebra with graph theory (aka “algebraic graph theory”).

A small “singular graph.” (I. Sciriha, 2007)

Notice this is the kernel over the integers, and is computed as a module. It is easy to upgrade to the rationals.

A matrix kernel (null space) is a vector space, and has all the attendant properties.

Subsubsection3.4.2Numerical Linear Algebra

Numerical linear algebra is supplied by SciPy, through to LAPACK, ATLAS, BLAS.

A matrix of double-floating point real numbers (RDF).

And the QR decomposition of B.

Subsubsection3.4.3Image Compression

Subsection3.5Simple Number Theory

Sage was born of necessity to do number theory.

Factor 50-digit number (⁓166 bits).

Euler \(\phi\) function. (“totient” function.)

Integers less than \(100\) and relatively prime to \(100\text{.}\) (Note the srange function to generate Sage integers.)

Fact: \(\displaystyle\sum_{d\mid n}\,\phi(d) = n\)

Proof: Group the fractions, \(\displaystyle\frac{i}{n}\text{,}\) \(0\leq i\leq n-1\text{,}\) by denominators once written in reduced terms.

Subsection3.6Linear Recurrence Relations

Numbers of certain objects can sometimes be counted by recurrence relations. We would like closed-form expressions for terms of sequences defined this way.

Subsubsection3.6.1Perrin's Sequence

Perrin Sequence:

\(p(0) = 3\text{;}\) \(p(1) = 0\text{;}\) \(p(2)=2\)

\(p(n) = p(n-2) + p(n-3)\)

Looks like the Fibonacci sequence, but “skips back” two terms, not one.

Compute by hand: \(3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, \dots\)

This is in Sloane's Online Encyclopedia of Integer Sequences as sequence number A001608.

A brute-force approach with a Python function. Impractical above about \(n=60\text{.}\)

Fact: If \(q\) is prime, then \(q\) divides \(p(q)\text{.}\)

(First composite number that behaves this way is \(521^2\text{.}\))

Generating function: \(f(x)=\displaystyle\sum_{i=0}^\infty\,p_i\,x^i\)

Theory gives easy computation for Perrin sequence, denominator comes from recurrence relation, numerator is simple polynomial multiplication.

\begin{equation*} f(x) = \frac{3-x^2}{1-x^2-x^3}\text{.} \end{equation*}

We can expand \(f\) as a Taylor series.

Subsubsection3.6.2Decompose with Partial Fractions

Partial Fractions can simplify a rational generating function. New, three-term recurrence.

\(a(0)=7\text{;}\) \(a(1)=41\text{;}\) \(a(2)=204\)

\(a(n) = 7a(n-1) - 12a(n-2) + 10a(n-3)\)

Generating function—the rational function:

Check \(a(3)\text{,}\) first new term of the sequence:

Create partial fraction decomposition and examine the pieces:

Subsubsection3.6.3Using SymPy

SymPy is a pure Python package included in Sage, but not integrated with Sage.

docs.sympy.org/dev/modules/solvers/solvers.html#recurrence-equtions (sic)

Import pieces of the SymPy library.

Define the recurrence as an expression in \(y(\cdot)\) that equals zero.

And solve: