login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A220452 Number of unordered full binary trees with labels from a set of n labels. 2
1, 3, 9, 37, 225, 1881, 19873, 251889, 3712257, 62286625, 1171487361, 24402416193, 557542291969, 13861636770177, 372514645389825, 10759590258589441, 332386419622387713, 10935312198369141249, 381705328034883127297, 14089260601787531469825, 548302210950105933701121 (list; graph; refs; listen; history; text; internal format)
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

Stack Exchange, The n immortals problem

V. Kotesovec, Interesting asymptotic formulas for binomial sums, Jun 09 2013

FORMULA

a(n) = sum(binom(n,k)*(2k-3)!!, k=1..n)

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

Cf. A001147.

Sequence in context: A155159 A222518 A107886 * A130407 A137031 A047148

Adjacent sequences:  A220449 A220450 A220451 * A220453 A220454 A220455

KEYWORD

nonn,easy

AUTHOR

Felix A. Pahl, Dec 15 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 17 20:01 EDT 2014. Contains 240655 sequences.