[Hyper 02a] Counting positions mathematically

I mentioned in [Hyper 02] that there is a mathematical way of counting positions in hypergammon. Here is an outline of how that works. It starts with factorials.

Factorials

The factorial of a number n (written n!) is the product of the positive integers less than and equal to n. For example, 9 factorial is

9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362,880

Combinations

A simple and handy formula for counting things is the combination formula, which is:

C(n,m) =

m! × (n − m)!

It tells you the number of ways m items can be selected from a collection of n items when the order doesn’t matter. For example, the number of ways 5 cards can be chosen from a deck of 52 is

C(52,5) =

5! × 47!

= 2,598,960

Arrangements

Another handy formula tells how many ways a given number of checkers can be arranged on a given number of points. For example, how many ways can 2 checkers be arranged on 3 points? The answer is 6, and we can list the possibilities:

(1,1), (1,2), (1,3), (2,2), (2,3), and (3,3)

Here is a formula that gives you this number. The number of ways m checkers can be arranged onto n points is

D(n,m) = C(n + m − 1, m)

Bearoff Positions

Take, for example, the number of bearoff positions in backgammon. A “bearoff” position is where all off one player’s checkers are in his home board or borne off. The number of bearoff positions for one player is

D(7,15) = C(21,15) =

21!

15! × 6!

= 54,264

The “15” is the number of checkers we have to play with, and the “7” is the number of points those checkers can be arranged on. The reason we use 7 instead of 6 is that some checkers might be borne off, so we include the bearoff tray as one the locations that a checker can be at.

Arranging White Checkers in Hypergammon

Here is another example. How many ways can up to 3 white checkers be arranged on a backgammon board? There are 26 locations for the checkers — the 24 regular points, plus the bar, plus the bearoff tray. The number of ways of arranging 3 checkers on 26 points is

D(26,3) = C(28,3) =

28!

3! × 25!

= 3,276

Counting Hypergammon Positions

Now we have the tools to count hypergammon positions. The easiest way to do the calculation is tackle it in four steps.

No points occupied by black. Suppose all of black’s checkers are either on the bar or borne off (so black has no checkers on points 1 through 24). There are 4 ways that black can arrange his 3 checkers this way. (He can have between 0 and 3 checkers on the bar, with the other checkers being borne off.) Earlier we calculated that there are 3,276 arrangements for 3 white checkers when there are no black checkers in the way. The total number of combinations therefore is

4 × 3276 = 13,104 positions
One point occupied by black. Suppose black occupies one of the regular points 1 through 24. There are 24 different points that could be. The other 2 black checkers can be in three locations (the occupied point, on the bar, or borne off). That is D(3,2) = 6 different ways to arrange the other 2 black checkers. The white checkers can be in any of 25 locations (the 23 available points, or on the bar, or borne off), so in D(25,3) = 2,925 ways. The total number of combinations is

24 × 6 × 2925 = 421,200 positions
Two points occupied by black. There are C(24,2) = 276 ways to choose the 2 points for black to occupy. The other black checker can be on either of those two points, on the bar, or borne off, that is, in 4 possible places. The white checkers can be arranged among 24 other locations (the 22 available points, on the bar, or borne off), so in D(24,3) = 2,600 ways. The total number of combinations is

276 × 4 × 2600 = 2,870,400 positions
Three points occupied by black. There are C(24,3) = 2,024 ways black can occupy 3 points with 3 checkers. The white checkers can occupy any of the other 21 points, or they can be on the bar or borne off. Thus, white’s checkers can be arranged in D(23,3) = 2,300 ways. The total number of combinations is

2,024 × 2300 = 4,655,200 positions

Here are the final results:

0 points occupied by black 13,104
1 point occupied by black 421,200
2 points occupied by black 2,870,400
3 points occupied by black 4,655,200
7,959,904 legal positions

Amazingly, this is the same answer we got from the computer program in [Hyper 02].

Post Response

Your Name:
Your E-Mail Address:
Subject:
Message:
If necessary, enter your password below:
Password:

0 points occupied by black	13,104
1 point occupied by black	421,200
2 points occupied by black	2,870,400
3 points occupied by black	4,655,200
	7,959,904	legal positions