Source code for pybs.unordered_tree.functions

from operator import __add__ as _add
from itertools import imap as _imap

from pybs.utils import memoized2 as memoized


@memoized
[docs]def number_of_trees_of_order(n): """Returns the number of unordered rooted trees with exactly *n* vertices. Uses a formula from Sloane's OEIS sequence no. ``A000081``. """ if n < 2: return n result = 0 for k in range(1, n): result += k * number_of_trees_of_order(k) * _s(n-1, k) return result / (n - 1)
@memoized def _s(n, k): """Used in number_of_trees_of_order""" result = 0 for j in range(1, n/k + 1): result += number_of_trees_of_order(n+1-j*k) return result # Joe Riel (joer(AT)san.rr.com), Jun 23 2008
[docs]def number_of_trees_up_to_order(n): '''Number of _trees up to, not including order `n`. Based on :class:`number_of_trees_of_order`. ''' return reduce(_add, _imap(number_of_trees_of_order, xrange(n)), 0)
[docs]def number_of_tree_pairs_of_total_order(n): """Needed for conjugate symplectic check. Known as :math:`m_n`. \ Taken from Hairer et al. \ On Conjugate symplecticity of B-series integrators """ # TODO: Implement general formula instead of table lookup. table = [0, 0, 1, 1, 3, 6, 16, 37, 96, 239, 622, 1607, 4235] return table[n]