Riffs & Rotes & A061396

[Jon Awbrey]

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

Hello, I am new to the SeqFan list.  I would like
to report on some work that I did as a beginning
and continuing graduate student in the years from
1976 to 1986.  Since this is not currently my area
of active work, I am afraid that I will have to be
somewhat dependent on my old notes, such as I find
them.  I tried to organize this stuff in a logical
order, but that was hopeless, so I will just have
to take things up in a somewhat random order.

So let me introduce the sequence formally known as "A061396".

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

Riffs & Rotes

1, 2, 6, 20, 73, 281, 1124, 4488

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

ID:       A061396

Seq:      1,1,2,6,20,73,281,1124,4488

Name:     Number of "rooted index-functional forests" (Riffs) on n nodes.
          Number of "rooted odd trees with only exponent symmetries" (Rotes)
          on 2n+1 nodes.

Ref:      J. Awbrey, personal journal, circa 1978.
          Letter to N. J. A. Sloane, 1980-Aug-04.

Formula:  G.f.  A(x) = 1 + x + 2*x^2 + 6*x^3 + ... satisfies
          A(x) = Product_{j = 0 to infinity} (1 + x^(j+1)*A(x))^a_j.

Example:  These structures come from recursive primes factorizations
          of natural numbers, where the recursion proceeds on both
          the exponents (^k) and the indices (_k) of the primes
          invoked in the factorization:

          2 = (prime_1)^1 = (p_1)^1, briefly, p,   weight = 1 node  => a(1) = 1.
          3 = (prime_2)^1 = (p_2)^1, briefly, p_p, weight = 2 nodes and
          4 = (prime_1)^2 = (p_1)^2, briefly, p^p, weight = 2 nodes => a(2) = 2.

Keys:     nice,nonn,new,easy,more

Offset:   0

Author:   Jon Awbrey (jawbrey at oakland.edu), Jun 09 2001

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

It looks like a good place to begin is with this
summary of work, dated 1978-11-27, that I believe
I presented in Ed Palmer's graph theory seminar
at Michigan State somewhere around that time.

[ Notation Used In Transcription:
|
| p_i^e = (p_i)^e.
|
| p = p_1^1 = 2^1 = 2.
|
| p^e = p_1^e = 2^e.
|
| p_i = p_i^1.
]

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

| 1978-11-27
|
| Riffs
|
| taking as primitive the concepts of the primes factorization and
| of the n^th prime p<n>, let us see how completely we can analyze
| integers in these terms.  consider the primes factorization of
| of an integer
|
| n = (p_i<1>)^e<1> . (p_i<2>)^e<2> . ... . (p_i<w>)^e<w> , 
|
| and further analyze every non-unit exponent & index in the same manner,
| continuing until no non-unit integers are left.  the remaining 1's are
| superfluous & may be replaced by a convention that blank exponents &
| indices are understood to be 1.  the resulting expression is called
| riff(n), and the number of p's is taken as an ad hoc measure on the
| integers, |riff(n)|.
|
| eg:
|
| 1978
|
| = 2^1 . 23^1 . 43^1
|
| = p_1^1 . p_9^1 . p_14^1
|
| = p_1^1
|
| . p_(p_2^2)^1
|
| . p_(p_1^1 . p_4^1)^1
|
| = p_1^1
|
| . p_(p_(p_1^1)^(p_1^1))^1
|
| . p_(p_1^1 . p_(p_1^2)^1)^1
|
| = p_1^1
|
| . p_(p_(p_1^1)^(p_1^1))^1
|
| . p_(p_1^1 . p_(p_1^(p_1^1))^1)^1
|
| = p
|
| . p_(p_p^p)
|
| . p_(p . p_(p^p))
|
| |riff(1978)| = 10.
|
| a natural question is:  how many integers are there of a given weight?
| it is easily seen that the enumerating generation function for riffs
| by weight will satisfy the following equation,
| where R(x) = Sum_(k=0)^oo R<k>.x^k:
|
| R(x) = Prod_(m=0)^oo (1 + x^(m+1).R(x))^R<m>
|
| proof:  imagine the riffs arranged in order of increasing weight;
| we may construct any riff by moving along the sequence, & at each
| station either doing nothing (-> 1) or doing three things in succession:
| (1) weighing out a single p to make the place (-> x), at which we get
| our one and only chance (2) for picking up the riff at that place as an
| index (-> x^m), and (3) choosing any riff at all as the exponent (-> R(x)).
| there are then R<m> such choices for distinct indices of weight m,
| (-> R<m> in the exponent of 1 + x.x^m.R(x)).
| 
| this form may be solved for a recursive expression by:
| taking logs, using taylor series identity for log(1+y),
| --
| the functional equation obtained at this stage is:
| R(x) = Exp ( Sum_(j=1)^oo (-1)^(j+1) . R(x^j) . (R(x))^j . (x^j)/j ).
| --,
| multiplying out the powers R^n(x) that result and taking derivatives.
| the result is:
|
| [too complex to write here]
|
| a combinatorial form is:
|
| [too complex to write here]
|
| and the first few terms of the enumerator are:
|
| 1 + 1x + 2x^2 + 6x^3 + 20x^4 + 73x^5 + 281x^6 + 1124x^7 + 4488x^8 + ...

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

I did not know how the SeqFan list processor would handle attachments,
or how your list deals with files, but I have these latter formulas
done up in a Word Doc format, if anybody wants them.  They could
probably use some checking.

Many Regards,

Jon Awbrey

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