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