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

1, 1, 2, 4, 10, 23, 60, 153, 405, 1076, 2909, 7907, 21693, 59834, 166004, 462612, 1294612, 3635809, 10244017

Offset

1,3

Comments

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.

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?

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.

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

Links

Table of n, a(n) for n=1..19.

MathStackExchange, Egyptian unit decomposition + coverings of Zp by arithmetic progressions.

Wikipedia, Covering set

Example

The number of possible "splittings" can be found by the algorithmic approach outlined above.
For n = 3:
  [1] -> [2,2] -> [2,4,4]
  [1] -> [3,3,3]
  so a(3) = 2.
For n = 4:
  [1] -> [2,2] -> [2,4,4] -> [2,4,8,8] or [4,4,4,4]
  [1] -> [2,2] -> [2,6,6,6]
  [1] -> [3,3,3] -> [3,3,6,6]
  so a(4) = 4.

Prog

(Julia)
function validCoverings(n)
    coverings = [[1]]
    for m in 2:n
        len = length(coverings)
        for i in 1:len
            replacelen = m-length(coverings[i])+1
            for j in 1:length(coverings[i])
                val = coverings[i][j]
                newCover = copy(coverings[i])
                deleteat!(newCover, j)
                for k in 1:replacelen
                    insert!(newCover, j, val*replacelen)
                end
                newCover = sort(newCover)
                if(!(newCover in coverings))
                    append!(coverings, [newCover])
                end
            end
        end
    end
    length(filter((x) -> length(x)==n, coverings))
end

Crossrefs

Cf. A000699.

Sequence in context: A152173 A032171 A127713 * A151256 A205999 A208126

Adjacent sequences: A354073 A354074 A354075 * A354077 A354078 A354079

Keyword

nonn,more

Author

Toni Wunderlich, Jun 12 2022

Extensions

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

Status

approved