A005803 - OEIS

%I M1838 #115 Sep 08 2022 08:44:34

%S 1,0,0,2,8,22,52,114,240,494,1004,2026,4072,8166,16356,32738,65504,

%T 131038,262108,524250,1048536,2097110,4194260,8388562,16777168,

%U 33554382,67108812,134217674,268435400,536870854,1073741764,2147483586

%N Second-order Eulerian numbers: a(n) = 2^n - 2*n.

%C Starting with n=2, a(n) is the second-order Eulerian number <<n-1,1>> (see A008517).

%C Also, number of 3 X n binary matrices avoiding simultaneously the right-angled numbered polyomino patterns (ranpp) (00;1), (01;0) and (01;1). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1<i2, j1<j2 and these elements are in same relative order as those in the triple (x,y,z). - _Sergey Kitaev_, Nov 11 2004

%C This is the number of target DNA sequences of the correct length present after each successive cycle of the Polymerase Chain Reaction (PCR). The first two cycles produce 0 target sequences, there are 2 target sequences present after the third cycle, then 8 after the fourth cycle, and so forth. - _A. Timothy Royappa_, Jun 16 2012

%C a(n+2) = the row sums of A222403. - _J. M. Bergot_, Apr 04 2018

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A005803/b005803.txt">Table of n, a(n) for n=0..500</a>

%H S. Bilotta, E. Grazzini, and E. Pergola, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Grazzini/graz3.html">Enumeration of Two Particular Sets of Minimal Permutations</a>, J. Int. Seq. 18 (2015) 15.10.2.

%H I. Gessel and R. P. Stanley, <a href="https://doi.org/10.1016/0097-3165(78)90042-0">Stirling polynomials</a>, J. Combin. Theory, A 24 (1978), 24-33.

%H Jim Haglund and Mirko Visontai, <a href="http://hans.math.upenn.edu/~jhaglund/preprints/es-final.pdf">Stable multivariate Eulerian polynomials and generalized Stirling permutations</a>.

%H Sergey Kitaev, <a href="http://www.emis.de/journals/INTEGERS/papers/e21/e21.Abstract.html">On multi-avoidance of right angled numbered polyomino patterns</a>, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.

%H Sergey Kitaev, <a href="https://web.archive.org/web/20130625171839/http://www.ms.uky.edu/~math/MAreport/4-ser.ps">On multi-avoidance of right angled numbered polyomino patterns</a>, University of Kentucky Research Reports (2004).

%H Sandi Klavžar, Uroš Milutinović and Ciril Petr, <a href="http://dx.doi.org/10.1016/j.exmath.2005.05.003">Hanoi graphs and some classical numbers</a>, Expo. Math. 23 (2005), no. 4, 371-378.

%H James McClung, <a href="https://web.wpi.edu/Pubs/E-project/Available/E-project-051620-220950/unrestricted/Constructions_and_Applications_of_W-States.pdf">Constructions and Applications of W-States</a>, Bachelor Thesis, Worcester Polytechnic Institute (2020).

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.

%H Sam Spiro, <a href="https://arxiv.org/abs/1810.00993">Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic</a>, arXiv preprint arXiv:1810.00993 [math.CO], 2018 (A000246); Discrete Math, 343 (2020), article 111869.

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

%F G.f.: 1 + 2*x^3/((1-x)^2*(1-2*x)). a(n) = A008517(n-1, 2). - _Michael Somos_, Oct 13 2002

%F Equals binomial transform of [1, -1, 1, 1, 1, ...]. - _Gary W. Adamson_, Jul 14 2008

%F a(0) = 1 and a(n) = Sum_{k=0..n-3} ((-1)^(n+k+1)*binomial(2*n-1,k)*stirling1(2*n-k-3,n-k-2)), n=>1. - _Johannes W. Meijer_, Oct 16 2009

%F a(0)=1, a(1)=0, a(2)=0, a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3). - _Harvey P. Dale_, May 21 2011

%F a(n) = A000225(n+1) - A081494(n+1), n > 1. In other words, a(n) equals the sum of the elements in a Pascal triangle of depth n+1 minus the sum of the elements on its perimeter. - _Ivan N. Ianakiev_, Jun 01 2014

%F a(n) = A165900(n-1) + Sum_{i=0..n-1} a(i), for n > 0. - _Ivan N. Ianakiev_, Nov 24 2014

%F a(n) = A000225(n) - A005408(n-1). - _Miquel Cerda_, Nov 25 2016

%F E.g.f.: exp(x)*(exp(x) - 2*x). - _Ilya Gutkovskiy_, Nov 25 2016

%e G.f. = 1 + 2*x^3 + 8*x^4 + 22*x^5 + 52*x^6 + 114*x^7 + 240*x^8 + 494*x^9 + ...

%p A005803:=-2*z/(2*z-1)/(z-1)**2; # conjectured by _Simon Plouffe_ in his 1992 dissertation. Gives sequence except for three leading terms

%t Table[2^n-2n,{n,0,50}] (* or *) LinearRecurrence[{4,-5,2},{1,0,0},51] (* _Harvey P. Dale_, May 21 2011 *)

%o (PARI) {a(n) = if( n<0, 0, 2^n - 2*n)}; /* _Michael Somos_, Oct 13 2002 */

%o (Haskell)

%o a005803 n = 2 ^ n - 2 * n

%o a005803_list = 1 : f 1 [0, 2 ..] where

%o    f x (z:zs@(z':_)) = y : f y zs  where y = (x + z) * 2 - z'

%o -- _Reinhard Zumkeller_, Jan 19 2014

%o (Magma) [2^n-2*n: n in [0..30]]; // _Wesley Ivan Hurt_, Jun 04 2014

%Y Equivalent to second column of A008517.

%Y a(n) = A070313 + 1 = A052515 + 2. Bisection of A077866.

%Y Equals for n =>3 the third right hand column of A163936.

%Y Cf. A000918 (first differences).

%Y Cf. A000079, A000325, A005843, A130102.

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_, _Simon Plouffe_