|
%I #10 Sep 07 2013 14:28:42
%S 1,5,11,19,29,41,55,71,77,85,95,119,121,149,167,187,197,221,239,263,
%T 273,293,315,339,365,389,411,431,453,477,503,531,561,581,611,639,665,
%U 693,723,751,781,809,839,871,901,933,963
%N The most common total path length for each size of (fully leafed) binary tree, with left and right distinguished.
%D Robert P. Dobrow, James Allen Fill, Total Path Length for Random Recursive Trees, Combinatorics, Probability and Computing, Volume 8, Issue 04, July 1999, pp 317-333.
%o (Common Lisp)
%o (defparameter all '(((1 1)))) ;the first element of each pair represents a total path length, the second element represents how many trees of that size have the same path length
%o (defun combine-duplicates (list1) ;takes a list of pairs and merges any pairs with the same first number, by adding their second number together
%o (let*
%o ((list (sort list1 #'(lambda (a b) (< (first a) (first b)))))
%o (place list))
%o (loop
%o (when (null (cdr place)) (return))
%o (if (= (first (car place)) (first (cadr place)))
%o (progn
%o (incf (second (car place)) (second (cadr place)))
%o (setf (cdr place) (cddr place)))
%o (setf place (cdr place))))
%o list))
%o (defun combine (num a b) ; combines 2 trees's path lengths into a larger tree, num is the number of element contained in both trees and the new root
%o (list (+ num (first a) (first b))
%o (* (second a) (second b)))) ;the numbers of possible trees are multiplied because each possible way of choosing one possibility from each, should be counted
%o (defun map-all (func list1 list2) ;this takes a function and two lists and feeds the function one element from each, in all combinations
%o (mapcan #'(lambda (b)
%o (mapcar #'(lambda (a) (funcall func a b)) list1))
%o list2))
%o (defun path-lengths (x) ;computes the list of possible total path lengths for a tree with x nodes
%o (when (<= (length all) x) ;if we have not already computed the solution for this size, we do so
%o (let ((num (1+ (* 2 x)))) ;because we are working with fully leafed trees, we calculate the number of elements when we are given just the number of nodes
%o (nconc all (list ;we stick the results for this size onto the end of our list of all results
%o (combine-duplicates
%o (mapcan ;we try all ways of splitting x-1 indistinguishable nodes into two groups
%o #'(lambda (n) (map-all
%o #'(lambda (a b) (combine num a b)) ;we get all possible trees by recursing to all possible trees for each branch
%o (path-lengths n) ;the path lengths of all possible trees with some of our nodes
%o (path-lengths (- x n 1)))) ;the path lengths of all possible trees with the rest of our nodes
%o (loop for i below x collect i))))))) ; list of 0 to x-1
%o (elt all x)) ;return the solutions for this size
%o (progn (path-lengths 40) nil) ;fills up the 'all' with results, change 40 to however many elements of this sequence you want (progn ... nil is so that it doesn't cover the screen with numbers)
%o (defun find-max (seq) ; finds the pair with the greatest number of trees
%o (let ((max '(0 0)))
%o (loop for i in seq do
%o (when (> (second i) (second max))
%o (setf max i)))
%o max))
%o (loop for a in all collect (first (find-max a))) ;gives you the path length with the greatest number of trees, for each size
%Y Cf. A028387 (maximum total path length for each size of tree).
%K nonn
%O 1,2
%A _Anders Horn_, Aug 25 2012
| 