cp's OEIS Frontend

A220452 Number of unordered full binary trees with labels from a set of n labels.

%I A220452 #27 Aug 13 2022 20:48:59
%S A220452 1,3,9,37,225,1881,19873,251889,3712257,62286625,1171487361,
%T A220452 24402416193,557542291969,13861636770177,372514645389825,
%U A220452 10759590258589441,332386419622387713,10935312198369141249,381705328034883127297,14089260601787531469825,548302210950105933701121
%N A220452 Number of unordered full binary trees with labels from a set of n labels.
%C A220452 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.
%H A220452 Felix A. Pahl, <a href="/A220452/b220452.txt">Table of n, a(n) for n = 1..400</a>
%H A220452 Mathematics Stack Exchange, <a href="http://math.stackexchange.com/questions/258503">The n immortals problem</a>
%H A220452 V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Interesting asymptotic formulas for binomial sums</a>, Jun 09 2013
%F A220452 a(n) = Sum_{k=1..n} binomial(n,k)*(2k-3)!!.
%F A220452 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
%e A220452 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.
%t A220452 Table[Sum[Binomial[n,k]*(2*k-3)!!, {k, 1, n}], {n, 1, 20}] (* _Vaclav Kotesovec_, Dec 17 2012 *)
%o A220452 (Java)
%o A220452 import java.math.BigInteger;
%o A220452 public class A220452 {
%o A220452     public static void main (String [] args) {
%o A220452         int max = Integer.parseInt (args [0]);
%o A220452         BigInteger [] doubleFactorials = new BigInteger [max + 1];
%o A220452         BigInteger [] [] binomialCoefficients = new BigInteger [max + 1] [max + 1];
%o A220452         doubleFactorials [0] = BigInteger.ONE;
%o A220452         for (int n = 1;n <= max;n++) {
%o A220452             binomialCoefficients [n] [0] = BigInteger.ONE;
%o A220452             BigInteger sum = BigInteger.ZERO;
%o A220452             for (int k = 1;k <= n;k++) {
%o A220452                 binomialCoefficients [n] [k] = k == n ? BigInteger.ONE : binomialCoefficients [n - 1] [k - 1].add (binomialCoefficients [n - 1] [k]);
%o A220452                 sum = sum.add (binomialCoefficients [n] [k].multiply (doubleFactorials [k - 1]));
%o A220452             }
%o A220452             System.out.println (n + " " + sum);
%o A220452             doubleFactorials [n] = doubleFactorials [n - 1].multiply (BigInteger.valueOf (2 * n - 1));
%o A220452         }
%o A220452     }
%o A220452 }
%Y A220452 Cf. A001147.
%Y A220452 Partial sums of A084262.
%K A220452 nonn,easy
%O A220452 1,2
%A A220452 _Felix A. Pahl_, Dec 15 2012