A005819 Number of words of length n in a certain language. (Formerly M1584)

1, 2, 6, 12, 22, 34, 52, 74, 102, 134, 176, 222, 280, 344, 416, 496, 592, 694, 814, 942, 1082, 1232, 1404, 1584, 1784, 1996, 2226, 2468, 2738, 3016, 3324, 3648, 3992, 4352, 4736, 5132, 5564, 6014, 6488, 6978, 7508, 8050, 8634, 9238, 9866, 10516, 11212

Offset

1,2

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Herman Jamke, Table of n, a(n) for n = 1..100

J. Berstel and M. Pocchiola, A geometric proof of the enumeration formula for Sturmian words, Internat. J. Algeb. Comput., 3(3):349-355, 1993. - Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

S. Dulucq, Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)

S. Dulucq and D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm, Theoret. Comput. Sci. 71 (1990), 381-400.

Formula

a(n) = -1 + Sum_{i=1..n} (n-i+1)*phi(i) for n>=2, where phi is Euler's totient function (this is conjectured in the Duluck & Gouyou-Beauchamps paper, p. 399).

Prog

(PARI) a(n)=if(n<2, n>0, sum(i=1, n, (n-i+1)*eulerphi(i))-1) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

Crossrefs

Sequence in context: A147623 A232234 A045964 * A322072 A304627 A168193

Adjacent sequences: A005816 A005817 A005818 * A005820 A005821 A005822

Keyword

nonn

Author

N. J. A. Sloane and Simon Plouffe

Extensions

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

Status

approved