A005183 - OEIS

%I M1434 #126 May 30 2026 16:39:47

%S 1,2,5,13,33,81,193,449,1025,2305,5121,11265,24577,53249,114689,

%T 245761,524289,1114113,2359297,4980737,10485761,22020097,46137345,

%U 96468993,201326593,419430401,872415233,1811939329,3758096385,7784628225,16106127361,33285996545

%N a(n) = n*2^(n-1) + 1.

%C a(n-1) is the number of permutations of length n which avoid the patterns 132, 4312. - _Lara Pudwell_, Jan 21 2006

%C Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) <= e(j) >= e(k) and e(i) != e(k). [Martinez and Savage, 2.11] - _Eric M. Schmidt_, Jul 17 2017

%C Indices of records in A066099. Also, indices of "cusps" in the graph of A030303 giving positions of 1's in the binary Champernowne word A030190. - _M. F. Hasler_, Oct 12 2020

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

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

%H Stephan Baier and Pallab Kanti Dey, <a href="https://arxiv.org/abs/1905.13003">Prime powers dividing products of consecutive integer values of x^2^n + 1</a>, arXiv:1905.13003 [math.NT], 2019. See p. 7.

%H Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, <a href="https://arxiv.org/abs/2405.05357">Flattened Catalan Words</a>, arXiv:2405.05357 [math.CO], 2024. See p. 16.

%H Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/1803.06706">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, arXiv:1803.06706 [math.CO], 2018.

%H Andrew M. Baxter and Lara K. Pudwell, <a href="https://doi.org/10.37236/4479">Ascent sequences avoiding pairs of patterns</a>, Elect. J. Comb. 22(1) (2015), #P1.58.

%H Christian Bean, Bjarki Gudmundsson, and Henning Ulfarsson, <a href="https://arxiv.org/abs/1705.04109">Automatic discovery of structural rules of permutation classes</a>, arXiv:1705.04109 [math.CO], 2017.

%H Richard K. Guy, <a href="https://www.jstor.org/stable/2691503">The Second Strong Law of Small Numbers</a>, Math. Mag 63(1) (1990), 3-20.

%H Richard K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag, 63(1) (1990), 3-20. [Annotated scanned copy]

%H Richard K. Guy and N. J. A. Sloane, <a href="/A005180/a005180.pdf">Correspondence</a>, 1988.

%H Vít Jelínek, Toufik Mansour, and Mark Shattuck, <a href="https://doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Adv. Appl. Math. 50(2) (2013), 292-326. See Example 4.16, H_{1223} and Example 4.17 L_{1232} and propositions 4.20 and 4.22, all shifted with an additional leading a(0)=1.

%H Qi Liu, Sergey Kitaev, and Philip B. Zhang, <a href="https://arxiv.org/abs/2604.06735">Simultaneous avoidance of length-4 patterns in ascent sequences</a>, arXiv:2604.06735 [math.CO], 2026. See p. 4 (Table 1).

%H Shuzhen Lv and Sergey Kitaev, <a href="https://arxiv.org/abs/2509.12726">Stoimenow matchings avoiding multiple Catalan patterns simultaneously</a>, arXiv:2509.12726 [math.CO], 2025. See pp. 3, 10.

%H Toufik Mansour and Mark Shattuck, <a href="https://arxiv.org/abs/2507.17947">On ascent sequences avoiding 021 and a pattern of length four</a>, arXiv:2507.17947 [math.CO], 2025. See p. 11.

%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.

%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 Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/webbook/bookmain.html">Systematic Studies in Pattern Avoidance</a>, 2005.

%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, 2015 Joint Mathematics Meetings, AMS Special Session on Enumerative Combinatorics, January 11, 2015.

%H Lara Pudwell and Andrew Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, Permutation Patterns 2014, East Tennessee State University, July 7, 2014.

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

%F Main diagonal of the array defined by T(0, j)=j+1 j>=0, T(i, 0)=i+1 i>=0, T(i, j)=T(i-1, j-1)+T(i-1, j)-1. - _Benoit Cloitre_, Jun 17 2003

%F G.f.: (1 -3*x +3*x^2)/((1-x)*(1-2*x)^2). - _Lara Pudwell_, Jan 21 2006

%F E.g.f.: exp(x) +x*exp(2*x). - _Joerg Arndt_, May 22 2013

%F Binomial transform of A028310. a(n) = 1 + Sum{k=0..n} C(n, k)*k = 1 + A001787(n). - _Paul Barry_, Jul 21 2003

%F a(n) = Sum_{k=0..2^n} A000120(k) = A000788(2^n). - _Benoit Cloitre_, Sep 25 2003

%F Row sums of triangle A134399. - _Gary W. Adamson_, Oct 23 2007

%F a(n) = A000788(A000079(n)). - _Reinhard Zumkeller_, Mar 04 2010

%F a(n) = 2*a(n-1) +2^(n-1) -1 (with a(0)=1). - _Vincenzo Librandi_, Dec 31 2010

%p A005183 := (1-3*z+3*z**2)/(1-z)/(1-2*z)**2; # Generating function conjectured by _Simon Plouffe_ in his 1992 dissertation.

%t Table[(n+1)*2^n+1,{n,1,30}] (* _Alexander Adamchuk_, Sep 09 2006 *)

%t LinearRecurrence[{5,-8,4},{1,2,5},30] (* _Harvey P. Dale_, Jul 29 2015 *)

%o (PARI) a(n)=n*2^(n-1)+1 \\ _Charles R Greathouse IV_, Sep 24 2015

%o (Magma) [n*2^(n-1)+1: n in [0..35]]; // _Vincenzo Librandi_, May 14 2017

%o (SageMath) [2^(n-1)*n+1 for n in (0..35)] # _G. C. Greubel_, May 31 2019

%Y Cf. A000079, A000120, A000788, A028310, A030190, A030303, A066099, A134399.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, _R. K. Guy_

%E More terms from _Lara Pudwell_, Jan 21 2006

%E Edited by _N. J. A. Sloane_ at the suggestion of Jim Propp, Jul 14 2007