This site is supported by donations to The OEIS Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A078008 Expansion of (1-x)/(1 - x - 2*x^2). 113

%I

%S 1,0,2,2,6,10,22,42,86,170,342,682,1366,2730,5462,10922,21846,43690,

%T 87382,174762,349526,699050,1398102,2796202,5592406,11184810,22369622,

%U 44739242,89478486,178956970,357913942,715827882,1431655766,2863311530,5726623062

%N Expansion of (1-x)/(1 - x - 2*x^2).

%C Conjecture: a(n) = the number of fractions in the infinite Farey row of 2^n terms with even denominators. Compare the Salamin & Gosper item in the Beeler et al. link. - _Gary W. Adamson_, Oct 27 2003

%C Counts closed walks starting and ending at the same vertex of a triangle. 3a(n)=P(C_n,3) chromatic polynomial for 3 colors on cyclic graph C_n. A078008(n) + 2*A001045(n) = 2^n provides decomposition of Pascal's triangle. - _Paul Barry_, Nov 17 2003

%C Permutations with one fixed point avoiding 123 and 132.

%C General form: iterate k -> 2^n-k. See also A001045. - _Vladimir Joseph Stephan Orlovsky_, Dec 11 2008

%C The inverse g.f. generates sequence 1, 0, -2, -2, -2, -2, ...

%C a(n) gives the number of oriented (i.e., unreduced for symmetry) meanders on an (n+2) X 3 rectangular grid; see A201145. - _Jon Wild_, Nov 22 2011

%C Pisano period lengths: 1, 1, 6, 1, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, ... - _R. J. Mathar_, Aug 10 2012

%C a(n) is the number of length n binary words that end in an odd length run of 0's if we do not include the first letter of the word in our run length count. a(4) =6 because we have 0000, 0010, 0110, 1000, 1010, 1110. - _Geoffrey Critzer_, Dec 16 2013

%C a(n) is the top left entry of the n-th power of any of the six 3 X 3 matrices [0, 1, 1; 1, 1, 1; 1, 0, 0], [0, 1, 1; 1, 1, 0; 1, 1, 0], [0, 1, 1; 1, 0, 1; 1, 1, 0], [0, 1, 1; 1, 1, 0; 1, 0, 1], [0, 1, 1; 1, 0, 1; 1, 0, 1] or [0, 1, 1; 1, 0, 0; 1, 1, 1]. - _R. J. Mathar_, Feb 04 2014

%C a(n) is the number of compositions of n into parts of two kinds without part 1. - _Gregory L. Simay_, Jun 04 2018

%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 1.1.10a.

%H T. D. Noe, <a href="/A078008/b078008.txt">Table of n, a(n) for n=0..300</a>

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="http://neilsloane.com/doc/tooth.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]

%H Roland Bacher, <a href="http://arxiv.org/abs/1509.09054">Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle</a>, arXiv:1509.09054 [math.CO], 2015. See Section 4.6.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.

%H Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.

%H P. Barry, A. Hennessey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry1/barry83.html">Notes on a Family of Riordan Arrays and Associated Integer Hankel Transforms </a>, JIS 12 (2009) 09.5.3

