Counting Graphic Sequences

In this post I give the the number of graphic sequences of length 0 through 6.

The numbers were counted by iterating over all sequences using a custom made graphic sequence iterator.

length	0	1	2	3	4	5	6	7
#	1	1	2	4	11	31	102	342

Iterating Monotonic Decreasing Sequences

In this post I will show an algorithm to iterate over all monotonic decreasing sequences of non-negative integers of length at most \(m\) and height \(n\).

In a previous post I counted the number of monotonic decreasing sequences of length at most \(m\) and height \(n\). In order to study these objects it is nice If you can generate them all on a computer.

Furthermore, it would be nice to "visit" them one at a time. This cuts down on memory consumption, because then only one sequence has to be in memory at any time. In this blog post I will outline an algorithm to generate all the monotonic decreasing sequences of non-negative integers of length at most \(m\) and height \(n\) in lexicographical order.

Counting Monotonic Decreasing Sequences

In this blog post I will count the number of monotonic decreasing sequences of length \(m\) and height \(n\).

I recently got interested in graphic sequences. A graphic sequence is an example of a monotonic decreasing non-negative integer sequence i.e. a sequence which never goes up. For example

4,3,3,3,1,1

The next terminology will be used throughout this blog. The height of a sequence is the greatest element which occurs in the sequence. For monotonic decreasing sequences this corresponds with the first element. So the height of the sequence mentioned above is 5.

I set out to count the number of non-negative integer sequences of length <\(m\) and height \(n\). After some considerations I found an elegant manner in which to present the answer.

Consider plotting the above sequence on graph paper. We need a 6 by 5 box to plot the sequence. (Remember, it is a sequence of non-negative integers.) The graph is given below.

When the descenders are added a path is formed from the upper left corner to the lower right corner. (The descenders are in orange.) Because we have plotted a monotonic decreasing sequence the path is formed by making steps due "south" or "east". There are precisely \({m+n-1} \choose {n}\) such paths. (There are \(m+n-1\) choices to make of which \(n\) are "south").

An other relation can be deduced by examining the correspondence between monotonic decreasing sequences and south-east-paths. Let's count the monotonic decreasing sequences of length \(m\) and height at most \(n\). Notice that all those sequences are a tail-subsequence of a monotonic decreasing sequence of length \(m + 1\) and height \(n\). So one can deduce the relation

\[
\sum_{i=0}^{n} {{m+n-1} \choose {n}} = {{m+n} \choose {n}}
\]

On can count the number of monotonic decreasing non-negative integer sequences by considering a nice correspondence between such sequences and south-east-paths on grids.

Introduction to Software Development

In this blog I will outline how I introduced a friend to the art and craft of software development.

A friend of mine got interested in software development, but was not quit sure how to start. Because I have a strong opinion what constitutes "good" software development skills, I offered to guide him in his explorations in software development. This blog summarizes the first day of guidance.

In my opinion a software developer is not tied down to a single language. But an aspiring developer has to start somewhere. The language choice was made on two grounds: my own familiarity with languages and it's popularity in the field. We settled for Java.

After downloading the appropriate software development kit and setting up the PATH variable we could really start. I created the conical "Hello World!"-example using only a rudimentary text editor and the command line. We build upon the example by introducing the following concepts

• Introduction of a package
• Separation of source- and class-files
• Introduction of the classpath
• Objects

After this bare-boned example we set out to install an integrated development environment. I loaded the die in favor of Eclipse. After downloading and installing Eclipse I challenged my friend to reproduce the command line example. By emphasizing steps which are easer with the help of the IDE, my friend quickly reproduced the afore mentioned example. The following step was the introduction of test driven development. I showed my friend how a test can be used to guide the development of a new feature. Afterwards I explained him the virtues of test with respect to refactoring. The example was extended by writing test and constantly refactoring, thereby introducing the following concepts.

• Inheritance
• Method overloading
• Interfaces
• Abstract classes

The next step was to introduce version control. My friend could easily motivate the need for some form of version control. In the end we settled for subversion as our version control system. We downloaded a subversion client and extended the PATH variable. I showed him how the command line can be used to version a file, but we quickly installed a Subclipse. Along the way we created a google code project which now hosts are first steps. Guided by tests and committing our progress we enhanced the example with

• Commit often, Commit Early
• Command line arguments
• Alternate output streams
• Mocking

In the end I showed my friend coding katas. The main goal was to introduce a means to hone his programming skills without my presence. The secondary goal was the introduction of maven as build to. We agreed to do an other session. As a homework assignment my friend would do a kata a day, or more if he likes to. I pointed out "Head First Java" as a good book to learn Java.

This wraps up the summary of the software introduction I gave to a friend.