Thursday, November 18, 2010

Determine when to accept a double in backgammon

In this blog post I will examine the precise conditions when to accept a double in backgammon.

The question and it's answer whether to accept a double probably is a classical result in backgammon. Guided by mathematics it is primarily concerned with the expected value of a game.

To recap: If you win a game normally you win the amount indicated by the doubling cube. If you win a gammon i.e. without your opponent bearing off a single checker, you win twice the amount on the doubling cube. If the opponent hasn't borne off any checkers and still has checkers in your home board you win a backgammon and gain triple the amount indicated by the doubling cube.

Let's assume the change of winning the game normally is \(p_{n}\), that of winning a gammon is \(p_{g}\) and that of winning a backgammon is \(p_{b}\). In similar fashion define the chances of losing as \(q_{n},\,q_{g}\) and \(q_{b}\).
Furthermore, let\(v\) be the current value of the doubling cube.

If your opponent offers you a double and you refuse you lose \(-v\) points, guaranteed. But if you accept the double the expected value will be

2vp_{n} + 4vp_{g} + 6vp_{b} - 2vq_{n} - 4vq_{g} - 6vq_{b} = 2v((p_{n} - q_{n}) + 2(p_{g} - q_{g}) + 3(p_{b} - q_{b}))

So you should accept a double if the above expression is greater then \(-v\).

Lets further assume that the changes of losing are winning a gammon are backgammon are zero. Then the above equality simplifies (using the relation \(q_{n} = 1-p_{n}\)) to \(2p_{n}-1 \ge -\frac{1}{2}\) or \(p_{n} \ge \frac{1}{4}\). This is a very classic result of backgammon. For example, it is stated, without proof, in 501 essential backgammon problems, considered to be the bible of backgammon.

In order to gain an other insight we assume that the changes of winning or losing a backgammon or winning a gammon are zero, but losing a backgammon is a possibility. (For example your trapped on the bar while your opponent already beared off succesfully at least one checker.)
The above equations reduces to \(p_{n}-q_{n}-2q_{g} \ge -\frac{1}{2}\). Now the relation \(p_{n} + q_{n} + q_{g} = 1\) tells use that \(q_{n} = 1 - p_{n} - q_{g}\). This simplifies our equations to \(p_{n} \ge \frac{1}{4} + \frac{1}{2}q_{g}\). This tells use you have to have a greater change of winning if your are to accept a double when there is a change of losing a gammon.

The above equations and a keen insight in the chances at the backgammon board can help to guide your decision of taking a double or not.
In an other blog I will investigate the conditions of offering a double.

MinuteMath: A bite size math problem a day

I Recently subscribed to the The Mathematical Association of America twitter feed. The most important reason for me is their daily MinuteMath.

The MinuteMath is a daily bite size mathematical problem of varying difficulty. All the problems are multiple choice and hints, solutions and classifications are given.

It is a fun way to distract your mind for a moment and figure out a interesting little problem. If your interested start following @maanow.

Sunday, October 24, 2010

MathJax: Include mathematics non-obtrusively

In this blog post I will explain the use of MathJax, a javascript based display engine for mathematics.

In an early post I pointed out that has a very nice solution for producing beautiful LaTeX on the web. Unfortunately as of October 31 2010 their service has shut down. As a result the LaTeX on my blog did not render any more.

So a tweet alerted me to mathjax, a display engine for mathematics. With mathjax it is possible to write mathematics in LaTeX or MathML and the javascript based engine will make a beautiful image.
As a bonus mathjax allows you to scale the mathematics, view the source in LaTeX or MathML and choice the rendermode i.e. straight to MathML or via their custom fonts.

Seeing their beautiful examples I decided that use mathjax for this blog. So once again, mathematics can be viewed in splendid glory.


Saturday, October 16, 2010

Why I changed my twitter picture

In this blog I will explain why I changed my twitter picture.

After a presentation I gave at the University of Utrecht someone in the audience came up to me and asked the following question: "Can I follow you on twitter?"

This flattering request made one thing clear. My twitter pictures has no relation with me. How could anybody know my account from the following picture?

In order to be more accessible, I changed my picture. For now I have changed it to the picture I use for my blog. Maybe in the future I will pick a fancier picture.

Saturday, August 28, 2010

Inputting Unicode characters in Ubuntu

This blog is a reminder for myself how to use the keyboard to input Unicode characters in Ubuntu.

Somethings I just can not remember. Every time I need to enter a Unicode character I realize that I do not remember how to do this in Ubuntu, without resorting to graphical character picker.

