



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 (zeroone) 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 2subset of an nset X then, for n>=3, a(n3) is equal to the number of (n3)subsets and (n1)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.


REFERENCES

K. E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, pp. 307314 (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 / McGrawHill (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) 35223524.
D. E. Knuth, The art of computer programming, vol3: Sorting and Searching, AddisonWesley (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. [From Robert G. Wilson v, May 21 2010]
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: HoldenDay, Inc., 1964)


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..1000
GuoNiu Han, Enumeration of Standard Puzzles
GuoNiu Han, Enumeration of Standard Puzzles [Cached copy]
H. W. Lang, Bitonic sequences
J. C. Novelli and A. Schilling, The Forgotten Monoid, arXiv 0706.2996
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 sequences related to linear recurrences with constant coefficients, signature (3,3,1).


FORMULA

G.f.: 2*x*(x^2x+1)/(1x)^3.
n hyperspheres divide R^k into at most C(n1, 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(n1)+2*n (with a(0)=2) [Vincenzo Librandi, Nov 20 2010]
a(0)=2, a(1)=4, a(2)=8, a(n)=3*a(n1)3*a(n2)+a(n3) [Harvey P. Dale, May 14 2011]


EXAMPLE

a(0) = 0^2+0+2 = 2, a(1) = 1^2+1+2 =4, a(2) = 2^2+2+2 = 8, etc.


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 *)


PROG

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


CROSSREFS

Cf. A014206 (dim 2), A046127 (dim 3), A059173 (dim 4), A059174 (dim 5). A row of A059250.
Cf. A000124, A051890. Also A033547=partial sums of A014206.
Cf. A002061 (Central polygonal numbers).
Cf. A002522, A051890.
Sequence in context: A194694 A194692 A155506 * A025196 A084626 A090533
Adjacent sequences: A014203 A014204 A014205 * A014207 A014208 A014209


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane.


EXTENSIONS

More terms from Stefan Steinerberger, Apr 08 2006


STATUS

approved



