combinatorial-0.0: Count, enumerate, rank and unrank combinatorial objects

Combinatorics.TreeDepth

Synopsis

# Documentation

nodeDepth :: [[Integer]] Source #

nodeDepth !! n !! k is the absolute frequency of nodes with depth k in trees with n nodes.

treeDepth !! n !! m !! k is the absolute frequency of nodes with depth k in trees with n nodes and depth m. This can't work - the function carries not enough information for recursive definition. treeDepth :: [[[Integer]]] treeDepth = iterate (ls -> zipWith treeDepthIt ([[]]++ls) (ls++[[0]])) [[1]]

treeDepthIt :: [Integer] -> [Integer] -> [Integer] treeDepthIt nm0 nm1 = foldl1 add [scale (if null nm0 then 0 else last nm0) (nm0 ++ [1]), scale (sum (init nm1)) nm1, 0 : init nm1]

Trees are abstracted to lists of integers, where each integer denotes the number of nodes in the corresponding depth of the tree. The number associated with each tree is the frequency of this kind of tree on random tree generation.

nodeDegree !! n !! k is the number of nodes with outdegree k in a n-node tree.

expected value of node degree