%H M. Beeler, R. W. Gosper, R. C. Schroeppel, <a href="http://www.inwap.com/pdp10/hbaker/hakmem/number.html">R. HAKMEM. MIT AI Memo 239, Feb 29 1972</a>. (Item #54 by Salamin & Gosper)

%H Ji Young Choi, <a href="https://www.emis.de/journals/JIS/VOL21/Choi/choi10.html">A Generalization of Collatz Functions and Jacobsthal Numbers</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.

%H Leonhard Euler, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k69587/f255.double.r=introductio+in+analysin+infinitorum">Introductio in analysin infinitorum</a>, (1748), section 216.

%H T. Mansour and A. Robertson, <a href="https://arxiv.org/abs/math/0204005">Refined Restricted Permutations Avoiding Subsets of Patterns of Length Three</a>, arXiv:math/0204005 [math.CO], 2002.

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

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

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%F Euler expands(1-x)/(1 - x - 2*x^2) into an infinite series and finds that the coefficient of the n-th term is (2^n + (-1)^n 2)/3. Section 226 shows that Euler could have easily found the recursion relation: a(n) = a(n-1) + 2a(n-2) with a(0) = 1 and a(1) = 0. - V. Frederick Rickey (fred-rickey(AT)usma.edu), Feb 10 2006. [Typos corrected by Jaume Oliver i Lafont, Jun 01 2009]

%F a(n) = sum_{k=0..floor(n, 3)} binomial(n, f(n)+3k) where f(n) = (0, 2, 1, 0, 2, 1, ...) = A080424(n). - _Paul Barry_, Feb 20 2003

%F E.g.f. (exp(2x) + 2exp(-x))/3. - _Paul Barry_, Apr 20 2003

%F a(n) = A001045(n) + (-1)^n = A000079(n) - 2*A001045(n). - _Paul Barry_, Feb 20 2003

%F a(n) = (1/3)(2^n + 2(-1)^n). - Mario Catalani (mario.catalani(AT)unito.it), Aug 29 2003

%F a(n) = T(n, i/(2sqrt(2)))(-i*sqrt(2)^n - U(n-1, i/(2sqrt(2)))(-i*sqrt(2))^(n-1)/2 - _Paul Barry_, Nov 17 2003

%F a(0)=1, a(n) = 2a(n-1) + 2(-1)^n, n>0; a(n) = sum_{k=0..n} (-1)^k(2^(n-k-1) + 0^(n-k)/2). - _Paul Barry_, Jul 30 2004

%F a(n) = A014113(n-1) for n>0; a(n) = A052953(n-1) - 2*(n mod 2) = sum of n-th row of the triangle in A108561. - _Reinhard Zumkeller_, Jun 10 2005

%F A137208(n+1) - 2*A137208(n) = a(n) signed. - _Paul Curtz_, Aug 03 2008

%F a(n) = A001045(n+1) - A001045(n) - _Paul Curtz_, Feb 09 2009

%F If p[1] =0, and p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - _Milan Janjic_, Apr 29 2010

%F a(n) = 2*(a(n - 2) + a(n - 3) + a(n - 4) .... + a(0)), that is, twice the sum of all the previous terms except the last; with a(0) = 1 and a(1) = 0. - _Benoit Jubin_, Nov 21 2011

%F a(n+1) = 2*A001045(n). - _Benoit Jubin_, Nov 22 2011

%F G.f.: 1 - x + x*Q(0), where Q(k) = 1 + 2*x^2 + (2*k+3)*x - x*(2*k+1 + 2*x)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 05 2013

%F G.f.: 1+ x^2*Q(0), where Q(k) = 1 + 1/(1 - x*(4*k+1+2*x)/(x*(4*k+3+2*x) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jan 01 2014

%F a(n) = 3*a(n-2) + 2*a(n-3). - _David Neil McGrath_, Sep 10 2014

%t k=0;lst={1, k};Do[k=2^n-k;AppendTo[lst, k], {n, 1, 5!}];lst (* _Vladimir Joseph Stephan Orlovsky_, Dec 11 2008 *)

%t CoefficientList[Series[(1-x)/(1-x-2x^2),{x,0,50}],x] (* _Harvey P. Dale_, Mar 30 2011 *)

%t LinearRecurrence[{1, 2}, {1, 0}, 35] (* _Jean-François Alcover_, Sep 23 2017 *)

%o (PARI) a(n)=(1<<n+2*(-1)^n)/3 \\ _Charles R Greathouse IV_, Jun 10 2011

%Y Cf. A001045.

%Y See A151575 for a signed version.

%Y Bisections: A047849, A020988.

%Y Cf. A151548, A139250, A151555, A153006.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, Nov 17 2002

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 17 17:23 EST 2019. Contains 319250 sequences. (Running on oeis4.)