OFFSET
1,2
COMMENTS
a(n) is the size of the population generated by n unrelated ancestors if two individuals produce one descendant together if and only if they are not related.
LINKS
Felix A. Pahl, Table of n, a(n) for n = 1..400
Mathematics Stack Exchange, The n immortals problem
V. Kotesovec, Interesting asymptotic formulas for binomial sums, Jun 09 2013
FORMULA
a(n) = Sum_{k=1..n} binomial(n,k)*(2k-3)!!.
a(n) ~ (2n-3)!!*sqrt(e) ~ (2n)!/(n!*2^n*(2n-1))*sqrt(e) ~ n^(n-1)*2^(n-1/2)*exp(1/2-n). - Vaclav Kotesovec, Dec 17 2012
EXAMPLE
For n=3, each of the three pairs of ancestors produces one descendant, and each of these descendants produces one more descendant with the respective remaining ancestor; three ancestors, three first-order descendants and three second-order descendants makes a population of a(3)=9.
MATHEMATICA
Table[Sum[Binomial[n, k]*(2*k-3)!!, {k, 1, n}], {n, 1, 20}] (* Vaclav Kotesovec, Dec 17 2012 *)
PROG
(Java)
import java.math.BigInteger;
public class A220452 {
public static void main (String [] args) {
int max = Integer.parseInt (args [0]);
BigInteger [] doubleFactorials = new BigInteger [max + 1];
BigInteger [] [] binomialCoefficients = new BigInteger [max + 1] [max + 1];
doubleFactorials [0] = BigInteger.ONE;
for (int n = 1; n <= max; n++) {
binomialCoefficients [n] [0] = BigInteger.ONE;
BigInteger sum = BigInteger.ZERO;
for (int k = 1; k <= n; k++) {
binomialCoefficients [n] [k] = k == n ? BigInteger.ONE : binomialCoefficients [n - 1] [k - 1].add (binomialCoefficients [n - 1] [k]);
sum = sum.add (binomialCoefficients [n] [k].multiply (doubleFactorials [k - 1]));
}
System.out.println (n + " " + sum);
doubleFactorials [n] = doubleFactorials [n - 1].multiply (BigInteger.valueOf (2 * n - 1));
}
}
}
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Felix A. Pahl, Dec 15 2012
STATUS
approved