login
Number of (unordered) plane trees with n leaves, such that for every node the number of "children of children" has no common divisor > 1.
0

%I #61 Jun 14 2022 01:41:00

%S 1,1,2,4,10,23,60,153,405,1076,2909,7907,21693,59834,166004,462612,

%T 1294612,3635809,10244017

%N Number of (unordered) plane trees with n leaves, such that for every node the number of "children of children" has no common divisor > 1.

%C This sequence can be generated by the following algorithm: Starting with the array [1], one can use the following replacement rule: Let k be an arbitrary natural number. For any element x of the array, we replace x with k copies of k*x. The leaves then represent the numbers in the array, with the structure being governed by the prime factorization of the entries. The leaf "height" is then described by the number of prime factors in the factorization of that number. a(n) is the number of distinct arrays (up to permutations) of a fixed length n that can be generated this way.

%C Another way of describing this problem is sketched in the Math.SE post in the links: Given n arithmetic progressions with terms a_i, how many ways (up to identical terms a_i) are there to disjointly cover the residue classes modulo the lcm of all a_i?

%C This sequence arose in the "inverse covering set" problem. Normally when considering covering sets (see the corresponding Wikipedia article below), we fix a base b and want to find a set of primes P and factor k such that k*b^m+1 is divisible by a prime in P for any natural number m (so it is a sequence that is non-obviously always composite). The "inverse" problem is: Given P and a set of multiplicative orders of b^(...) modulo the primes in P, can we find a b fitting these criteria? The number of "allowed" sets (i.e., non-overlapping covered residues) of multiplicative orders for n primes is then represented by a(n). They are a special case of representing 1 as a sum of Egyptian fractions where one can always group appropriate terms and gain a smaller set with the same property.

%C a(n-1) <= a(n) <= A000699(n).

%H MathStackExchange, <a href="https://math.stackexchange.com/questions/4469815/egyptian-unit-decomposition-coverings-of-mathbbz-p-by-arithmetic-progress">Egyptian unit decomposition + coverings of Zp by arithmetic progressions</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Covering_set">Covering set</a>

%e The number of possible "splittings" can be found by the algorithmic approach outlined above.

%e For n = 3:

%e [1] -> [2,2] -> [2,4,4]

%e [1] -> [3,3,3]

%e so a(3) = 2.

%e For n = 4:

%e [1] -> [2,2] -> [2,4,4] -> [2,4,8,8] or [4,4,4,4]

%e [1] -> [2,2] -> [2,6,6,6]

%e [1] -> [3,3,3] -> [3,3,6,6]

%e so a(4) = 4.

%o (Julia)

%o function validCoverings(n)

%o coverings = [[1]]

%o for m in 2:n

%o len = length(coverings)

%o for i in 1:len

%o replacelen = m-length(coverings[i])+1

%o for j in 1:length(coverings[i])

%o val = coverings[i][j]

%o newCover = copy(coverings[i])

%o deleteat!(newCover, j)

%o for k in 1:replacelen

%o insert!(newCover, j, val*replacelen)

%o end

%o newCover = sort(newCover)

%o if(!(newCover in coverings))

%o append!(coverings, [newCover])

%o end

%o end

%o end

%o end

%o length(filter((x) -> length(x)==n, coverings))

%o end

%Y Cf. A000699.

%K nonn,more

%O 1,3

%A _Toni Wunderlich_, Jun 12 2022

%E a(15)-a(19) added by Richard Knäbchen (Mathematics undergraduate at the "Technische Universität Chemnitz")