login
Expansion of (1-x)/( (1+x)*(1-2*x) ).
135

%I #182 May 13 2024 11:43:16

%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)*(1-2*x) ).

%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. 3*a(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

%C a(n) is the number of words of length n over a binary alphabet whose position in the lexicographic order is a multiple of three. a(3) = 2: aba, bab. - _Alois P. Heinz_, Apr 13 2022

%C a(n) is the number of words of length n over a ternary alphabet starting with a fixed letter (say, 'a') and ending in a different letter, such that no two adjacent letters are the same. a(4) = 6: abab, abac, abcb, acab, acac, acbc. - _Ignat Soroko_, Jul 19 2023

%D Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.

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

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

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.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 Paul Barry, <a href="https://arxiv.org/abs/1912.01124">A Note on Riordan Arrays with Catalan Halves</a>, arXiv:1912.01124 [math.CO], 2019.

%H Paul Barry, <a href="https://arxiv.org/abs/2004.04577">On a Central Transform of Integer Sequences</a>, arXiv:2004.04577 [math.CO], 2020.

%H Paul Barry and 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, and 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 E. Esteves-Rams, C. L. Azana Ricardo, B. Aragon Fernandez, <a href="https://doi.org/10.1524/zkri.220.7.592.67101">An alternative expression for counting the number of close-packaged polytypes</a>, Z. Krist. 220 (2005) 592-595, eq (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 Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 13.

%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 Lafont_, Jun 01 2009]

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

%F E.g.f. (exp(2*x) + 2*exp(-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) = (2^n + 2*(-1)^n)/3. - Mario Catalani (mario.catalani(AT)unito.it), Aug 29 2003

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

%F From _Paul Barry_, Jul 30 2004: (Start)

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

%F a(n) = Sum_{k=0..n} (-1)^k*(2^(n-k-1) + 0^(n-k)/2). (End)

%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

%F a(n) = (-1)^n * A151575(n). - _G. C. Greubel_, Jun 28 2019

%F a(n)+a(n+1) = 2^n. - _R. J. Mathar_, Feb 24 2021

%F a(n) = -a(2-n) * (-2)^(n-1) = (3/2)*(a(n-1) + a(n-2)) - a(n-3) for all n in Z. - _Michael Somos_, Mar 18 2022

%e G.f. = 1 + 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + ... - _Michael Somos_, Mar 18 2022

%t Table[(2^n + 2*(-1)^n)/3, {n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Dec 11 2008; modified by _G. C. Greubel_, Jun 28 2019 *)

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

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

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

%o (Magma) [(2^n + 2*(-1)^n)/3: n in [0..40]]; // _G. C. Greubel_, Jun 28 2019

%o (Sage) [(2^n + 2*(-1)^n)/3 for n in (0..40)] # _G. C. Greubel_, Jun 28 2019

%o (GAP) List([0..40], n-> (2^n + 2*(-1)^n)/3) # _G. C. Greubel_, Jun 28 2019

%Y First differences of 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