# The $n$ Immortals problem.

I saw this riddle posted on reddit a long time ago, called the "Seven Immortals."

In the beginning, the world is inhabited by seven immortals, ageless and sexless, who begin to multiply and populate the land. Any immortal can mate with any other to produce exactly one child, and the same is true of their descendants, with the caveat that no immortal could mate with his own ancestors or relatives. No couple can mate more than once, and they continue to intermingle until no more matings are possible. How many immortals are left in the end?

The solution is

$19873$, which I lazily confirmed by writing a Mathematica program.

Having a mathematical mind, I of course immediately wondered about the "$n$ Immortals" problem. Surely a combinatorial solution with binomial coefficients should be attainable by extending the "genes" approach discussed in the comments. But is this the only way? It feels like a graph theory problem to me.

My second question is, is there any significance to this problem? Does the solution arise in any other mathematical contexts?

-
As a graph, I think we could state this as "the maximum number of nodes in a directed acyclic graph with $n$ sources where each non-source has in-degree $2$ and there is at most one path between any two vertices". Not sure what to do with that though! –  usul Dec 14 '12 at 7:33
Can you confirm using your program whether the sequence matches oeis.org/A151150 ? –  Qiaochu Yuan Dec 14 '12 at 7:36
You could also ask an inverse question: Suppose we are left with $m$ immortals who never have children. What's the largest number of immortals there could be? Taking these as sources, we want to find the largest directed acyclic graph where each non-sink has out-degree 2 and restricting to any one vertex's transitive closure yields a binary tree with that vertex at the root. Also the number of sinks in this graph tells us how many immortals there were to start with. –  usul Dec 14 '12 at 7:37
@Qiaochu: It doesn’t, according to the computations posted at the Reddit link. –  Brian M. Scott Dec 14 '12 at 7:59
Got it. Graph theory does not seem like the right language; I would talk about trees. You can identify an immortal with its tree of ancestors, and the question is to count certain such trees, which have leaves labeled by the original population of immortals, and the condition on mating is a condition on upward-closed subtrees. –  Qiaochu Yuan Dec 14 '12 at 8:23

Given $n$ initial immortals, for any group of $k$ of them there is exactly one descendant with exactly these ancestors for every unordered full binary tree with $k$ labeled leaves, of which there are $(2k-3)!!$ (where $(-1)!!=1$). Thus the total number of immortals is
$$\sum_{k=1}^n\binom nk(2k-3)!!\;.$$