Combinatorica

The following function in the Mathematica Combinatorica package ShowGraphArray[Partition[FiniteGraphs, 4]] produces the following graphic.

I found it in the book 'Computational Discrete Mathematics, Combinatorics and Graph Theory with Mathematica, by Sriram Pemmaraju and Steven Skiena, Cambridge 2003.' It's not the typical Proposition / Proof mathematics book but it does give you access to about 450 -practical- freely available ( if you have Mathematica ) tools to extend your problem solving toolkit.

Magic squares - Revisited

Regular readers of this blog know that I am fascinated by magic squares. Finding the 3 by 3 magic square with digits 1,2, ..., 9 can be formulated as an Integer Programming problem. An Integer Programming problem is a Linear Programming problem with the additional constraints that all variables must have integer values.

c={1,1,1,1,1,1,1,1,1};
m={
{1,1,1,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,1,1,1},
{1,0,0,1,0,0,1,0,0},
{0,1,0,0,1,0,0,1,0},
{0,0,1,0,0,1,0,0,1},
{1,0,0,0,1,0,0,0,1},
{0,0,1,0,1,0,1,0,0},
{-1,-1,-1,0,0,0,0,0,0},
{0,0,0,-1,-1,-1,0,0,0},
{0,0,0,0,0,0,-1,-1,-1},
{-1,0,0,-1,0,0,-1,0,0},
{0,-1,0,0,-1,0,0,-1,0},
{0,0,-1,0,0,-1,0,0,-1},
{-1,0,0,0,-1,0,0,0,-1},
{0,0,-1,0,-1,0,-1,0,0},
{1,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,1},
{-1,0,0,0,0,0,0,0,0},
{0,-1,0,0,0,0,0,0,0},
{0,0,-1,0,0,0,0,0,0},
{0,0,0,-1,0,0,0,0,0},
{0,0,0,0,-1,0,0,0,0},
{0,0,0,0,0,-1,0,0,0},
{0,0,0,0,0,0,-1,0,0},
{0,0,0,0,0,0,0,-1,0},
{0,0,0,0,0,0,0,0,-1}
};
b={15,15,15,15,15,15,15,15,-15,-15,-15,-15,-15,-15,-15,-15,9,9,9,9,9,9,9,9,9,-1,-1,-6,-1,-1,-1,-1,-1,-1};
LinearProgramming[-c,-m,-b]

{2, 7, 6, 9, 5, 1, 4, 3, 8}

Mathematica does find a solution in less than a second. An interesting ( Mathematica ) programming exercise would be to generate the code for solving this integer programming problem for magic squares of size n. With increasing n the number of constraints increase fast. This could become an interesting benchmark. - For a 3 by 3 magic square 34 constraints are used above ( although 32 would have sufficed, probably even less ) but these constraints can be systematically generated.

Optimizing profits

Mathematicians like space. Like in vector space, metric space, topological space. In fact, any set with structure can be called a space. In "simple" Euclidean geometry there are all sorts of problems of how to fill a space with as much objects as physically possible. How many spheres of a certain radius can we store in a cube? And so forth. - The Japanese people excel in many areas: architecture, technology. This combined with the special conditions ( a lack of =space= ) in Tokyo lead to extraordinary inventions. The following =must= have been the solution to an optimization problem of some kind. Like maximize the number of hotelrooms ( they must have started with rooms in mind ) given a number of constraint. Or simply maximize profits because I bet this 'cheap' hotel is making more profits than their five star competitors. Thanks to optimization and applied mathematics. No matter how much they love space mathematicians can minimize it for you.



I am Dutch, so somewhat exposed to overpopulation and too many people on limited ( office ) space. I can comfortably stay in any hotel though, no matter how smallish the room.  Not even the German U-boat movie 'Das Boot' gave me the same feeling of claustrophobia.

Different representations of sequences

The following five mathematical objects, i.e.: a sequence, a generating function, a recurrence equation, an arithmetical function and an asymptotic estimate, are all representations of the well-know Fibonacci sequence.

