A005183 - OEIS

%I M1434 #110 May 15 2024 10:39:33

%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 A. M. Baxter and L. K. Pudwell, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p58">Ascent sequences avoiding pairs of patterns</a>, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015) Paper #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 R. K. Guy, <a href="http://www.jstor.org/stable/2691503">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20.

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

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

%H V. Jelinek, T. Mansour, and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Adv. Appl. Math. 50 (2) (2013) 292-326, 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 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 L. 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 L. Pudwell and A. 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 (Sage) [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