R/howmanytrees.R

   1 ## howmanytrees.R (2004-12-23)
   2
   3 ##   Calculate Numbers of Phylogenetic Trees
   4
   5 ## Copyright 2004 Emmanuel Paradis
   6
   7 ## This file is part of the R-package `ape'.
   8 ## See the file ../COPYING for licensing issues.
   9
  10 howmanytrees <- function(n, rooted = TRUE, binary = TRUE,
  11                          labeled = TRUE, detail = FALSE)
  12 {
  13     if (!labeled && !(rooted & binary))
  14       stop("can compute number of unlabeled trees only for rooted binary cases.")
  15     if (n < 3) N <- 1 else {
  16         if (labeled) {
  17             if (!rooted) n <- n - 1
  18             if (binary) N <- prod(seq(1, (2*n - 3), by = 2))
  19             else {
  20                 N <- matrix(0, n, n - 1)
  21                 N[1:n, 1] <- 1
  22                 for (i in 3:n)
  23                   for (j in 2:(i - 1))
  24                     N[i, j] <- (i + j - 2)*N[i - 1, j - 1] + j*N[i - 1, j]
  25                 if (detail) {
  26                     rownames(N) <- 1:n
  27                     colnames(N) <- 1:(n - 1)
  28                 } else N <- sum(N[n, ])
  29             }
  30         } else {
  31             N <- numeric(n)
  32             N[1] <- 1
  33             for (i in 2:n)
  34               if (i %% 2) N[i] <- sum(N[1:((i - 1)/2)]*N[(i - 1):((i + 1)/2)]) else {
  35                   x <- N[1:(i/2)]
  36                   y <- N[(i - 1):(i/2)]
  37                   y[length(y)] <- (y[length(y)] + 1)/2
  38                   N[i] <- sum(x*y)
  39               }
  40             if (detail) names(N) <- 1:n else N <- N[n]
  41         }
  42     }
  43     N
  44 }