# A277795 # Number of trees with n unlabeled nodes such that all nodes with degree >2 lie on a single path with length = the tree's diameter. # program by Andrey Zabolotskiy ''' The algorithm: 1. Take all possible max path lengths from 3 to n (lpath). 2. Find all possible ways to distribute the rest of nodes (n-lpath of them) over the nodes on the path except the end nodes (lpath-2 of them). 3. For a node on the path and a number of nodes attached to it, split those nodes into non-branched chains (side branches) with the lengths bound by the condition that the max path length of the tree should not be increased by those side branches. Thus every tree is represented by a sequence of unordered sets of lengths of side branches: side branches growing from the 2nd node on the max path (all of length 1), side branches growing from the 3rd node on the path (all of length 1 or 2), ..., side branches growing from the (lpath-1)th node on the path (all of length 1). 4. Among the trees generated, some are related via mirror symmetry. Eliminate the lexicographically smaller members of such pairs. 5. Count the trees. ''' d = {(0, 0): [[]]} def partitions(n, mm): 'unordered (sorted) partitions of n to nonzero parts <= m' m = min(mm, n) if (n, m) in d: return d[(n, m)] a = [] for i in range(1, m+1): a += [[i] + x for x in partitions(n-i, min(m, i))] d[(n, m)] = a return a od = {} def opartitions(n, k): 'ordered partitions of n to k parts' if k <= 0: raise ValueError if k == 1: return [[n]] if n == 0: return [[0]*k] if (n, k) in od: return od[(n, k)] a = [] for i in range(n+1): a += [[i]+x for x in opartitions(n-i, k-1)] od[(n, k)] = a return a def f(l, sizes): if not l: return [[]] return [[x]+y for x in partitions(l[0], sizes[0]) for y in f(l[1:], sizes[1:])] a = [1, 1, 1] for n in range(3, 24): trees = [] for lpath in range(3, n+1): op = opartitions(n-lpath, lpath-2) # resourses for side branches sizes = list(range(1, (lpath+1)//2)) + list(range((lpath-2)//2, 0, -1)) for o in op: trees += f(o, sizes) trees = [x for x in trees if x >= list(reversed(x))] # print(trees) a.append(len(trees)) print(n, a[n])