ON THE NUMBER OF WALKS ON A REGULAR CAYLEY TREE

ERIC ROWLAND AND DORON ZEILBERGER

Abstract. We provide a new derivation of the well-known generating function counting the number of walks on a regular tree that start and end at the same vertex, and more generally, a generating function for the number of walks that end at a vertex a distance i from the start vertex. These formulas seem to be very old, and go back, in an equivalent form, at least to Harry Kesten’s work on symmetric random walks on groups from 1959, and in the present form to Brendan McKay (1983).

Consider the (infinite) regular Cayley tree where each vertex has degree m. How many walks of length n are there that start and end at the same vertex? Let’s call this number A_{m}(0, n). More generally, how many such walks of length n are there that end up at a given vertex that has distance i from the starting vertex? Let’s call that number A_{m}(i, n). The sequences {A_{m}(0, 2n)}_{n=0}^{∞} for m = 2, 3, 4 are Sloane’s \underline{A000984} (the central binomial coefficients), \underline{A089022}, and \underline{A035610} respectively [4]. For 5 ≤ m ≤ 8 these are sequences A12096r, 0 ≤ r ≤ 3. The sequences for i > 0 do not seem to be present at the time of this writing.

The generating function of {A_{m}(0, n)},

f_{m}(t) := ∑_{n=0}^{∞} A_{m}(0, n)t^{n},

supplied to Sloane [4, \underline{A035610}] by Paul Boddington, is

f_{m}(t) = \frac{2(m − 1)}{m − 2 + m\sqrt{1 − 4(m − 1)t^{2}}} .

We couldn’t find any proof of this in the literature. Stevanović et al. [6] reference Boddington’s formula without proof. After the first version of this article was written, Brendan McKay pointed out to us that the formula for f_{m}(t), as well as the formula for f_{m}^{(i)}(t) given below, are contained in [3]. Shortly after, we also received an email message from Franz Lehner, who kindly told us about Harry Kesten’s work [2]. He also mentioned Pierre Cartier’s work [1].

Nevertheless, we still believe that the present note is worth publishing, because of the elegant method of proof that should be applicable in many other problems. Of course, none of this is “deep” (by today’s state of the art), so our paper should be labeled “for entertainment only”.

More generally, we prove that

f_{m}^{(i)}(t) := ∑_{n=0}^{∞} A_{m}(i, n)t^{n},

Date: March 12, 2009.

the generating function for those walks that end up at a vertex that has distance i from the starting vertex, for any i ≥ 0, equals

f_{m}^{(i)}(t) = \frac{2(m − 1)}{m − 2 + m\sqrt{1 − 4(m − 1)t^{2}}} · (\frac{1 − \sqrt{1 − 4(m − 1)t^{2}}}{2(m − 1)t} )^{i} .

Let us remark that A_{2m}(i, n) is also the coefficient of any reduced word of length i in the expansion of (∑_{i=1}^{m} x_{i} + x_{i}^{−1})^{n} in non-commuting symbols x_{1}, …, x_{m}.

The recurrence

Obviously A_{m}(i, 0) is 0 unless i = 0, in which case it is 1. If n > 0 and i = 0, then the number of walks is mA_{m}(1, n − 1), since the first step must be to a vertex at distance 1 from the starting vertex. If i > 0 then we have the recurrence

A_{m}(i, n) = A_{m}(i − 1, n − 1) + (m − 1)A_{m}(i + 1, n − 1)

for i ≥ 1 and n ≥ 1, since any vertex whose distance is i from the starting point has exactly one neighbor whose distance is i − 1 and exactly m − 1 neighbors whose distance is i + 1.

With the same effort, we can solve a slightly more general problem.

A more general recurrence and weighted Dyck paths

Let’s consider, for any constants c_{1}, c_{2}, c_{3}, the solution of the recurrence

A(i, n) = c_{1}A(i − 1, n − 1) + c_{2}A(i + 1, n − 1), i ≥ 1, n ≥ 1;
A(0, n) = c_{3}A(1, n − 1), n ≥ 1;
A(i, 0) = δ_{i,0}.

This is a slight variation on the generic recurrence for Dyck paths. These are walks in the two-dimensional lattice with steps

U : (x, y) → (x + 1, y + 1)
D : (x, y) → (x + 1, y − 1)