So this post will settle the score once and for all, and hopefully after this I will be able to remember it. (At least I will be able to come here for reference.)

The keyboard shortcut to enter a Unicode character in Ubuntu is:

Ctrl+Shift+u <Unicode>

For example to enter a € symbol type Ctrl+Shift+u 20ac. All that is left is learning usefull Unicode codes.

Here's a unicode character map

Wednesday, August 18, 2010

Maven Versions Plugin

I was going to write about the maven versions plugin. But an other blogger beat me to the punch.
So without restating what can be found there, I will point out what John Ferguson Smart has to say on the maven versions plugin

Tuesday, August 17, 2010

Blogger Stats

In this post I will outline a service Blogger is providing: Stats

I recently switched Blogger dashboard. Instead of the standard Blogger dashboard, I opted for the "Blogger in draft" dashboard. Among other things, this dashboard sports a new button: "Stats".
Behind the Stats button there is a lot of information about the traffic your blog is attracting.

There are four menu's : Overview, Posts, Traffic Source and Audience. Every menu shows information over on of the following periods: Now, Day, Week, Month and All Time. The Overview menu shows an overview of the other three menu's. The post menu shows which posts attracted how many page views.
The Traffic Source menu show referring urls, referring sites and the search keywords which were used to find your posts.
Finally the Audience menu shows a summery of the location from where the request for your blog came and which browser and operating system were used.

So what can this information tell you? Well, for one, do not underestimate the number of page views. Although I have two subscribers to my blog, both of which I know personally, I never thought that my blog would be read.
But contrary to my believe and looking at some of the comments, my posts does get read. Blogger Stats can help you realise that you have an audience.

Furthermore, It gives you a sense of direction. By seeing which post were read the most, you know what your audience likes. For example the top three post in number of page views for this blog are.

  1. Counting Unlock Patterns
  2. Counting Backgammon End Positions
  3. Tethering made easy with easytether

So I presume that writing about my latest experience of playing online backgammon in the train while my laptop was tethered to my android phone, which I had to unlock to set up the connection, would be a show stopper.

But most of all, Blogger Stats is like an addiction. It is hard to resist the urge of checking the stats every now and then, to see how many page views you got for this day.

Saturday, August 14, 2010

Google Library: Organizing your bookshelf

In this blog post I will introduce Google Library.

I recently started to use Google Library as a means to organize my bookshelf. This service of Google can be reached by You will find a link called "My library" which will take you to your library.

The library is subdivided in shelf. There are five standards shelfs: Reviewed, Favorites, Reading now, To read, Have read. Custom shelfs can be added as well.
Every shelf can be made private or public. Public shelfs will be published online so others can see them.

Adding books to shelfs is very easy. Search a book. Every book on the result page has a link "Add to my library". A drop-down menu let's you choose the shelf. Once saved the book will appear in the right shelf in your library.

That wraps up this nice service Google is offering.

Spreading Knowledge

In this post I will outline various forms of spreading knowledge.

I signed the manifesto for software craftsmanship and I take my responsibilities serious. Not only should you maintain a high standard for your self, you should help others in becoming software craftsman.
One way in doing this is by spreading knowledge.

There are various ways one can share and spread knowledge. Any form of communication with the intent of explanation is a form of spreading knowledge. Examples of communication forms abound. Let's group these forms according to the number of senders and receivers.

We will distinguish the following numbers: one and many. Below I have created a table listing the various combinations of senders and receivers.

11One-on-one tutoring
1manyPresentation or blog
many1Open outcry or a forum
manymanyOpen discussion

In seeing these summary one can check off a list of participation in various forms of communication. For example I now realise that I do not often participate in a forums.
So I will challenge myself in actively seeking out opportunities to contribute to forums.

Saturday, August 7, 2010

Java Puzzler: 1 July 1937

In this blog post I will discuss the idiosyncrasies of Java and the date of 1 July 1937 in the Netherlands. I encountered this as a bug at work.

Look at the following code. Note that my timezone is set to Europe/Amsterdam.

Calendar calendar = Calendar.getInstance();
  calendar.set(1937, 5, 30, 23, 59, 59);

  calendar.add(Calendar.SECOND, 1);

I will tell you the output of line 4. It is Wed Jun 30 23:59:59 CEST 1937. What would you expect to be the output of line 7?
If somebody would ask me this question, I would be very suspicious. Why ask this question if the answer should obviously be Thu Jul 01 00:00:00 CEST 1937? What is going on here? But for me, without resorting to psychology, there is no other answer thinkable then the obvious.

