login
Expansion of (1-2*x)/(1-4*x).
100

%I #114 Apr 23 2023 07:30:38

%S 1,2,8,32,128,512,2048,8192,32768,131072,524288,2097152,8388608,

%T 33554432,134217728,536870912,2147483648,8589934592,34359738368,

%U 137438953472,549755813888,2199023255552,8796093022208,35184372088832

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

%C Binomial transform of A046717. Second binomial transform of A000302 (with interpolated zeros). Partial sums are A007583.

%C Counts closed walks of length 2n at a vertex of the cyclic graph on 4 nodes C_4. With interpolated zeros, counts closed walks of length n at a vertex of the cyclic graph on 4 nodes C_4. - _Paul Barry_, Mar 10 2004

%C In general, Sum_{k=0..n} Sum_{j=0..n} C(2(n-k), j)*C(2k, j)r^j has expansion (1-(r+1)x)/(1+(r+3)x+(r-1)(r+3)x^2+(r-1)^3*x^3). - _Paul Barry_, Jun 04 2005

%C a(n) is the number of binary strings of length 2n with an even number of 0's (and hence an even number of 1's). - _Toby Gottfried_, Mar 22 2010

%C Number of compositions of n where there are 2 sorts of part 1, 4 sorts of part 2, 8 sorts of part 3, ..., 2^k sorts of part k. - _Joerg Arndt_, Aug 04 2014

%C a(n) is also the number of permutations simultaneously avoiding 231 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - _Manda Riehl_ Aug 07 2014

%C INVERT transform of powers of 2 (A000079). - _Alois P. Heinz_, Feb 11 2021

%C a(n) is the number of elements in an n-interval of the binomial poset of even-sized subsets of positive integers, cf. Stanley reference and second formula by Paul Barry. Each multichain 0 = x_0 <= x_1 <= x_2 = 1 in such an n-interval corresponds to a closed walk described above by Paul Barry. More generally, each multichain 0 = x_0 <= x_1 <= ... <= x_k = 1 corresponds to a closed walk of length 2n on the k-dimensional hypercube, cf. A054879, A092812, A121822. - _Geoffrey Critzer_, Apr 21 2023

%D Richard P. Stanley, Enumerative Combinatorics, Vol 1, second edition, Example 3.18.3-f, page 323.

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

%H Milan Janjic, <a href="https://pmf.unibl.org/wp-content/uploads/2017/10/enumfun.pdf">Enumerative Formulas for Some Functions on Finite Sets</a>

%H M. Paukner, L. Pepin, M. Riehl, and J. Wieser, <a href="https://arxiv.org/abs/1511.00080">Pattern Avoidance in Task-Precedence Posets</a>, arXiv:1511.00080 [math.CO], 2015-2016.

%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 (4).

%F G.f.: (1-2*x)/(1-4*x).

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

%F a(n) = (4^n+0^n)/2 (i.e., 1 followed by 4^n/2, n > 0).

%F E.g.f.: exp(2*x)*cosh(2*x) = (exp(4*x)+exp(0))/2. - _Paul Barry_, May 10 2003

%F a(n) = Sum_{k=0..n} C(2*n, 2*k). - _Paul Barry_, May 20 2003

%F a(n) = A001045(2*n+1) - A001045(2*n-1) + 0^n/2. - _Paul Barry_, Mar 10 2004

%F a(n) = 2^n*A011782(n); a(n) = gcd(A011782(2n), A011782(2n+1)). - _Paul Barry_, Jan 12 2005

%F a(n) = Sum_{k=0..n} Sum_{j=0..n} C(2*(n-k), j)*C(2*k, j). - _Paul Barry_, Jun 04 2005

%F a(n) = Sum_{k=0..n} A038763(n,k). - _Philippe Deléham_, Sep 22 2006

%F a(n) = Integral_{x=0..4} p(n,x)^2/(Pi*sqrt(x(4-x))) dx, where p(n,x) is the sequence of orthogonal polynomials defined by C(2*n,n): p(n,x) = (2*x-4)*p(n-1,x) - 4*p(n-2,x), with p(0,x)=1, p(1,x)=-2+x. - _Paul Barry_, Mar 01 2007

%F a(n) = ((2+sqrt(4))^n + (2-sqrt(4))^n)/2. - Al Hakanson (hawkuu(AT)gmail.com), Nov 22 2008

%F a(n) = A000079(n) * A011782(n). - _Philippe Deléham_, Dec 01 2008

%F a(n) = A004171(n-1) = A028403(n) - A000079(n) for n >= 1. - _Jaroslav Krizek_, Jul 27 2009

%F a(n) = Sum_{k=0..n} A201730(n,k)*3^k. - _Philippe Deléham_, Dec 06 2011

%F a(n) = Sum_{k=0..n} A134309(n,k)*2^k = Sum_{k=0..n} A055372(n,k). - _Philippe Deléham_, Feb 04 2012

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

%F E.g.f.: 1/2 + exp(4*x)/2 = (Q(0)+1)/2, where Q(k) = 1 + 4*x/(2*k+1 - 2*x*(2*k+1)/(2*x + (k+1)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Apr 29 2013

%F a(n) = ceiling( 2^(2n-1) ). - _Wesley Ivan Hurt_, Jun 30 2013

%F G.f.: 1 + 2*x/(1 + x)*( 1 + 5*x/(1 + 4*x)*( 1 + 8*x/(1 + 7*x)*( 1 + 11*x/(1 + 10*x)*( 1 + ... )))). - _Peter Bala_, May 27 2017

%F Sum_{n>=0} 1/a(n) = 5/3. - _Amiram Eldar_, Aug 18 2022

%F Sum_{n>=0} a(n)*x^n/A000680(n) = E(x)^2 where E(x) = Sum_{n>=0} x^n/A000680(n). - _Geoffrey Critzer_, Apr 21 2023

%e G.f. = 1 + 2*x + 8*x^2 + 32*x^3 + 128*x^4 + 512*x^5 + 2048*x^6 + 8192*x^7 + ...

%p a:= n-> 2^max(0, (2*n-1)):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jul 20 2017

%t CoefficientList[Series[(1-2x)/(1-4x),{x,0,40}],x] (* or *)

%t Join[{1}, NestList[4 # &, 2, 40]] (* _Harvey P. Dale_, Apr 22 2011 *)

%o (PARI) a(n)=1<<max(0,2*n-1) \\ _Charles R Greathouse IV_, Jul 25 2011

%o (Magma) [(4^n+0^n)/2: n in [0..30]]; // _Vincenzo Librandi_, Jul 26 2011

%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 25); Coefficients(R!( (1-2*x)/(1-4*x))); // _Marius A. Burtea_, Jan 20 2020

%o (PARI) x='x+O('x^100); Vec((1-2*x)/(1-4*x)) \\ _Altug Alkan_, Dec 21 2015

%Y Row sums of triangle A136158.

%Y Cf. A000079, A081295, A009117, A016742, A054879, A092812, A121822. Essentially the same as A004171.

%K easy,nonn

%O 0,2

%A _Paul Barry_, Mar 17 2003