|
|
A079583
|
|
a(n) = 3*2^n - n - 2.
|
|
17
|
|
|
1, 3, 8, 19, 42, 89, 184, 375, 758, 1525, 3060, 6131, 12274, 24561, 49136, 98287, 196590, 393197, 786412, 1572843, 3145706, 6291433, 12582888, 25165799, 50331622, 100663269, 201326564, 402653155, 805306338, 1610612705, 3221225440
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Consider the infinite sequence of strings x(1) = a, x(2) = aba, x(3) = ababbaba, ..., where x(n+1) = x(n).b^{n+1}.x(n), for n >= 1. Each x(n), for n >= 2, has borders x(1), x(2), ..., x(n-1), none of which cover x(n). The length of x(n+1) is 3*2^n-n-2. - William F. Smyth, Feb 29 2012
Number of edges in the rooted tree g[n] (n>=0) defined recursively in the following manner: denoting by P[n] the path on n vertices, we define g[0] =P[2] while g[n] (n>=1) is the tree obtained by identifying the roots of 2 copies of g[n-1] and one of the end-vertices of P[n+1]; the root of g[n] is defined to be the other end-vertex of P[n+1]. Roughly speaking, g[4], for example, is obtained from the planted full binary tree of height 5 by replacing the edges at the levels 1,2,3,4 with paths of lengths 4, 3, 2, and 1, respectively. - Emeric Deutsch, Aug 08 2013
|
|
REFERENCES
|
T. Flouri, C. S. Iliopoulos, T. Kociumaka, S. P. Pissis, S. J. Puglisi, W. F. Smyth, W. Tyczynski, New and efficient approaches to the quasiperiodic characterization of a string, Proc. Prague Stringology Conf., 2012, 75-88.
|
|
LINKS
|
|
|
FORMULA
|
a(0)=1, a(n) = 2*a(n-1) + n;
G.f.: (x^2-x+1)/((1-2*x)*(1-x)^2) = 3*U(0)x, where U(k) = 1 - (k+2)/(3*2^k - 18*x*4^k/(6*x*2^k - (k+2)/U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Jul 04 2012
|
|
MATHEMATICA
|
|
|
PROG
|
(Magma) I:=[1, 3, 8]; [n le 3 select I[n] else 4*Self(n-1)-5*Self(n-2)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 23 2012
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|