If I have n dogs [a, b, c, ...], and I want to breed them in every possible combination (every possible binary tree made of nodes [a, b, c, ...]), how many different end-result puppies are possible? (edit: gender doesn't matter, any dog can breed with any dog, so, unrealistic, but more general.)
I can't quite wrap my head around it, but I started thinking there are n! possible puppies with exactly the same parents, but bred in a different order.
I get that by taking every permutation of n dogs, and each couplet's offspring breeds with the next couplet's offspring, and so on. But that doesn't quite answer it since, given the same starting permutation, I can have many binary trees (ex some deep, some wide). I'm thinking that there are log2 n different binary trees for one given permutation. But that doesn't always give whole numbers...
So, the best I've got is n! * log2(n), but that can't be right.
Thoughts?
(PS, not homework, I'm a nerd, and my wife and I are buying a puppy :) )
edit2: a note on genetics, obviously, the exact same tree will yield different puppies every single time because of how genes/meiosis/crossover works. I'm really interested in the general case. How many different trees are there, with each parent represented once.
edit3: Is the correct answer the Catalan numbers? (IE every possible binary tree given a set of count=n) (2n)!/(n!(n+1)!) oeis.org/A000108 and https://stackoverflow.com/a/16004841/3884713?
It seems that you are concerned about fractions of the parentage that each of the $n$ dogs contribute to a given puppy. A $k^{\text{th}}$ generation puppy will have $2^k$ ancestors, who may be repeated. You are looking at weak compositions of $2^k$ into $n$ parts-you express $2^k=A+B+C+\dots N$ where the capital letters represent how many of that type of parent there are. There are ${2^k+n-1 \choose n-1}$ of these.
A subtlety is that you probably don't want the same dog breeding with itself in the first round. After the first you don't worry, because there could be two ab puppies in the first round to breed together. This will impose the restriction that no part can be larger than $2^{k-1}$ but all others will be possible. We can note that only one part can be larger than that, so compute the number of strings that have too many a's and subtract $n$ times that. The number of compositions that have $i$ a's is just the number of weak compositions of $2^k-i$ into $n-1$ pieces, so ${2^k-i+n-2 \choose n-2}$ We have to sum this from $i=2^{k-1}+1$ to $i=2^k$, so we have $${2^k+n-1 \choose n-1}-n\sum_{i=2^{k-1}+1}^n{2^k-i+n-2 \choose n-2}$$