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