A079583 a(n) = 3*2^n - n - 2.

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

Offset: 0

Author

Benoit Cloitre, Jan 25 2003

Keywords

• nonn
• easy

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

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

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Tomas Flouri, Costas S. Iliopoulos, Solon P. Pissis, W. F. Smyth, On approximate string covering (draft, 2012).
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

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

Programs

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

Mathematica

lst={};Do[AppendTo[lst, 3*2^n-n-2], {n, 0, 4!}];lst (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)
LinearRecurrence[{4,-5,2},{1,3,8},40] (* Vincenzo Librandi, Jun 23 2012 *)

PARI

a(n)=3<Charles R Greathouse IV, Feb 29 2012

Formula

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

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). - Miquel Cerda, Aug 08 2016