Dominoes, Eulerian Circuits, and Spanning Trees

Brendan D McKay, Australian National University (speaker)

and

Bob W Robinson, University of Georgia

Suppose you have all the possible dominoes on n symbols, without blanks or doubles. For example, for n = 5 the dominoes are 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, and 4-5. Place one down at random, then extend it in a line to the right. To make each move, choose uniformly at random from amongst the remaining dominoes that are legal. For example, one possible sequence of moves is 2-3 3-4 4-1 1-5 5-2, at which point you have to choose fairly between playing 2-1 and 2-4. Sometimes this process will continue until no dominoes are left: 2-3 3-4 4-1 1-5 5-2 2-1 1-3 3-5 5-4 4-2 but other times you will get stuck early: 2-3 3-4 4-2 2-5 5-1 1-2. Define p(n) to be the probability that you manage to play all the dominoes.

Despite the long history of this problem, which dates back to Reiss, Lucas and Tarry in the previous century, there seems to be scant prospect of finding a simple exact formula. Instead, we seek the asymptotic behaviour. Firstly we write p(n) in terms of the number of distinct linear arrangements, which correspond to the eulerian circuits in a complete graph. That in turn leads us to spanning trees in regular tournaments and a difficult integral in n complex dimensions. Finally, we estimate the integral to obtain a delightfully simple answer.