By Eric Rowland and Doron Zeilberger
Problem:"Brothers and sisters have I none, but that man's father is my father's son. How are he and I related?"
Solution:
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.
.pdf
LaTeX source
First Written: Mar. 10, 2009. Second Version: Mar. 12, 2009. This version: Mar. 17, 2009.
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.
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