login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014206 a(n) = n^2 + n + 2. 33
2, 4, 8, 14, 22, 32, 44, 58, 74, 92, 112, 134, 158, 184, 212, 242, 274, 308, 344, 382, 422, 464, 508, 554, 602, 652, 704, 758, 814, 872, 932, 994, 1058, 1124, 1192, 1262, 1334, 1408, 1484, 1562, 1642, 1724, 1808, 1894, 1982, 2072, 2164, 2258, 2354, 2452, 2552 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

Draw n + 1 circles in the plane; sequence gives maximal number of regions into which the plane is divided (a(n) = A002061(n+1) + 1 for n >= 0). Cf. A051890.

Number of binary (zero-one) bitonic sequences of length n + 1. - Johan Gade (jgade(AT)diku.dk), Oct 15 2003

Also the number of permutations of n + 1 which avoid the patterns 213, 312, 13452 and 34521. Example: the permutations of 4 which avoid 213, 312 (and implicitly 13452 and 34521) are 1234, 1243, 1342, 1432, 2341, 2431, 3421, 4321. - Mike Zabrocki, Jul 09 2007

If Y is a 2-subset of an n-set X then, for n >= 3, a(n-3) is equal to the number of (n-3)-subsets and (n-1)-subsets of X having exactly one element in common with Y. - Milan Janjic, Dec 28 2007

With a different offset, competition number of the complete tripartite graph K_{n, n, n}. [Kim, Sano] - Jonathan Vos Post, May 14 2009. Cf. A160450, A160457.

A related sequence is A241119. - Avi Friedlich, Apr 28 2015

From Avi Friedlich, Apr 28 2015: (Start)

This sequence, which also represents the number of Hamiltonian paths in K_2 X P_n (A200182), may be represented by interlacing recursive polynomials in arithmetic progression (discriminant =-63). For example:

a(3*k-3) = 9*k^2 - 15*k + 8,

a(3*k-2) = 9*k^2 - 9*k  + 4,

a(3*k-1) = 9*k^2 - 3*k  + 2,

a(3*k)   = 3*(k+1)^2  - 1. (End)

REFERENCES

K. E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, pp. 307-314 (1968). [for bitonic sequences]

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 73, Problem 3.

T. H. Cormen, C. E. Leiserson and R. L. Rivest: Introduction to Algorithms. MIT Press / McGraw-Hill (1990) [for bitonic sequences]

Indiana School Mathematics Journal, vol. 14, no. 4, 1979, p. 4.

S.-R. Kim and Y. Sano: The competition numbers of complete tripartite graphs, Discrete Appl. Math., 156 (2008) 3522-3524.

D. E. Knuth, The art of computer programming, vol3: Sorting and Searching, Addison-Wesley (1973) [for bitonic sequences]

J. D. E. Konhauser et al., Which Way Did the Bicycle Go?, MAA 1996, p. 177.

Derrick Niederman, Number Freak, From 1 to 200 The Hidden Language of Numbers Revealed, A Perigee Book, NY, 2009, p. 83.

A. M. Yaglom and I. M. Yaglom: Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #44 (First published: San Francisco: Holden-Day, Inc., 1964)

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..1000

A. Burstein, S. Kitaev, T. Mansour, Partially ordered patterns and their combinatorial interpretations, PU. M. A. Vol. 19 (2008), No. 2-3, pp. 27-38.

Guo-Niu Han, Enumeration of Standard Puzzles [Broken link]

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

S.-R. Kim and Y. Sano, The competition numbers of complete tripartite graphs, Discrete Appl. Math., 156 (2008) 3522-3524.

Hans Werner Lang, Bitonic sequences

Jean-Christoph Novelli and Anne Schilling, The Forgotten Monoid, arXiv 0706.2996 [math.CO], 2007.

Parabola, vol. 24, no. 1, 1988, p. 22, Problem #Q736.

Yoshio Sano, The competition numbers of regular polyhedra, May 12, 2009.

Jeffrey Shallit, mentions this function in a blog post as the solution for small n to a problem involving boolean matrices whose values for larger n are unknown.

Eric Weisstein's World of Mathematics, Plane Division by Circles

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

FORMULA

G.f.: 2*x*(x^2 - x + 1)/(1 - x)^3.

n hyperspheres divide R^k into at most C(n-1, k) + Sum_{i = 0..k} C(n, i) regions.

a(n) = A002061(n+1) + 1 for n >= 0. - Rick L. Shepherd, May 30 2005

((binomial(n+3, n+1) - binomial(n+1, n))*(binomial(n+3, n+2) - binomial(n+1, n)). - Zerinvary Lajos, May 12 2006

Equals binomial transform of [2, 2, 2, 0, 0, 0,...]. - Gary W. Adamson, Jun 18 2008

a(n) = A003682(n+1), n > 0. - R. J. Mathar, Oct 28 2008

a(n) = a(n-1) + 2*n  (with a(0) = 2). - Vincenzo Librandi, Nov 20 2010

a(0) = 2, a(1) = 4, a(2) = 8, a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). -  Harvey P. Dale, May 14 2011

a(n + 1) = n^2 + 3*n + 4. - Alonso del Arte, Apr 12 2015

a(n) = Sum_{i=n-2..n+2} i*(i+1)/5. - Bruno Berselli, Oct 20 2016

EXAMPLE

a(0) = 0^2 + 0 + 2 = 2.

a(1) = 1^2 + 1 + 2 = 4.

a(2) = 2^2 + 2 + 2 = 8.

a(6) = 4*5/5 + 5*6/5 + 6*7/5 + 7*8/5 + 8*9/5 = 44. - Bruno Berselli, Oct 20 2016

MAPLE

A014206 := n->n^2+n+2;

with (combinat):seq(fibonacci(3, n)+n+1, n=0..50); # Zerinvary Lajos, Jun 07 2008

MATHEMATICA

Table[n^2 + n + 2, {n, 0, 50}] (* Stefan Steinerberger, Apr 08 2006 *)

LinearRecurrence[{3, -3, 1}, {2, 4, 8}, 50] (* Harvey P. Dale, May 14 2011 *)

CoefficientList[Series[2 (x^2 - x + 1)/(1 - x)^3, {x, 0, 50}], x] (* Vincenzo Librandi, Apr 29 2015 *)

PROG

(PARI) a(n)=n^2+n+2 \\ Charles R Greathouse IV, Jul 31 2011

(PARI) x='x+O('x^100); Vec(2*x*(x^2-x+1)/(1-x)^3) \\ Altug Alkan, Nov 01 2015

(MAGMA) [n^2+n+2: n in [0..50]]; // Vincenzo Librandi, Apr 29 2015

CROSSREFS

Cf. A014206 (dim 2), A046127 (dim 3), A059173 (dim 4), A059174 (dim 5). A row of A059250.

Cf. A000124, A051890, A002522, A241119. Also A033547 is partial sums of A014206.

Cf. A002061 (central polygonal numbers).

Sequence in context: A194694 A194692 A155506 * A025196 A084626 A090533

Adjacent sequences:  A014203 A014204 A014205 * A014207 A014208 A014209

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Stefan Steinerberger, Apr 08 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 10 21:23 EST 2016. Contains 279011 sequences.