$$(1,1,2,3,5,8,13,21,34,55,...)$$
$$g[x]=\frac{x}{1-x-x^2}$$
$$a[1]=1; a[2]=1; a[n]=a[n-1]+a[n-2]$$
$$F_n = \frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1-\sqrt{5}}{2})^n$$
$$f(x)=\frac{1}{\sqrt{5}}e^{x\log{\phi}}$$

So, if we have to solve a problem involving sequences we have various options to choose from to represent the sequence we are working with. I had quite a cognition after my first confront with the consequences of this concept. Summation for example. Summation of a sequence is equal to multiplication with $\frac{x}{1-x}$ in the generating function realm. The GF of $(1,1,1, \cdots )$ is $\frac{1}{1-x}$ which means that the GF of $(1,2,3, \cdots )$ must be $\frac{x}{(1-x)^2}$.

The concrete tetrahedron

I once wrote that I rated Concrete Mathematics 6 out of 5 stars. Unfortunately the book was published in the pre LaTeX era. To the eyes or 21st century readers the book simply looks ugly. If you look a bit deeper though you'll notice that you struck gold as far as content is concerned. But... what we can do today on a laptop with Mathematica installed on it was beyond the possibilities of the super computers in the days CM was written. In that respect the book looks out-dated.

Recently a book by Kauers, Palle was published by Springer called 'The Concrete Tetrahedron'. In the book the concrete tetrahedron stands for:
- symbolic sums;
- recurrence equations;
- asymptotic estimates;
- generating functions.

The authors have the following to say about it.

... the present book is not meant to be merely a summary of “Concrete Mathematics”. We have a new twist to add to the matter, and this is computer algebra. In the last decade of the 20th century, many algorithms have been discovered by which much of the most tedious and error-prone work about the four vertices of the Concrete Tetrahedron can be performed by simply pressing a button. We believe that a mathematics student of the 21st century must be able to use these algorithms, and so we will devote a great part of this book to explaining what can and should be left to a computer, and what can and should be still better done the traditional way.

In Apostol's Analytic Number Theory formal power series and Dirichlet multiplication are among the topics. For me that was a reason to refresh, review my knowledge on formal power series and generating functions. ( One of my favorite subjects in mathematics. ) That is how I became aware of this new release.

Link: The Concrete Tetrahedron

Link: Video lectures about Concrete Mathematics

A database of sequences

In the Online Encyclopedia of Integer Sequences ( OEIS ) you can find tons of information on any sequence you can possibly think of.

An example.
A002024 n appears n times.
Starts with: 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6, ...
Closed form: a[n] = Floor[1/2 + Sqrt[2n] ]

Amazing.

( Award winning ) Turing Machine

Great site about the Turing Machine.

A conjecture about perfect numbers

Perfect number

In number theory the sum of the divisors is denoted as $\sigma$: $$\sigma(n) = \Sigma_{d/n} d$$ and $s(n)=\sigma(n) - n$ is the sum of the proper divisors. A perfect number is equal to the sum of its proper divisors. All known perfect numbers are even, it is unknown if odd perfect numbers exist. The number $2^{p-1}(2^p-1)$ is perfect if and only if $(2^p-1)$ is prime.

Conjecture

Show that: if $p$ is odd then
$$ 2^{p-1}(2^p-1) = \sum_{k=1}^{\frac{p+1}{2}-1} (2k-1)^3$$
( Notice that $2^{p-1}(2^p-1)$ yields a perfect number if $(2^p-1)$ is prime. )

Example

$6$ is perfect, since $6 = 1 + 2 + 3.$
$28$ is perfect, since $28= 1 + 2 + 4 + 7 + 14.$

