The Number of Walks on a Regular Cayley Tree

The Number of Walks on a Regular Cayley Tree

By Eric Rowland and Doron Zeilberger
.pdf LaTeX source
First Written: Mar. 10, 2009. Second Version: Mar. 12, 2009. This version: Mar. 17, 2009.
Problem:"Brothers and sisters have I none, but that man's father is my father's son. How are he and I related?"
Solution:
father(x)=son(father(myself)) implies, thanks to the uniquenss assumption, that
father(x)=myself,
that means that x belongs to the set father^-1(myself), and hence x is one of my (possibly many, possibly none) sons.
Even if you have twelve brothers, you can modify that old chestnut by replacing "son" by "eldest son", or "second-eldest son", ..., "12th-eldest son". Assuming that Adam had m children, but Abel, Cain, and Seth, and everyone else for ever after, had m-1 children, there are lots and lots of ways of describing a relation, including the self-relation. For example Adam himself equals himself, but also the "father of the father of the eldest son of the second-eldest son of Adam", and the "father of the third-eldest son of the father of the second-eldest son of Adam", etc. How many ways? The present paper answers this extremely important question once and for all.
Added March 12, 2009: After posting the first version on the archive, we were told by Brendan McKay that the results of our paper go back at least to his 1983 paper, and Franz Lehner informed us that, in some form, it goes back to Harry Kesten's 1959 paper. But we believe that our method of proof is different, and may be useful in other situations.
Added March 16, 2009: Richard Stanley kindly pointed our attention to Example 6.7.3 and Exercise 6.74 of "Enumerative Combinatorics", v.2. This problem is equivalent to the case m=2k of our result.
Added March 17, 2009: Read Franz Lehner's ineresting message

Doron Zeilberger's List of Papers
Doron Zeilberger's Home Page