login
A005819
Number of words of length n in a certain language.
(Formerly M1584)
10
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
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
KEYWORD
nonn
EXTENSIONS
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008
STATUS
approved