Any perfect number ( except 6 ) can be represented as a sum of cubes.
$\begin{array}{ccc}
\underline{p} & \underline{Pf} &\underline{s}\\
3 & 28 & 1^3 + 3^3 \\
5 & 496 & 1^3 + 3^3 + 5^3 + 7^3 \\
7 & 8128 & 1^3 + 3^3 + ... + 15^3 \\
13 & 33550336 & 1^3 + 3^3 + ... + 127^3
\end{array}$

Proof

My exercise for New Year's Day. ( You may have noticed that I like doing 'sums'. ) Later...

( Source:
- A primer of analytic number theory, From Pythagoras to Riemann by Jeffrey Stopple
)

Stirling numbers in Discrete Calculus

Definition

Stirling numbers of the second kind represent the number of k-partitions of an n-set and are recursively defined as $\left\{ 0,0 \right\} = 1$, and $\left\{ n,k \right\} = \left\{ n-1,k-1 \right\} + k \cdot \left\{ n-1,k \right\}$. They are used in the Discrete Calculus to convert powers to factorial powers, i.e. $n^2 = n^{\underline{1}} + n^{\underline{2}}$.

The matrix below shows the Stirling numbers for $n=0$, to $n=5$.
$\left(
\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 3 & 1 & 0 & 0 \\
0 & 1 & 7 & 6 & 1 & 0 \\
0 & 1 & 15 & 25 & 10 & 1
\end{array}
\right)$

Example

Calculate $\sum_{k=1}^{n} k^5$.

$\Sigma \Delta k^5$
$=\Sigma ((n+1)^{\underline{1}} + 15(n+1)^{\underline{2}} + 25(n+1)^{\underline{3}} + 10(n+1)^{\underline{4}} + (n+1)^{\underline{5}} )$
$=\frac{1}{2}(n+1)^{\underline{2}} + 5(n+1)^{\underline{3}} + \frac{25}{4}(n+1)^{\underline{4}} + 2(n+1)^{\underline{5}} + \frac{1}{6}(n+1)^{\underline{6}}$
$=-\frac{n^2}{12}+\frac{5 n^4}{12}+\frac{n^5}{2}+\frac{n^6}{6}$
$=\frac{1}{12} n^2 (1+n)^2 \left(-1+2 n+2 n^2\right)$

\begin{array}{lll}
\underline{n} & \underline{n^5} & \underline{\frac{1}{12} n^2 (1+n)^2 \left(-1+2 n+2 n^2\right)} \\
1 & 1 & 1 \\
2 & 32 & 33 \\
3 & 243 & 276 \\
4 & 1024 & 1300 \\
5 & 3125 & 4425
\end{array}

Five proofs for the sum-formula of 1+2+3+ ... +n

The running totals of 1,2,3 ... are called the triangular numbers. We will show that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

Proof-1 Gauss's proof

( Gauss supposedly came up with this proof when he was 8 years old. On this page you will find more than 100 different tellings of this story. )
$s = 1 + 2 + 3 + \cdots + n$
$\underline{s = n + (n-1) + (n-2) + \cdots + 1}$
$2s = (n + 1) + ((n-1)+2) + ((n-2)+3) + \cdots + (1+n) \Leftrightarrow $
$2s = n \cdot (n + 1) \Leftrightarrow $
$s = \frac{n(n+1)}{2}$

Proof-2 By induction

Let $S=\left\{ n \in \mathbf{N} | \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \right\}$
Clearly $1 \in S$
Assume, $n \in S$:
$\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$, or $n \in S \Rightarrow n+1 \in S$
Now, since $(S \subset \mathbf{N} \wedge 1 \in S \wedge n \in S \Rightarrow n+1 \in S ) \Rightarrow S=\mathbf{N}.$

Proof-3 With the Pascal Triangle

Because $n^k$ is in the PT for any $k \in \mathbf{N}$, sums of polynomials with integer coefficients can be read from the PT. ( $n={n \choose 1}$, $n^2={n \choose 1} + 2{n \choose 2}$, and so forth. )
$\underline{n}$
0: 1
1: 1 - 1
2: 1 - 2 - 1
3: 1 - 3 - 3 - 1
4: 1 - 4 - 6 - 4 - 1
5: 1 - 5 - 10-10 - 5 - 1
From $n$ we seek the second column, one row down or ${n+1 \choose 2}= \frac{n(n+1)}{2}$

