OFFSET
0,2
COMMENTS
Row sums of A132110. - Gary W. Adamson, Aug 09 2007
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
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Tomas Flouri, Costas S. Iliopoulos, Solon P. Pissis, and W. F. Smyth, On approximate string covering (draft, 2012). [Broken link]
Tomas Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth, and Wojciech Tyczynski, New and efficient approaches to the quasiperiodic characterization of a string, Proc. Prague Stringology Conf., 2012, pp. 75-88.
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).
FORMULA
a(n) = 2*a(n-1) + n, with a(0)=1.
Binomial transform of [1, 2, 3, 3, 3, ...]. - Gary W. Adamson, Aug 09 2007
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
a(n) = (A227712(n) - 1)/3. - Emeric Deutsch, Feb 18 2016
a(n) = A007283(n) - n - 2. - Miquel Cerda, Aug 07 2016
a(n) = A000225(n) + A000325(n+1). - Miquel Cerda, Aug 08 2016 [corrected by Falk Hüffner, Jun 14 2026]
From Elmo R. Oliveira, Mar 09 2026: (Start)
a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3).
E.g.f.: 3*exp(2*x) - (x + 2)*exp(x). (End)
MATHEMATICA
lst={}; Do[AppendTo[lst, 3*2^n-n-2], {n, 0, 4!}]; lst (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)
(* Alternative: *)
LinearRecurrence[{4, -5, 2}, {1, 3, 8}, 40] (* Vincenzo Librandi, Jun 23 2012 *)
PROG
(PARI) a(n)=3<<n-n-2 \\ Charles R Greathouse IV, Feb 29 2012
(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
Benoit Cloitre, Jan 25 2003
STATUS
approved