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

1, 2, 5, 13, 33, 81, 193, 449, 1025, 2305, 5121, 11265, 24577, 53249, 114689, 245761, 524289, 1114113, 2359297, 4980737, 10485761, 22020097, 46137345, 96468993, 201326593, 419430401, 872415233, 1811939329, 3758096385, 7784628225, 16106127361, 33285996545

Offset: 0

Author

N. J. A. Sloane, R. K. Guy

Keywords

• nonn
• easy

Comments

a(n-1) is the number of permutations of length n which avoid the patterns 132, 4312. - Lara Pudwell, Jan 21 2006

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

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

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Stephan Baier and Pallab Kanti Dey, Prime powers dividing products of consecutive integer values of x^2^n + 1, arXiv:1905.13003 [math.NT], 2019. See p. 7.
• Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, Flattened Catalan Words, arXiv:2405.05357 [math.CO], 2024. See p. 16.
• Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
• Andrew M. Baxter and Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015) Paper #P1.58.
• Christian Bean, Bjarki Gudmundsson, and Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.
• R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20.
• R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
• R. K. Guy and N. J. A. Sloane, Correspondence, 1988.
• Vít Jelínek, Toufik Mansour, and Mark Shattuck, On multiple pattern avoiding set partitions, 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.
• Toufik Mansour and Mark Shattuck, On ascent sequences avoiding 021 and a pattern of length four, arXiv:2507.17947 [math.CO], 2025. See p. 11.
• Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
• Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015 Joint Mathematics Meetings, AMS Special Session on Enumerative Combinatorics, January 11, 2015.
• Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, Permutation Patterns 2014, East Tennessee State University, July 7, 2014.
• Index entries for linear recurrences with constant coefficients, signature (5,-8,4).

Crossrefs

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

Programs

Magma

[n*2^(n-1)+1: n in [0..35]]; // Vincenzo Librandi, May 14 2017

Maple

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

Mathematica

Table[(n+1)*2^n+1,{n,1,30}] (* Alexander Adamchuk, Sep 09 2006 *)
LinearRecurrence[{5,-8,4},{1,2,5},30] (* Harvey P. Dale, Jul 29 2015 *)

PARI

a(n)=n*2^(n-1)+1 \\ Charles R Greathouse IV, Sep 24 2015

Sage

[2^(n-1)*n+1 for n in (0..35)] # G. C. Greubel, May 31 2019

Formula

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

G.f.: (1 -3*x +3*x^2)/((1-x)*(1-2*x)^2). - Lara Pudwell, Jan 21 2006

E.g.f.: exp(x) +x*exp(2*x). - Joerg Arndt, May 22 2013

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

a(n) = Sum_{k=0..2^n} A000120(k) = A000788(2^n). - Benoit Cloitre, Sep 25 2003

Row sums of triangle A134399. - Gary W. Adamson, Oct 23 2007

a(n) = A000788(A000079(n)). - Reinhard Zumkeller, Mar 04 2010

a(n) = 2*a(n-1) +2^(n-1) -1 (with a(0)=1). - Vincenzo Librandi, Dec 31 2010

Extensions

More terms from Lara Pudwell, Jan 21 2006

Edited by N. J. A. Sloane at the suggestion of Jim Propp, Jul 14 2007