%I #79 Feb 13 2022 04:10:19

%S 1,3,8,19,42,89,184,375,758,1525,3060,6131,12274,24561,49136,98287,

%T 196590,393197,786412,1572843,3145706,6291433,12582888,25165799,

%U 50331622,100663269,201326564,402653155,805306338,1610612705,3221225440

%N a(n) = 3*2^n - n - 2.

%C Row sums of A132110. - _Gary W. Adamson_, Aug 09 2007

%C 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

%C 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

%D 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.

%H Vincenzo Librandi, <a href="/A079583/b079583.txt">Table of n, a(n) for n = 0..1000</a>

%H Tomas Flouri, Costas S. Iliopoulos, Solon P. Pissis, W. F. Smyth, <a href="http://www.inf.kcl.ac.uk/pg/pississo/approx_covers.pdf">On approximate string covering</a> (draft, 2012).

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).

%F a(0)=1, a(n) = 2*a(n-1) + n;

%F Binomial transform of [1, 2, 3, 3, 3, ...]. - _Gary W. Adamson_, Aug 09 2007

%F 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

%F a(n) = (A227712(n) - 1)/3 - _Emeric Deutsch_, Feb 18 2016

%F a(n) = A007283(n) - n - 2. - _Miquel Cerda_, Aug 07 2016

%F a(n) = A000225(n) + A000325(n). - _Miquel Cerda_, Aug 08 2016

%t lst={};Do[AppendTo[lst, 3*2^n-n-2], {n, 0, 4!}];lst (* _Vladimir Joseph Stephan Orlovsky_, Oct 25 2008 *)

%t LinearRecurrence[{4,-5,2},{1,3,8},40] (* _Vincenzo Librandi_, Jun 23 2012 *)

%o (PARI) a(n)=3<<n-n-2 \\ _Charles R Greathouse IV_, Feb 29 2012

%o (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

%Y Cf. A000295, A132110, A227712, A083329 (first differences).

%K nonn,easy

%O 0,2

%A _Benoit Cloitre_, Jan 25 2003