A003945 - OEIS

%I #130 Jun 01 2024 11:56:28

%S 1,3,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,

%T 196608,393216,786432,1572864,3145728,6291456,12582912,25165824,

%U 50331648,100663296,201326592,402653184,805306368,1610612736,3221225472,6442450944,12884901888

%N Expansion of g.f. (1+x)/(1-2*x).

%C Coordination sequence for infinite tree with valency 3.

%C Number of Hamiltonian cycles in K_3 X P_n.

%C Number of ternary words of length n avoiding aa, bb, cc.

%C For n > 0, row sums of A029635. - _Paul Barry_, Jan 30 2005

%C Binomial transform is {1, 4, 13, 40, 121, 364, ...}, see A003462. - _Philippe Deléham_, Jul 23 2005

%C Convolved with the Jacobsthal sequence A001045 = A001786: (1, 4, 12, 32, 80, ...). - _Gary W. Adamson_, May 23 2009

%C Equals (n+1)-th row sums of triangle A161175. - _Gary W. Adamson_, Jun 05 2009

%C a(n) written in base 2: a(0) = 1, a(n) for n >= 1: 11, 110, 11000, 110000, ..., i.e.: 2 times 1, (n-1) times 0 (see A003953(n)). - _Jaroslav Krizek_, Aug 17 2009

%C INVERTi transform of A003688. - _Gary W. Adamson_, Aug 05 2010

%C An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 42, 138, 162 and 168, lead to this sequence. For the corner squares these vectors lead to the companion sequence A083329. - _Johannes W. Meijer_, Aug 15 2010

%C A216022(a(n)) != 2 and A216059(a(n)) != 3. - _Reinhard Zumkeller_, Sep 01 2012

%C Number of length-n strings of 3 letters with no two adjacent letters identical. The general case (strings of r letters) is the sequence with g.f. (1+x)/(1-(r-1)*x). - _Joerg Arndt_, Oct 11 2012

%C Sums of pairs of rows of Pascal's triangle A007318, T(2n,k)+T(2n+1,k); Sum_{n>=1} A000290(n)/a(n) = 4. - _John Molokach_, Sep 26 2013

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

%H Yasemin Alp and E. Gokcen Kocer, <a href="https://doi.org/10.1007/s00025-024-02193-5">Exponential Almost-Riordan Arrays</a>, Results Math. (2024) Vol. 79, 173.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=151">Encyclopedia of Combinatorial Structures 151</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=304">Encyclopedia of Combinatorial Structures 304</a>

%H Markus Kuba and Alois Panholzer, <a href="http://dx.doi.org/10.1016/j.disc.2012.07.011">Enumeration formulas for pattern restricted Stirling permutations</a>, Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012

%H C. Richard and U. Grimm, <a href="https://arxiv.org/abs/math/0302302">On the entropy and letter frequencies of ternary squarefree words</a>, arXiv:math/0302302 [math.CO], 2003.

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

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

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(0) = 1; for n > 0, a(n) = 3*2^(n-1).

%F a(n) = 2*a(n-1), n > 1; a(0)=1, a(1)=3.

%F More generally, the g.f. (1+x)/(1-k*x) produces the sequence [1, 1 + k, (1 + k)*k, (1 + k)*k^2, ..., (1+k)*k^(n-1), ...], with a(0) = 1, a(n) = (1+k)*k^(n-1) for n >= 1. Also a(n+1) = k*a(n) for n >= 1. - _Zak Seidov_ and _N. J. A. Sloane_, Dec 05 2009

%F The g.f. (1+x)/(1-k*x) produces the sequence with closed form (in PARI notation) a(n)=(n>=0)*k^n+(n>=1)*k^(n-1). - _Jaume Oliver Lafont_, Dec 05 2009

%F Binomial transform of A000034. a(n) = (3*2^n - 0^n)/2. - _Paul Barry_, Apr 29 2003

%F a(n) = Sum_{k=0..n} (n+k)*binomial(n, k)/n. - _Paul Barry_, Jan 30 2005

%F a(n) = Sum_{k=0..n} A029653(n, k)*x^k for x = 1. - _Philippe Deléham_, Jul 10 2005

%F Binomial transform of A000034. Hankel transform is {1,-3,0,0,0,...}. - _Paul Barry_, Aug 29 2006

%F a(0) = 1, a(n) = 2 + Sum_{k=0..n-1} a(k) for n >= 1. - _Joerg Arndt_, Aug 15 2012

%F a(n) = 2^n + floor(2^(n-1)). - _Martin Grymel_, Oct 17 2012

%F E.g.f.: (3*exp(2*x) - 1)/2. - _Stefano Spezia_, Jan 31 2023

%p k := 3; if n = 0 then 1 else k*(k-1)^(n-1); fi;

%t Join[{1}, 3*2^Range[0, 60]] (* _Vladimir Joseph Stephan Orlovsky_, Jun 09 2011 *)

%t Table[2^n+Floor[2^(n-1)], {n,0,30}] (* _Martin Grymel_, Oct 17 2012 *)

%t CoefficientList[Series[(1+x)/(1-2x),{x,0,40}],x] (* or *) LinearRecurrence[ {2},{1,3},40] (* _Harvey P. Dale_, May 04 2017 *)

%o (PARI) a(n)=if(n,3<<n--,1) \\ _Charles R Greathouse IV_, Jan 12 2012

%Y Essentially same as A007283 (3*2^n) and A042950.

%Y Cf. A001787, A001045, A161175.

%Y Generating functions of the form (1+x)/(1-k*x) for k=1 to 12: A040000, A003945, A003946, A003947, A003948, A003949, A003950, A003951, A003952.

%Y Generating functions of the form (1+x)/(1-k*x) for k=13 to 30: A170732, A170733, A170734, A170735, A170736, A170737, A170738, A170739, A170740, A170741, A170742, A170743, A170744, A170745, A170746, A170747, A170748.

%Y Generating functions of the form (1+x)/(1-k*x) for k=31 to 50: A170749, A170750, A170751, A170752, A170753, A170754, A170755, A170756, A170757, A170758, A170759, A170760, A170761, A170762, A170763, A170764, A170765, A170766, A170767, A170768, A170769.

%Y Cf. A003688.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_

%E Edited by _N. J. A. Sloane_, Dec 04 2009