Riffs & Rotes & A061396 & A062537
Jon Awbrey
jawbrey at oakland.edu
Wed Jun 27 13:44:25 CEST 2001
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
I A062537
%S A062537 0,1,2,2,3,3,3,3,3,4,4,4,4,4,5,3,4,4,4,5,5,5,4,5,4,5,4,5,5,6,5,4,6,5,6,
%T A062537 5,5,5,6,6,5,6,5,6,6,5,6,5,4,5,6,6,4,5,7,6,6,6,5,7,5,6,6,4,7,7,5,6,6,7,
%U A062537 6,6,6,6,6,6,7,7,6,6,4,6,5,7,7,6,7,7,6,7,7,6,7,7,7,6,5,5,7,6,6,7,5,7,8
%N A062537 Nodes in riff (rooted index-functional forest) for n.
%C A062537 A061396(n) gives number of times n appears in this sequence.
%H A062537 J. Awbrey, <a href="http://www.research.att.com/~njas/sequences/a061396a.txt">
Illustrations of riffs for small integers</a>
%F A062537 a(PROD(p_i^e_i)) = SUM(a(i)+a(e_i)+1), product over nonzero e_i in prime factorizati on.
%K A062537 nonn,easy,nice,new
%O A062537 1,3
%A A062537 dww, Jun 25, 2001
Let N = positive integers.
A062537 : N -> N such that
A062537 : n ~> |riff(n)| = Cardinality (Points(riff(n))),
AKA the "weight", or the number of nodes in the riff of n.
This is what I was referring to as a "measure of complexity" on the positive integers.
Some of the only work that I was able to find on simlilar notions was in Hardy & Wright,
where there was a little bit on what they called measures of "roundness". Of course,
if we want to instantly double the number of sequences in the EIS, we could simply
now form the functional composition A062537(A-whatever) = |riff(A-whatever)|.
Exercise for the reader. But of course, again, some of the more interesting
cases would be where it does not quite double, but coincides with sequences
that are already indexed. The mind boggles.
The mindset of the graph counting circle where I was doing this work was so focussed
on the enumeration functions themselves, nice monotone sequences and their asymptotics,
that I would not even have regarded this as a sequence, but now that it is, it encourages
me to go back and look at those other measures of complexity, based on more familiar families
of graphs, like the rooted trees in Göebel's correspondence, or the planted plane tree measures
that I was looking at. So I will go see what I can dig up from the runes.
Jon Awbrey
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Jon Awbrey wrote:
>
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
>
> David W. Wilson wrote:
> >
> > Let R(n) be the number nodes in the riff of n.
>
> Permit me to translate into my personal pidgin as I try to follow.
> It will take me a bit to adjust as I used to use R(x) for the g.f.
>
> your R(n) = my |riff(n)|
>
> > Then we have
> >
> > R(n) = R(PROD(p_i^e_i)) = SUM(R(p_i^e_i)) = SUM(R(i) + R(e_i) + 1).
>
> Yup.
>
> > Now suppose we wish to find the smallest n with R(n) = k.
> > Then we have
> >
> > k = SUM(R(p_i^e_i))
> >
> > that is, the R(p_i^e_i) form a partition of k. Thus, to find n,
> > we must run through the partitions {a_j} of k, choose all possible
> > distinct i and e_i with R(p_i^e_i) = a_j, and minimize n = PROD(p_i^e_i)
> > over these i and e_i.
> >
> > In general, there are a large number of prime powers p_i^e_i with
> > R(p_i^e_i) = a_j. However, given that our aim is to minimize n,
> > we can neglect all but the smallest few p_i^e_i for each a_j.
> > Doing this makes the computation of n tractable, and allows
> > us to extend the above sequence to:
> >
> > 1 2 3 5 10 15 30 55 105 165 330 660 1155 2145 4290 7755 15015 30030
> > 54285 100815 201630 403260 705705 1411410 2822820 5645640 11392095
> > 20465445 40930890 79744665 159489330 318978660 637957320 1321483020
>
> Okay, this more or less makes sense to me.
> Both of my old multinomial formulas had lots
> of summations over partitions of this'n'that.
> Somewhere out of those, or maybe independently,
> I came up with schematic enumeration polynomials
> like the following, which are what I used in order
> to generate those tables I gave in an earlier note.
>
> Here is another page from my notes. This looks like a clean copy
> sum up of work that I had probably drudged away at for many moons:
>
> | 1979-01-07
> |
> | Write "{n}" for "the set of riffs of order n".
> | A schematic expression like "p_{i}^{j}" then
> | signifies the set of all riffs on that theme.
> |
> | Schematic Enumeration Polynomials.
> | [ Here, I am using R_k for a(k). ]
> |
> o-------------------------------------------------o--------------------------------------------------
> | {n} |
> o-------------------------------------------------o--------------------------------------------------
> | {n-1} |
> | {2} = p< + p< | R_2 = 2R_1
> | {n-1} |
> o-------------------------------------------------o--------------------------------------------------
> | {n-1} {n-2} |
> | {3} = p< + p< + p p< + p< | R_3 = 2R_2 + 2R_1
> | {n-1} {n-2} p |
> o-------------------------------------------------o--------------------------------------------------
> | {n-1} {n-2} |
> | {4} = p< + p< + p p< + p< |
> | {n-1} {n-2} p |
> | | R_4 = 2R_3 + 3R_2 + 2R_1
> | p {n-3} p |
> | + p< + p p< + p< p< |
> | {n-2} p {n-3} |
> o-------------------------------------------------o--------------------------------------------------
> | {n-1} {n-2} |
> | {5} = p< + p< + p p< + p< |
> | {n-1} {n-2} p |
> | |
> | p {n-3} p |
> | + p< + p p< + p< p< |
> | {n-2} p {n-3} | R_5 = 2R_4 + 3R_3 + 5R_2 + R_2^2 + R_1^3
> | |
> | p {n-3} | = 2R_4 + 3R_3 + 7R_2 + R_1
> | + p p< + p< p< + p< p< |
> | {n-3} p p {n-3} |
> | |
> | {n-3} {n-4} {n-4} |
> | + p< + p< p< |
> | {n-3} {n-4} |
> o-------------------------------------------------o--------------------------------------------------
>
> I carried this sort of scheme out successfully through weight 7,
> but must have lapsed in arithmetic or schematic on weights of 8.
>
> Thanks for your interest and your work on this problem.
> I rechnen that there's a bunch more fun to be had here.
>
> Jon Awbrey
>
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
More information about the SeqFan
mailing list