Let T be an innite regular tree and n a positive integer. Fix two vertices x and y in T . By a walk or a path between x and y we mean any nite sequence of edges that connect x and y in which backtrackings are allowed. There are many formulas in the literature which give the number of walks of length n between x and y, such as recurrence formulas, generating functions, Green functions, and others. Here we consider walks of length n between x and y which at a certain time follow a number of predetermined steps | Restricted walks in regular trees Laura Ciobanu Department of Mathematics University of Auckland Private Bag 92019 Auckland New Zealand ciobanu@ Sasa Radomirovic y Centre de Recerca Matematica 08193 Bellaterra Spain sasa@ Submitted Jun 7 2006 Accepted Oct 10 2006 Published Oct 27 2006 Mathematics Subject Classification 05C25 20E05 Abstract Let T be the Cayley graph of a finitely generated free group F. Given two vertices in T consider all the walks of a given length between these vertices that at a certain time must follow a number of predetermined steps. We give formulas for the number of such walks by expressing the problem in terms of equations in F and solving the corresponding equations. 1 Introduction Let T be an infinite regular tree and n a positive integer. Fix two vertices x and y in T. By a walk or a path between x and y we mean any finite sequence of edges that connect x and y in which backtrackings are allowed. There are many formulas in the literature which give the number of walks of length n between x and y such as recurrence formulas generating functions Green functions and others. Here we consider walks of length n between x and y which at a certain time follow a number of predetermined steps. This work was motivated by the following question of Tatiana Smirnova-Nagnibeda in relation to finding the spectral radius of a given surface group. Let F2 be the free group on generators a and b K a field of characteristic 0 T a 1 a b 1 b an element in the group algebra K F2 and c a b aba-1 b-1. What is the projection for any Partially supported by the Marie Curie Intra-European Fellowship number 515027 and a University of Auckland Postdoctoral Fellowship. This work was carried out during the tenure of an ERCIM Fellowship. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R93 1 m and for any m-tuple of integers k1 . krn of Tck1 onto the group algebra of the subgroup generated by c Alternately this can be formulated as
