# Riffs & Rotes & A061396

Jon Awbrey jawbrey at oakland.edu
Tue Jun 26 00:24:52 CEST 2001

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

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