Today, I am going to count the number of planted ternary trees on \(n\) leaves for \(n\geq 0\). A planted ternary tree is a rooted tree in which every internal vertex has degree 4. The leaves and the root have degree 1. Below, when we talk about the size of a tree, we will specifically mean the number of leaves.
In a ternary tree, every internal vertex has degree 4. So, if we split a ternary tree into subtrees at the vertex adjacent to the root, we get 3 ternary trees. Let us write \(T(p,q,r)\) for the number of ternary trees whose splitting as three subtrees of sizes \(p\), \(q\), and \(r\). Thus one may think that \[ T(p,q,r) = T(p)T(q)T(r) \] with base cases \(T(1)=1\) and \(T(2n)=0\) for every \(n\). Thus we can assume that \(p\), \(q\), and \(r\) are all odd.
There is a big problem with this count: assume we have a splitting of the form \(ABC\). In the best case, all \(A\), \(B\), and \(C\) have different number of leaves, hence no overcounting. However, if any two consecutive subtrees have the same size, then both decompositions \(ABC\) an \(BAC\) are counted as separate trees since the product \(T(p)T(q)\) counts ordered pairs of trees \(AB\) with sizes \(p\) and \(q\), respectively. We need to count unordered triples of subtrees. Thus we need to be careful about 3 subcases: (i) \(p=q<r\), (ii) \(p<q=r\), and (iii) \(p=q=r\). In the first two cases, we are taking multi-subsets of size 2 from the collection of all trees of the same size. In the last case, we are taking multi-subsets of size 3 from the collection of all trees of the same size.
\[ T(p,q,r) = \begin{cases} T(p)T(q)T(r) & \text{ if $p$, $q$, and $r$ are pairwise distinct,}\\ \frac{1}{2}(T(p)+1)T(p)T(r) & \text{ if } p=q<r \\ \frac{1}{2}T(p)(T(q)+1)T(q) & \text{ if } p<q=r \\ \frac{1}{6}(T(p)+2)(T(p)+1)T(p) & \text{ if } p=q=r \end{cases}\]
For my implementation, I am going to need a function that returns all partitions of an integers. I wrote that function in the past.
(defun partitions-with-zeros (n k &optional (a 0) acc)
(cond
((< n 0) nil)
((> k n) (partitions-with-zeros n (1- k) a (cons a acc)))
((= k 1) (list (reverse (cons (+ n a) acc))))
((= n 0) (list (append (reverse acc) (loop repeat k collect a))))
(t (loop for i from (floor n k) downto 0
append
(partitions-with-zeros (- n (* k i)) (1- k) (+ a i) (cons (+ a i) acc))))))
(defun partitions (n k)
(partitions-with-zeros (- n k) k 1))
(defun odd-partitions (n k)
(let ((alpha (floor (+ n k) 2)))
(mapcar (lambda (xs) (mapcar (lambda (x) (1+ (* 2 x))) xs))
(partitions-with-zeros (- n alpha) k))))PARTITIONS-WITH-ZEROS
PARTITIONS
ODD-PARTITIONSLet me test the code:
(partitions-with-zeros 11 3)
(partitions 11 3)
(odd-partitions 11 3)((3 4 4) (3 3 5) (2 4 5) (2 3 6) (2 2 7) (1 5 5) (1 4 6) (1 3 7) (1 2 8)
(1 1 9) (0 5 6) (0 4 7) (0 3 8) (0 2 9) (0 1 10) (0 0 11))
((3 4 4) (3 3 5) (2 4 5) (2 3 6) (2 2 7) (1 5 5) (1 4 6) (1 3 7) (1 2 8)
(1 1 9))
((3 3 5) (1 5 5) (1 3 7) (1 1 9))Next, I need a function that deals with counting multi-subsets. This is far more general than I need.
(defun binom (n k)
(cond
((or (< n 0) (< k 0) (< n k)) 0)
((= n k) 1)
((zerop k) 1)
((< (- n k) k) (binom n (- n k)))
(t (* (/ n k) (binom (1- n) (1- k))))))
(defun handle (xs &optional (k 0) (carry 1))
(cond ((null xs) carry)
((equal (car xs) (cadr xs))
(handle (cdr xs) (incf k) carry))
(t (handle (cdr xs)
0
(* carry (if (zerop k)
(car xs)
(binom (+ (car xs) k) (1+ k))))))))BINOM
HANDLELet us test:
(handle '(1 1 1))
(handle '(2 2 2 5))
(handle '(5 5 5))
(handle '(3 3 3 3 3))1
20
35
21Now, my implementation with memoization:
(let ((table (make-hash-table)))
(defun ternary (n)
(cond
((= n 1) 1)
((= n 2) 0)
(t (or (gethash n table)
(setf (gethash n table)
(reduce #'+
(mapcar (lambda (xs) (handle (mapcar #'ternary xs)))
(odd-partitions n 3)))))))))TERNARYI’ll check only the odd numbers since \(T(n)=0\) when \(n\) is even.
(loop for i from 1 to 51 by 2 collect (ternary i))(1 1 1 2 4 8 17 39 89 211 507 1238 3057 7639 19241 48865 124906 321198 830219
2156010 5622109 14715813 38649152 101821927 269010485 712566567)