Proof-4 Geometric

Look at the pattern
X
and
X---Y

X
X-X
and
X---Y-Y
X-X---Y

X
X-X
X-X-X
and
X---Y-Y-Y
X-X---Y-Y
X-X-X---Y

The number of X's and Y's are equal. The triangle X-pattern with base of n X's is replaced by a rectangular shape of n+1 by n X's OR Y's.

Proof-5 With Discrete Calculus

The discrete analog of solving a differential equation.
$\Delta f(n) = n+1$
$\Sigma \Delta f(n) = \Sigma (n+1) $
$f(n) = \frac{1}{2}(n+1)^{\underline{2}} + C$
$f(n) = \frac{1}{2}(n+1)n + C$
Since $f(1) = 1, C=0$
$f(n) = \frac{n(n+1)}{2}$

[Video] - Why Pi?

Why Pi? is the title of Don Knuth’s 16th Annual Christmas Tree Lecture. Don Knuth is a famous computer scientist and the designer and programmer of TeX. The first book I seriously self-studied was Concrete Mathematics by Knuth, Ron Graham and Patashnik with beautiful stuff on the Fibonacci series, the Pascal triangle, combinatorial identities, generating functions and numbers and divisibility. It's a beautiful book. I haven't watched the ( entire ) lecture yet, i parked it on my watch-queue.

Poetry in mathematics.

While I was looking for 'poetry in mathematics', all I could find was this article in the Journal of on-line Mathematics and its Applications (volume 6 October 2006) by JoAnne Growney called Mathematics in Poetry.


As I find it hard enough to describe what I mean by Poetry in mathematics, in my native language Dutch, I won't even give it a try in English. But I would like to show this snippet of math as an example of what I consider deeply poetic. Although the context is math, to me this is poetry, period.

\[\begin{aligned}
1^2 &= 1^3\\
(1+2)^2&=1^3+2^3\\
(1+2+3)^2&=1^3+2^3+3^3\\
(1+2+3+4)^2&=1^3+2^3+3^3+4^3\\
(1+2+3+4+5)^2&=1^3+2^3+3^3+4^3+5^3\\
(1+2+3+4+5+6)^2&=1^3+2^3+3^3+4^3+5^3+6^3\\
\cdots &= \cdots
\end{aligned} \]

$(1,9,36,100,225,441,\cdots)$.

Analytical function representing the Fibonacci series

The MST209 exam has a different format than MS221 and M208 have. In 2006, for example, the format was as follows:
Part A. 15 multiple-choice questions, 2 marks each = 30 points. ( 1 hour )
Part B. 8 questions, 5 marks each = 40 points. ( 1 hour 15 min )
Part C. 3 out of 7, 15 marks each = 45 points. ( 45 min )
Yes. Maximum score is 115. Scores above 100 are set to 100.
The exam looks doable. And again questions on eigenvalues and eigenvectors. That would be three in a row: MS221, M208 and MST209. Considering the fact that one can prove Binet's formula for the Fibonacci numbers with them it's worthwhile having it firm under your math-belt.

There is also an analytical function for the Fibonacci numbers which rounded, gives an exact Fibonacci number if the input variable is an integer. Here is the related math.

Let $F_n = F_{n-1} + F_{n-2}, F_0=0, F_1=1$, show that $Fa_n=\frac{1}{\sqrt{5}}e^{n \cdot \log{\phi}}$, where $\phi$ is the Golden Ratio or $\frac{1+\sqrt{5}}{2}$. ( Round $Fa_n$ to get $F_n$. )

