Date: Tue, 20 Jun 2006 00:48:52 +0200
Subject: Better definition for A113166
From: "Creighton Dement"
Dear Seqfans,
Among my submitted sequences, two favorites are A113166 and A113910. At
the time I submitted A113166, I found it hard to give a clear and
concise definition.
Perhaps I've found a better formulation of A113166 (see below).
However, I doubt the steps given allow one to compute the terms of this
sequence as efficiently as possible. I would be very pleased if someone
could add comments or extend this sequence.
Sincerely,
Creighton
Alternative definition of A113166: define a(1) = 0. To calculate a(n),
1. Expand (A + B)^n into 2^n words of length n consisting of letters A
and B (i.e., use of the distributive and associative laws of
multiplication but assume A and B do not commute).
2. To each of the 2^n words, associate a free binary necklace consisting
of n "black and white pearls". Figuratively, all 2^n necklaces can be
placed inside a treasure chest.
3. Remove all n-pearled necklaces which are found to have (at least) two
adjacent white pearls from the chest.
4. If two necklaces are found to be equivalent, remove one of them from
the chest. Continue until no two equivilant necklaces can be found in
the chest.
5. Counting the total number of white pearls left in the chest returns
a(n).
Ex. a(2)
Step 1. (A + B)^2 = AA + AB + BA + BB
Step 2. Chest = {AA, AB, BA, BB}
Step 3. Chest = {AB, BA, BB}
Step 4. Chest = {BA, BB}
Step 5. a(2) = 1
Ex. a(3)
Step 1. (A + B)^3 = (AAA + ABA + BAA + BBA) + (AAB + ABB + BAB + BBB)
Step 2. Chest = {AAA, ABA, BAA, BBA, AAB, ABB, BAB, BBB}
Step 3. Chest = {BBA, ABB, BAB, BBB}
Step 4. Chest = {BBA, BBB}
Step 5. a(3) = 1
To see how the above relates to Lucas / Pell numbers, observe the
following:
Set A equal to the 4X4 matrix
[[0.,-1.,1.,-1.],[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.]] and
B = [[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.],[-1.,1.,0.,-1.]]. Then
trace((A+B)^n) leads to the n-th Lucas number.
On the other hand, if A =
[[0.,-2.,1.,-1.],[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.]] and B =
[[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.],[-1.,1.,0.,-2.]], then
trace((A+B)^n) leads to the n-th term of Numerators of continued
fraction convergents to sqrt(2), A001333 (where "leads to" is written to
avoid referring to the sign / common multiple of the sequences).
What do A and B defined as matrices have to do with the A and B from
above? Observe that A^2 = 0 in both cases and to each of the 5 steps, we
can find an "equivalent step" involving matrices:
Steps 1: same as above.
Step 2: Using trace(X + Y) = trace(X) + trace(Y) for square matrices,
partition trace((A+B)^n) into the sum of 2^n terms.
Step 3. Using the property that A^2 = 0, remove any terms of the form
trace(X) where X is the zero-matrix.
Step 4. Using the property trace(XY) = trace(YX) for square matrices X
and Y, if two matrices from the chest can be shown to have the same
trace (without explicitely substituting values), remove one of the terms
from the sum.
Step 5. Count the A's.
Note that a(1) = 0 was defined as such because trace(A+B) = trace(A) +
trace(B) = trace(B) and the total number of A's in trace(B) is 0.
Date: Tue, 20 Jun 2006 03:44:29 -0700
From: Max
Creighton,
From your new definition of A113166 it follows an explicit formula:
A113166(n) = \sum_{k=1}^{[n/2]} k/(n-k) \sum_{j=1}^{gcd(n,k)} {
(n-k)*gcd(n,k,j)/gcd(n,k) \choose k*gcd(n,k,j)/gcd(n,k) }
or as a PARI/GP program:
{ A113166(n) = sum(k=1,n\2, k/(n-k) * sum(j=1,gcd(n,k),
binomial((n-k)*gcd([n,k,j])/gcd(n,k),k*gcd([n,k,j])/gcd(n,k)) )) }
In particular, for n=1..50 we have
0, 1, 1, 3, 3, 8, 8, 17, 23, 41, 55, 102, 144, 247, 387, 631, 987,
1636, 2584, 4233, 6787, 11011, 17711, 28794, 46380, 75181, 121441,
196685, 317811, 514712, 832040, 1346921, 2178429, 3525581, 5702937,
9229314, 14930352, 24160419, 39088469, 63250315, 102334155, 165587436,
267914296, 433505523, 701409597, 1134920903, 1836311903, 2971245198,
4807527024, 7778788585
This explicit formula also helps to prove the conjecture
%F A113166 Conjecture: a(p) = Fib(p-1) for all primes, where Fib =
A000045 (Creighton Dement and Antti Karttunen).
If n=p for prime p, then gcd(n,k) and gcd(n,k,j) in the formula equal
1 implying much simpler formula:
A113166(p) = \sum_{k=1}^{[p/2]} k/(n-k) { n-k \choose k }
= \sum_{k=1}^{[p/2]} { n-k-1 \choose k-1 }
which equals Fib(p-1) according to formula (61) at
http://mathworld.wolfram.com/FibonacciNumber.html
Max