

A113166


Total number of white pearls remaining in the chest  see Comments.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

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 npearled 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 equivalent necklaces can be found in the chest.
5. Counting the total number of white pearls left in the chest gives a(n).


REFERENCES

C. Dement, Floretiongenerated Integer Sequences (work in progress).


LINKS

Max Alekseyev, Table of n, a(n) for n = 1..50
C. Dement and Max Alekseyev, Notes on A113166


FORMULA

a(n) = sum_{k=1...[n/2]} k/(nk) sum_{j=1...gcd(n,k)} { (nk)*gcd(n,k,j)/gcd(n,k) choose k*gcd(n,k,j)/gcd(n,k) } (Alekseyev).
a(p) = Fib(p1) for all primes, where Fib = A000045 (Creighton Dement and Antti Karttunen, proved by Max Alekseyev).


PROG

(PARI) A113166(n) = sum(k=1, n\2, k/(nk) * sum(j=1, gcd(n, k), binomial((nk)*gcd([n, k, j])/gcd(n, k), k*gcd([n, k, j])/gcd(n, k)) ))


CROSSREFS

Cf. A034748, A006206, A000358, A000045, A000204.
Sequence in context: A205977 A238623 A138135 * A126872 A094966 A095068
Adjacent sequences: A113163 A113164 A113165 * A113167 A113168 A113169


KEYWORD

nonn


AUTHOR

Creighton Dement, Jan 05 2006; Jan 08 2006; Jul 29 2006


EXTENSIONS

More terms from Max Alekseyev, Jun 20 2006


STATUS

approved