If we define the elements $F_{n}$ and $F_{n+1}$ as the vector $s_n= \left(
\begin{array}{c}
F_{n+1}\\
F_{n}
\end{array}
\right)$
then $F_n$ simply becomes
$F_n= \left(
\begin{array}{cc}
1 & 1\\
1 & 0
\end{array}
\right)^n
\cdot s_{0}$.

We can calculate the power of a matrix by diagonalizing the matrix. And this is where eigenvalues and vectors come in. If $\lambda_1, \lambda_2$ are eigenvectors with respective eigenvectors $E= \left( e_1, e_2 \right)$ we get $F_n= E^{-1}
\cdot
\left(
\begin{array}{cc}
\lambda_1^n & 0\\
0 & \lambda_2^n
\end{array}
\right)
\cdot
E
\cdot s_{0}$

The eigenvectors are the roots of the characteristic equation $\left|
\begin{array}{cc}
1-\lambda & 1\\
1 & -\lambda
\end{array} \right| = 0$ and are thus $\frac{1}{2} + \frac{1+\sqrt{5}}{2}$ and $\frac{1}{2} - \frac{1+\sqrt{5}}{2}$.

( TO BE CONTINUED ... )

Fibonacci computational system

Exercise.

2.15. (Fibonacci computational system) Prove that each positive integer admits a unique representation in the form $a_1f_1 + a_2f_2 + \cdots$, where $f_n$ are the Fibonacci numbers, each of the numbers $a_i$ is either $0$ or $1$, the number of ones in the representation is finite, and no two subsequent elements of the sequence $a_i$ are equal to $1$ simultaneously. For example, the first few representations are $1 = f_1$, $2 = f_2$, $3 = f_3$, $4 = f_3 + f_1$, $5 = f_4$, $6 = f_4 + f_1$, $7 = f_4 + f_2$. (Pay attention to the fact that the number $f_0 = 1$ is not used in this computational system, so that the Fibonacci sequence starts with $1,2,3,5,8,\cdots$). Invent algorithms for converting numbers from the Fibonacci system to the decimal positional number system and back, and algorithms for adding and multiplying numbers written in the Fibonacci sequence.

( "Lectures on Generating Functions by S.K. Lando, AMS 2003" )

I like problems like this. Haven't solved it yet, I am working on it.

Off and on I study the book "A course in enumeration - GTM238, by M. Aigner. Springer 2007", a book for graduate students so I need a lot of extra reading to understand the book. A good companion for Chapter 1 is the well known Concrete Mathematics by Ron Graham, Don Knuth and Patashnik. For chapters 2 and 3, mostly about generating functions, I use the book as mentioned above by Lando. - Generating functions are among the mathematical objects I love most. The power of GFs are only limited by our own imagination.

Exponential Generating Functions

An exponential generation function (GF) representing the sequence $(a_n)$ is a GF of type $F(x) = \sum_n a_n \frac{x^n}{n!}$.

Zero friends paradox

(Dutch) mathematician Ionica Smeets explains why your friends ( very likely ) have more friends than you do. What if you have zero friends like me? Would that be a paradox? Ionica Smeets and one of her friends (...) have a very nice website about mathematics, unfortunately it is in Dutch. If you still want to have a look go here. They maintain a list of famous, yet still living mathematicians. Don Knuth, Ron Graham and Martin Aigner are not on that list. But Terence Tao is. ( ... )
( UPDATE: Corrected after comment received. )

Generating functions demonstrated

