Ross Drewe (rd(AT)labyrinth.net.au), Oct 06 2008 Notes on a generalization of F(n) F(n) is a table of sequences representing the number of valid nodes in level n of a labelled binary tree, when the labelling rule forbids 1 of the 2^L states given by the last L digits of the parent label. The definition of a rule can be formalised as follows: for a k-ary tree, state length L, there are k^L possible states which can be tabulated as an array s of size [k^L, k]. For each state (ie, each row in s), there are k possible outcomes (= symbols which can be appended to the parent label). A Boolean "permissions vector" of length k is needed to specify which output symbols are allowed, and which forbidden, for any given state. For example, if k = 3 (symbol set is 1,2,3) and L = 2, then s = [1 1 1 1 1 2 1 1 3 .....(1) 2 1 1 ... 3 3 3] and for any given row of s, the permissions vector z has 3 elements. For example, if: chosen state = [2 1 3], permission vector = [0 1 1], then: output [2 1 3 1] is forbidden output [2 1 3 2] is allowed output [2 1 3 3] is allowed. There are 2^k possible permission vectors for any given state, as follows: z = [0 0 0 0 0 1 0 1 0 .....(2) ... 1 1 1] The construction rule for any given tree consists of the fixed array s in conjunction with an array z, where each row of z can be selected independently from the ensemble of possibilities in (2). Hence there are k^L * 2^k possible construction rules (= state-vector combinations [s, z]). Every combination of distinct [k, L, s, z] generates a sequence A(k,L,s,z) of a(k,L,s,z) values, as discussed in entry A888888. The structure of s and z is unambiguous if they are generated in ascending numeric order, as shown in (1) and (2) above. This entry represents the set of all such sequences { A(k,L,s,z) }. Furthermore, s and z can be unambiguously created from k & L, and are exhaustive enumerations, so it is sufficient to label the whole set (for finite ranges of k and L) as T = { A(k,L) }, even though this is not true for an individual sequence A(k,L,s,z). Taking the antidiagonals of table T gives the present entry F(n). This table is interesting for 3 reasons: ---------------------------------------- a) It is a "monster entry" in terms of the number of sequences it incorporates, rather than having very large values within sequences. It is also remarkable for its economy of parameterisation, since there are only 2 independent parameters producing the large number of output sequences. To show the rapid growth of the number of sequences for small finite parameter ranges: take k = 2 to 4 (binary to quaternary trees only), L = 1 to 5 (state lengths <= 5), This produces produces 15 groups of trees: L 1 2 3 4 5 |---------------------------------------------------------------| | [s] = 2^1 | [s] = 2^2 | [s] = 2^3 | [s] = 2^4 | [s] = 2^5 | 2 | [z] = 2^2 | [z] = 2^2 | [z] = 2^2 | [z] = 2^2 | [z] = 2^2 | | [r] = 8 | [r] = 16 | [r] = 32 | [r] = 64 | [r] = 128 | | | | | | | k | [s] = 3^1 | [s] = 3^2 | [s] = 3^3 | [s] = 3^4 | [s] = 3^5 | 3 | [z] = 2^3 | [z] = 2^3 | [z] = 2^3 | [z] = 2^3 | [z] = 2^3 | | [r] = 24 | [r] = 72 | [r] = 216 | [r] = 648 | [r] = 1944 | | | | | | | | [s] = 4^1 | [s] = 4^2 | [s] = 4^3 | [s] = 4^4 | [s] = 4^5 | 4 | [z] = 2^4 | [z] = 2^4 | [z] = 2^4 | [z] = 2^4 | [z] = 2^4 | | [r] = 64 | [r] = 256 | [r] = 1024 | [r] = 4096 | [r] = 16384 | |---------------------------------------------------------------| The output table T = { A(k,L,s,z) } therefore has a total of about 24000+ rows. b) The table includes many well-known sequences, which is not surprising when the table has so many rows (= sequences). Eg: for the parameter ranges above (k<=4, L <=5), T includes: -- the natural numbers -- the even numbers -- power sequences 2^n, 3^n, and 4^n -- n-anacci sequences up to hexanacci -- sums of the first n n-anacci numbers -- higher order Lame sequences -- Padovan sequences etc. c) it is an interesting unification of a diverse set of sequences.