Counting Isomorphism Classes of $m$-ary Trees

Description of the problem

Two days ago, I did a count of ternary trees. But, there was a mistake in the count. I corrected the argument and repost the page. But the new version is very general. Now we can handle all $m$-ary trees:

Implementation

Let me recall the code we wrote yesterday. First, the code that deals with partitions of integers:


(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))

PARTITIONS-WITH-ZEROS
PARTITIONS

Next, the coed for counting with multisets:

(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
HANDLE

As I said earlier, the function can handle other arities as well. But for this, we need to modify the counting function with the correct base cases.

(let ((table (make-hash-table)))
  (defun quaternary (n) 
    (cond
      ((= n 1) 1)
      ((< n 4) 0)
      (t (or (gethash n table)
             (setf (gethash n table)
                   (reduce #'+
                           (mapcar (lambda (xs) (handle (mapcar #'quaternary xs)))
                                   (partitions n 4)))))))))

(loop for i from 1 to 60 by 3 collect (quaternary i))

QUATERNARY
(1 1 1 2 4 9 19 45 106 260 643 1624 4138 10683 27790 72917 192548 511624
 1366424 3666930)

And this is A036718 on OEIS. Then the general case can be handled by

(let ((table (make-hash-table :test #'equal)))
  (defun m-ary (n m) 
    (cond
      ((= n 1) 1)
      ((< n m) 0)
      (t (or (gethash (list n m) table)
             (setf (gethash (list n m) table)
                   (reduce #'+
                           (mapcar (lambda (xs) (handle (mapcar (lambda (x) (m-ary x m)) xs)))
                                   (partitions n m)))))))))

(loop for i from 1 to 58 by (1- 4) collect (m-ary i 4))
(loop for i from 1 to 77 by (1- 5) collect (m-ary i 5))
(loop for i from 1 to 99 by (1- 6) collect (m-ary i 6))
(loop for i from 1 to 110 by (1- 7) collect (m-ary i 7))

M-ARY
(1 1 1 2 4 9 19 45 106 260 643 1624 4138 10683 27790 72917 192548 511624
 1366424 3666930)
(1 1 1 2 4 9 20 47 112 277 693 1766 4547 11852 31146 82534 220149 590834
 1593951 4320723)
(1 1 1 2 4 9 20 48 114 283 710 1816 4690 12267 32338 85978 230080 619521
 1676808 4560286)
(1 1 1 2 4 9 20 48 115 285 716 1833 4740 12410 32754 87176 233547 629540
 1705809)

The first is A036718 as before. The other three are A036721, A036722, and A182378. The number of isomorphism classes of $m$-ary trees can be found in A299038.