Yes! Solved a problem ( well, just an exercise from Aigner's book, A course in Enumeration, which I particularly like ). Let me explain.

The problem was as stated as folows. Find $a_n$ such that
$$\sum_{k=0}^n {a_k * a_{n-k}} =1, \text{ for all } n$$.

In the case of a sequence of only two items this means that the following two statements must be true:
$a_1 * a_1 = 1$,
$a_1 * a_2 + a_2 * a_1 = 1$

We can simply see that the first two items of the sequence must be $(1,\frac{1}{2})$ since $1 * 1 = 1$, and $1 * \frac{1}{2} + \frac{1}{2} * 1 = 1$.

But we are looking for an infinite sequence! Would such a sequence at all exist? Well, it exists and there are probably several ways to find it. I used the theory of generating functions. As I explained earlier in my blog generating functions are formal power series representing infinite sequences.

Since the generating function of the sequence $(1,1,1 \cdots)$ is $\frac{1}{1-z}$, we know,if $g(z)$ is the generating function of the sequence we are looking for, that :
$${g(z)}^2 = \frac{1}{1-z} \Leftrightarrow $$
$${g(z)} = \sqrt{\frac{1}{1-z}} \Leftrightarrow $$
$$g(z) = (1-z)^{-\frac{1}{2}}.$$
But this is simply Newtons binomial formula, so the sequence we are looking for is: $$a(n) = C(\frac{2n-1}{2}, n)$$ with first five items:
$$(C(-\frac{1}{2},0), C(\frac{1}{2},1), C(\frac{3}{2},2), C(\frac{5}{2},3), C(\frac{7}{2},4), \cdots) = $$
$$(1,\frac{1}{2},\frac{3}{8},\frac{5}{16},\frac{35}{128}, \cdots)$$.

This is why I find generating functions beautiful and incredibly powerful.

Fibonacci Trivia

A while back I wrote that the number of ordered partitions ( called compositions in the Handbook of Discrete Mathematics ) of n of length k is C(n-1,k-1). It seems that the case where no 1's are used reduces that number to F(n-1) ( where F means the Fibonacci sequence ). I haven't been able to figure out a proof yet though. I just find it fascinating how often this number actually pops up.

Example.
The partitions of 6 are.
6
5-1
4-2
4-1-1
3-3
3-2-1
3-1-1-1
2-2-2
2-2-1-1
2-1-1-1-1
1-1-1-1-1-1
Or, a total of 11.

Ordered partitions with no 1s used are:
6
4-2
2-4
3-3
2-2-2
Or a total of 5, which is equal to, as expected F(5) = 5.

Partitions of length three are:
4-1-1
3-2-1
2-2-2
Or, a total of 3.

Ordered partitions of length three are:
4-1-1
1-4-1
1-1-4
3-2-1
3-1-2
2-1-3
2-3-1
1-2-3
1-3-2
2-2-2
Or a total of 10, which is equal to, as expected C(5,2) = 10.

Recurrence equations

Back in MST121 I learned that the solution of the following first order recurrence equation
$$a_n - 5 a_{n-1}=0 $$
is
$$a_n = a_0 * 5^n.$$

I have been playing around with Mathematica and digging in Discrete Mathematics books and I am now able to solve equations of the type $a_n - c_1 \cdot a_{n-1}=f(n) $, for example if $a_0=1$ the solution of
$$a_n - 5 a_{n-1}=n^2 $$
is
$$a_n = \frac{1}{32}(-8n^2-20n-15+47 \cdot 5^n).$$

Mathematica has a very nice function for solving recurrence equations ( of any order ) which is called RSolve which I only used to verify my own solution. The key to solving recurrence equations of the first order is always finding some sort of sum. Like the sum of the first $n$ integers, which is $\frac{1}{2} n(n+1)$, is in fact the solution of $a_n - a_{n-1} = n$, with $a_0=0$.

M208 TMA03 Question 4

Done in draft. Question about finding an orthogonal base of some abstract vector space. Not really difficult considering the marks assigned ( 20 ).

In MST121 / MS221 we learned to find the closed form for the Fibonacci sequence. Or solving the recurrence equation $a_{n} - a_{n-1} - a_{n-2} = 0$, equations of this type are called homogenous linear recurrence equations ( of the second order ). Inhomogenous equations have a function of n on the RHS. An inhomogenous recurrence equation of the first order is for example $a_{n} = 2 a_{n-1} + n$. The solutions of this equation consist of a homonegenous part and a particular part. ( More later. )