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?

Solution 1:

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)!!\;. $$