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
{
 @Override
 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.

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.

• Development
  
  • Java
  • subversion
  • maven
  • eclipse
    

    with the following plug-ins:
    

    • Mousefeed
    • Subversive
    • qwickie
    
    
  • Squirrel
  
  
• Programming Languages
  
  • Prolog
  • Haskell
  • Smalltalk
  
  
• Usefull
  
  • BloGTK
  • gtk-recordMyDesktop
  • Gedit
    with the following plug-ins
    
    • Bracket Completion
    • Session Saver
    • Snippets
    • TabSwitch
    
    
  
  
• Interesting
  
  • Geogebra
  • Processing
  • Contect Free Art
  • Combinatorial Game Suite
  
  

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.