Trees with Labeled Nodes that form Permutation of Positive Integers

[franktaw at netscape.net]

From: pauldhanna at juno.com

>    Could someone compute the initial terms of the following.
>I do not believe that it is in the OEIS (?).
>
>Number of labelled nodes in generation n of a rooted tree
>where a node with label k has k child nodes such that
>the label of each child node is the least unused label in
>the path from the root to that child node,
excluding those used by earlier children of the same parent,
>and where root is labeled '1'.
>
>Thus every distinct path in the tree eventually forms
>a permutation of the positive integers.
>
>...

This isn't really true.  There are many paths in this tree
that do not form a permutation of the positive integers.
You get such a permutation iff, infinitely often, you choose
the first child from the current node.

It is true, of course, that any finite initial path can be
extended to a path that is a permuatation of the positive
integers.

It is an interesting problem to construct an interesting tree
where every path from the root is a permutation of the
positive integers.  I think the following construction works:
start with node 1, which arbitrarily has node 2 as a child
(by the construction that follows, 1 would have no children).
For each node with label m, add BigOmega(m) children, where
BigOmega(m) is the number of prime factors of m with
repetition; label these chilidren with the first positive integers
not occurring in the path from the root to the current node.

The tree starts:

......1
......|
......2
......|
......3
......|
......4
...../.\
....5...6
.../....|\
..6.....5.7
./.\....|.|
7...8...7.5
|../|\..|.|
8.7.9.A.8.8

Any time you hit a prime, there is only one child in the next
generation.  If you keep choosing non-prime children, the
primes start accumulating in the list of positive integers not
occurring in the path, until eventually all children of a node will
be prime.

One could of course use Omega(m), the number of distinct
prime divisors, instead of BigOmega(m).  I think tau(m)-1 would
also work.  A001511(m) (the power of 2 dividing 2m) works, too
- in this case, the single children are under the odd nodes.
________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.