that start at the origin, end at the point (n, i), and never venture below the x-axis. Let’s define the weight of such a walk to be c_{1}^{#U}c_{2}^{#D}t^{#U+#D} and the poids to be

c_{1}^{#U}c_{2}^{#D’s not touching the x-axis}c_{3}^{#D’s touching the x-axis}t^{#U+#D},

or more succinctly,

c_{1}^{#U}c_{2}^{#D}(c_{3}/c_{2})^{# irreducible components}t^{#U+#D},

where an irreducible component is a portion of a walk that starts and ends on the x-axis, but otherwise is strictly above it.

It is easy to see that A(i, n)t^{n} is the weight enumerator, according to poids, of the set of paths that terminate at (n, i), and d_{i}(t) := ∑_{n=0}^{∞} A(i, n)t^{n} is the poids enumerator of all walks that end at a point with y = i.

Let’s first compute d_{0}(t), the poids enumerator of walks that end on the x-axis (i.e for which #U = #D). This is a minor variation on the usual way of counting Dyck paths. Let a(t) be the weight enumerator for all Dyck paths according to weight, and let b(t) be the weight enumerator (also according to weight) of irreducible paths. Obviously, we have

a(t) = \frac{1}{1 − b(t)}, b(t) = c_{1}c_{2}t^{2}a(t).

That leads to the quadratic equation

(c_{1}c_{2}t^{2})a(t)^{2} − a(t) + 1 = 0

whose solution is

a(t) = \frac{1 − \sqrt{1 − 4c_{1}c_{2}t^{2}}}{2c_{1}c_{2}t^{2}} ,

and hence b(t) = c_{1}c_{2}t^{2}a(t) equals

b(t) = \frac{1 − \sqrt{1 − 4c_{1}c_{2}t^{2}}}{2} .

Now let c(t) be the weight enumerator of irreducible paths according to poids. Of course

c(t) = \frac{c_{3}}{c_{2}} b(t),

since the last step now contributes a factor of c_{3} rather than c_{2}, from which we get

c(t) = \frac{c_{3}(1 − \sqrt{1 − 4c_{1}c_{2}t^{2}})}{2c_{2}},

and consequently, d(t) = d_{0}(t), the weight enumerator of all Dyck paths according to the weight poids is

d(t) = \frac{1}{1 − c(t)} = \frac{2c_{2}}{2c_{2} − c_{3} + c_{3}\sqrt{1 − 4c_{1}c_{2}t^{2}}} .

By plugging in c_{1} = 1, c_{2} = m − 1, c_{3} = m, we get Paul Boddington’s expression.

Finally, to get the weight enumerator d_{i}(t) according to poids of all walks that wind up at a point with y = i, note that any such walk can be uniquely decomposed into W_{0}UW_{1}UW_{2}UW_{3} ⋯ UW_{i} where there are i U’s and W_{0}, …, W_{i} are ordinary Dyck paths. Their poids is the poids of W_{0} times the product of the weights of W_{1}, …, W_{i}, times c_{1}^{i}t^{i} (to account for the i U’s). Hence

d_{i}(t) = d(t)(c_{1}ta(t))^{i} = \frac{2c_{2}}{2c_{2} − c_{3} + c_{3}\sqrt{1 − 4c_{1}c_{2}t^{2}}} · (\frac{1 − \sqrt{1 − 4c_{1}c_{2}t^{2}}}{2c_{2}t} )^{i} .

Plugging in c_{1} = 1, c_{2} = m − 1, c_{3} = m yields

f_{m}^{(i)}(t) = \frac{2(m − 1)}{m − 2 + m\sqrt{1 − 4(m − 1)t^{2}}} · (\frac{1 − \sqrt{1 − 4(m − 1)t^{2}}}{2(m − 1)t} )^{i} .

Added March 17, 2009: Richard Stanley kindly pointed out that the formula for f_{m}(t) is (essentially) given in Example 6.7.3 and Excercise 6.74 of [5].

References

[1] P. Cartier, Harmonic analysis on trees, Harmonic Analysis on Homogeneous Spaces, (Proc. Sympos. Pure Math., Vol. XXVI, Williams Coll., Williamstown, Mass.) , 419–424, Amer. Math. Soc., Providence, R.I., 1973.

[2] H. Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336–354.

[3] B. D. McKay, Spanning trees in regular graphs, Europ. J. Combinatorics 4 (1983), 149–160.

[4] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://www.research.att.

   com/~njas/sequences.

[5] Richard P. Stanley, “Enumerative Combinatorics”, volume 2, Cambridge University Press, 1999.

[6] D. Stevanović, N. M. M. de Abreu, M. A. A. de Freitas, and R. Del-Vecchio, Walks and regular integral graphs, Linear Algebra Appl. 423 (2007), 119–135.

Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.