A "Lucas Inversion Formula" for "Number of aperiodic binary necklaces with no subsequence 00"

Creighton Dement crowdog at crowdog.de
Tue Oct 25 00:32:41 CEST 2005


Dear Seqfans, 

This looks very neat to me, so I will go ahead and post it and hope
someone can prove it (the fact that the original "problem" came up under
the setting of floretions is, at least for the moment, beside the point)
if it has not already been formulated. 

Counting the number of occurances of the number m in the m-th "Lucas
String":
http://www.crowdog.de/LucasStrings.html  
(conjecture: Number of elements in the N-th set is Lucas(N) and all
divisiors of N are present on the string)

led me directly to: Number of aperiodic binary necklaces with no
subsequence 00, excluding the necklace "0". Comments:  Euler transform
is Fibonacci(n+1).
http://www.research.att.com/projects/OEIS?Anum=A006206

Moreover, it allowed me to reformulate what I was doing in terms of
(free) necklaces. 

The formula given for A006206 is 1/n * sum over d divides n of {mu(n/d)
* Lucas_d} 

Ex. A006206(5) = (1/5)*(mu(5)*Lucas(1) + mu(1)*Lucas(5) ) = (1/5)*(-1 +
11) = 2. 

However, a closer inspection of the "Lucas Strings" leads me to
conjecture:

Lucas(n) =  sum over d divides n of d*A006206(d)

Ex. Lucas(5) =  11 = 1*1 + 5*2  = 1*A006206(1) + 5*A006206(5) 
Lucas(18) = 5778 =  1*1 + 2*1 + 3*1 + 6*2 +  9*8 + 18*316 = 
1*A006206(1) + 2*A006206(2)  + 3*A006206(3) + 6*A006206(6) +
9*A006206(9)

It would seem this conjecture is somehow a direct consequence of the
above formula given for A006206 (or perhaps that it is the Euler
transform of Fib)... am I correct here?  If nothing else, I believe it
should  be added as a comment to Lucas A000204.

Here is another comment I found that looks quite relevant: 
L(n) is the number of points of period n in the golden mean shift. The  
            number of orbits of length n in the golden mean shift is
given by the n-th               term of the sequence A006206 - Thomas
Ward (t.ward(AT)uea.ac.uk), Mar               13 2001

Lastly, what I'm fairly convinced of: Pell is working "behind the
scenes", here. 
There should be a similar relation involving Pell numbers (so it would
seem upon inserting powers of two in the right places). However, it may
be too cumbersome to use- I'll check later.  Thanks.

Sincerely, 
Creighton

 








More information about the SeqFan mailing list