As it turns out the answer on my machine consistently is: Thu Jul 01 00:00:28 CEST 1937.

The crucial piece of information is that the timezone is set to Europe/Amsterdam. With the timezone set to something else e.g. Europe/London, the output is the expected Thu Jul 01 00:00:00 BST 1937. So what is going on here?

As it turns out, on 1 July 1937 the dutch government decided to changed meridians for timekeeping. Apparently in 1908 a the government introduced a national means to keep time. The time in the Netherlands was determined by the time in Amsterdam. At first the Westertoren was picked as defining meridian (4° 53' 01.95" east longitude) resulting in a time difference of 19 minutes and 32 seconds with GMT.
On the first of July 1937 the 5° meridian was used to tell time to give an even time difference of 20 minutes with GMT. But this produced a 28 seconds skip in time keeping. So the first 28 seconds of 1 July 1937 do not exist in the Netherlands. This is the cause of the peculiar behavior of the above code.

reference (in dutch).

Tethering made easy with easytether

In this blog post I point at a very easy way of tethering an android phone to a Ubuntu machine.

Ever since I got my android phone, I was looking at a way to tether it to my phone. There were options available but none to my liking. You either had to tether to a windows machine or get root access to the phone. Because I exclusively use Ubuntu as an operating system and I feel a little uneasy about rooting my phone, I was left tether-less.

Not so any longer. I accidentally stumbled upon a post explaining how to tether Ubuntu to your phone via easytether.

The instructions in the above post worked off the shelf, so I can now tether easily. I even made a little script to setup the connection so it is as easy as executing one command.

Sunday, August 1, 2010

Increasing Blog Posts

In this post I will outline ways to increase the number of blog posts.

Every blogger will go through various learning stages. Looking at my blog archive it is clear that it lacks a steadiness. Sometimes post are few and far between. So I thought up a means to get to a more more consistent level of publishing.

The modus operandi I am following now is outlined below.

  • Start a new post for every little idea you have.
  • Over time flesh out the posts.
  • Reread and rewrite posts a few times
  • publish
  • repeat

In this modus there will be post that aren't yet published, and can be used in times of "writers block" to fill the gap.

Thursday, July 29, 2010

Counting Backgammon End Positions

In this blog I will count the number of end positions in backgammon.

Recently I picked up backgammon again. But I could not put my mathematical mind to rest. I got interested in the question of how many end positions backgammons has.
In order to count the number of positions I will introduce the following terminology. The number of stones you own in the end position will be denoted by \(m\). The number of points used available is \(n\). \(o\) is the number of stones owned by the opponent, which occupy \(p\) points of the available \(n\).
So in the following example, playing as black, the following equalities apply \(m=8,\,n=6,\,o=2,\,p=1\).

Let's look at a special case first. Lets assume we have a contact-less end position. So \(o=0\). I will proof that the number of backgammon end positions with \(m\) stones and \(n\) points is

m + n - 1 \choose m

To see this equality, study the following diagram, which corresponds with the figure above if you ignore the opponent stones:

Every dot corresponds with a stone. Every bar with the division between points. A moments reflection will bring the insight that every diagram of this kind corresponds to a backgammon end position and vice versa, every backgammon end position can be described by such a diagram. This proofs the stated equality.

With the result of this special case we can answer the main question: How many backgammon end positions exist with \(m\) stones distributed over \(n\) points of which \(p\) are occupied by \(o\) opponent stones? This number is exactly

{n \choose p} {o - 1 \choose o - p} {m + n - p - 1 \choose m}

The proof of the above equality comes from the following insight. The opponent stones are distributed over \(p\) points. there are \(n \choose p\) ways of picking the occupied points.
For a point to be occupied it must at least contain one opponent stone. So of the \(o\) opponents stones, we can freely distribute o - p opponent stones over \(p\) points. This is the special case we counted already, so this can be achieved in \({(o-p) + (p-1) \choose o - p} = {o - 1 \choose o - p}\) ways.
This brings us to the final factor. It represent the \(m\) stones which should be distributed over the remaining \(n-p\) points. Again this is given by our preliminary result of \({m + n - p - 1 \choose m}\) ways. This proofs the stated result.

In conclusion: the number of backgammon end point positions with \(m\) stones distributed over \(n\) points of which \(p\) are occupied by \(o\) opponent stones equals

{n \choose p} {o - 1 \choose o - p} {m + n - p - 1 \choose m}

Null Object Pattern

In this post I will summarise the Null Object Pattern.

The null object pattern is a means to forgo null checks. The following example will be used to explain how the null object pattern can be used to reach this goal.

public Person getPerson()
  return person;

 public void showName()
  Person person = getPerson();
  String name = "unknown";
  if (person != null)
   name = person.getName();
  System.out.println("name: " + name);

In my opinion a few there are thing wrong with this code.

  • Different call flow. Because of the null check there are two possible paths through this code. If this is the only point at which this occurs, it would not be a big problem. But
  • Caller is responsible. The caller is made responsible to check if the returned value is correct. By placing the burden at the callers side probably means a lot of duplicate boilerplate code in checking for null values.
  • Error prone. You only have to forget the null check once and it will blow up in your face with a NullPointerException.

The null object pattern is a means to remedy these points. In the following example I refactored the original code.

class UnknownPerson extends Person
 public String getName()
  return "unknown";


 public Person getPerson()
  if (person == null)
   return new UnknownPerson();
  return person;

 public void showName()
  Person person = getPerson();
  System.out.println("name: " + person.getName());

With the introduction of the UnknownPerson all the mentioned problems are solved.

  • Same call flow. The calling code does not have to differentiate between a null value and a legitimate value
  • Callee is responsible. The callee is now responsible to check if the returned value is defined. By placing the burden at the callee side there is a single check so no duplication of code. So
  • Less error prone. Because the null check is in a single location there are less oppertunities for making a mistake.

This summarises the null object pattern.

Saturday, July 24, 2010

Introduction to Software Development - Part 2

In this blog I will outline the second instalment of the introduction to software development I had with a friend of mine.

In a previous post I told the story of introducing software development to a friend. In this second run, we took on a little project to hone our developing skills.

We looked into Mancala. It is a game in which stones get sown around the board. The exercise was meant to develop a feel for architecture.

We had a lot of discussion about responsibilities. Which object should be responsible for a certain task? I think that the question of responsibility is a very good to get your bearing while developing an application.

In the subsequent meeting we will finish this little project.

Fresh Install

In this blog I will outline the pieces of software I would install if I would be doing a fresh install of a computer. It is mainly written for a personal reference.

First of all, the operating system. I started using Ubuntu about three years ago and I really like it. So the primary software will the operating system, and it will be Ubuntu.

Saturday, June 26, 2010

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.


Friday, June 25, 2010

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.

Sunday, June 20, 2010

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


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.

Wednesday, June 2, 2010

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.

Wednesday, May 26, 2010

BloGTK: Blogging on the Train

In this blog post I will explain how this post is written while riding on the train.

I commute a lot. Every working day I ride the train. A single trip takes one hour. This is a nice amount of time to get things done. Reading a book, practicing a code Kata or pondering the big questions in life. Now I can add blogging to this list.

Seeing that I spend a lot of time in a train, it seemed a nice way to create a greater supply of post. Although a promise is made to introduce Internet in trains by the end of the year, I have no Internet connection while I am on the train. So it is not possible to connect to the blogger site and manage my posts.
So I started a search for a blogging client. The search was over quickly. I found BloGTK in the repository.

Unfortunately that version is using a package which is not available in Ubuntu 10.04 - Lucid Lynx. Luckily building from source was a breeze.

So this is the first of many posts while riding the train.

Friday, May 21, 2010

Estimating Collisions in URL Shortening

In this blog post I estimate the time before the first collision for URL shorteners such as occurs.

Increasing tweet density

In this post I will summaries the various ways in which I will increase the number of tweets over time.

In a previous blog post, I outlined reasons to start using twitter. Although the reasons I stated there are still valid, it does not help you to tweet regularly.

Since I started twittering, the density of my tweets fluctuated. In this blog post I will outline various ways to produce a steadier stream of tweets. It will be a reminder for myself, if I every find myself in calmer tweet weather.

List of regular tweet opportunities:

  • Tweet what you are reading.
  • Tweet what you are pondering
  • Tweet new admissions to your blog
  • Tweet your experiences as a commuter

Although the list isn't very long, it is a start for a steadier twitter stream. Let's find out how it will hold up against time.

Tuesday, May 11, 2010

Pitfalls of Reflection

In this post I will discuss a pitfall of the use of reflection in Java. Specifically how reflection can obscure and even change the semantics of a piece of code.

What is wrong with the following example of JavaBean naming convention?

public Boolean isCorrect() {
    /* implementation not shown. */

Did you spot the capital B on the Boolean return type? According to the JavaBean naming convention the property does not fall under the special rules for booleans and should be named accordingly.

public Boolean getCorrect() {
    /* implementation not shown. */

Although there is a sleight syntactic difference, the apparent semantic difference is non-existent. According to William Shakespeare:

A rose by any other name would smell as sweet

Enter reflection. By using reflection it is possible to perform hugely different behaviour depending on the name of a method. The following whimsical example is a clear demonstration of this fact.

Class aClass = ReflectedClass.class;
Method method;
    method = aClass.getDeclaredMethod("isCorrect");
catch (NoSuchMethodException e)

So one of the pitfalls of reflection is the hidden semantics associated with code. Stated in other words: the influence of code can not be inferred by the syntactic definition of that code.

Saturday, April 10, 2010

Qwickie: a usefull eclipse plugin for Wicket Development

In this post I will introduce Qwickie, a usefull eclipse plugin for Wicket Development.

In my daily work I develop software applications. As a web framework we use Wicket, a component based framework with a clear separation of the presentation and the logic.

The connection you between presentation and logic is made via "wicket:id"'s. (See the wicket examples page how this is done.) I found myself executing the following behavioural pattern or it's inverse a lot.

  1. Seek a wicket:id in a webpage
  2. Find corresponding wicket:id in the code

Recently I came across a nice little eclipse plugin which speeds up this pattern. It is named Qwickie, and it facilitates the following use cases:

  • Navigate from java code elements to the corresponding html element via wicket:id
  • Show the corresponding html fragment from the java code element

Both actions are performed by clicking the wicket:id while holding down the ctrl button. This shaves off time following the association between presentation and logic.

Tuesday, February 23, 2010

Google Code as Maven Repository

In this post I will explain how to set up a Google code project as a maven repository.

I like Maven. The fact that I can checkout some code and let Maven figure out all the dependencies is wonderful. I know that there are developers out there who will criticize Maven. But in my opinion, a lot of the critique is not really justified.

I also like Google code project hosting. It is very easy to start a project on Google code and have a mature environment for software development.

When I was looking around for a way to publicize my own artefacts I came across the idea of using project hosting on Google code as a maven repository. Because It took me a while to get everything up and running, I will outline the steps I had to take.

As a precondition, I assume a you have a Google code project where you can submit to and a working maven project.

  1. Add the maven repository.

    We will be using a plugin which is found on the maven repository.
      Repository for Maven

  2. Add the wagon-svn plugin

    We are going to use the wagon-svn plugin which will do all the heavy lifting for us. Make sure to use the latest version.

  3. Come up with a naming scheme.

    We are going to create repositories in the svn tree. I propose the following convention. Create a maven directory at the top of the svn tree. This directory will contain a repo directory and a snapshot-repo.

    This can be configured in the following way.
          Maven Repository for minimal-examples
          Maven Repository for minimal-examples (snapshot)

Now we are all set to start deploying! By running the command maven deploy, the svn-wagon plugin will deploy the artifacts to the repository. The first time you will have to accept the certificate that the Google code project return.
Furthermore, you will have to authenticate yourself with your username and password which are known to the Google code project. You can take up this information in your ~/.m2/settings.xml, so you do not have to enter this information all the time.


This wraps up the set up for using a Google code project as a Maven repository.

Friday, February 5, 2010

Observation on Binary Trees

In this post I will proof the following observation:

Let \(T\) be a binary tree, \(I\) the number of internal nodes and \(L\) the number of leaves in \(T\) then

L = I + 1

We will proof this fact by observing the following. Every binary tree can be "grown" by replacing leaves with trivial binary tree.
A minimal criminal C
Assume to the contrary that not every binary tree can be grown by replacing leaves with trivial binary trees. Then there must exist a smallest binary tree which can not be grown in such a way. Call it \(C\).
Notice that both subtrees of \(C\) are smaller binary trees. Because \(C\) was the smallest tree which could not be grown, both subtrees can be grown.
But the following description grows \(C\).

  1. Take trivial binary tree
  2. On the left leaf use the description for the left subtree of \(C\)
  3. On the right leaf use the description for the right subtree of \(C\)

This contradicts the fact that \(C\) was the smallest such tree. We are forced to drop the assumption that there exist a binary tree which could not be grown. Therefore all binary trees can be grown.

Now for the trivial binary tree is is clear that

L = I + 1

And when a leaf is grown both \(L\) and \(I\) go up by 1, maintaining the equality. From the above observations one can conclude that the equations hold for all binary trees.