

A014206


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


44



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.
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*k3) = 9*k^2  15*k + 8,
a(3*k2) = 9*k^2  9*k + 4,
a(3*k1) = 9*k^2  3*k + 2,
a(3*k) = 3*(k+1)^2  1. (End)
a(n+1) is the area of a triangle with vertices at (n+3, n+4), ((n1)*n/2, n*(n+1)/2),((n+1)^2, (n+2)^2) with n >= 1.  J. M. Bergot, Feb 02 2018
For prime p and any integer k, k^a(p1) == k^2 (mod p^2).  Jianing Song, Apr 20 2019
For n >= 1, a(n1) is the number of solutions x in the interval 0 <= x <= n of the equation x^2  [x^2] = (x  [x])^2, where [x] = floor(x). For n = 3, the a(2) = 8 solutions in the interval [0, 3] are 0, 1, 3/2, 2, 9/4, 5/2, 11/4 and 3.
This is a variant of the 4th problem proposed during the 20th British Mathematical Olympiad in 1984 (see A002061). The interval [1, n] of the Olympiad problem becomes here [0, n], and only the new solution x = 0 is added. (End)


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.
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.
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



FORMULA

G.f.: 2*(x^2  x + 1)/(1  x)^3.
n hyperspheres divide R^k into at most C(n1, k) + Sum_{i = 0..k} C(n, i) regions.
Equals binomial transform of [2, 2, 2, 0, 0, 0, ...].  Gary W. Adamson, Jun 18 2008
a(0) = 2, a(1) = 4, a(2) = 8, a(n) = 3*a(n1)  3*a(n2) + a(n3) for n >= 3.  Harvey P. Dale, May 14 2011
Sum_{n>=0} 1/a(n) = Pi*tanh(Pi*sqrt(7)/2)/sqrt(7).  Amiram Eldar, Jan 09 2021
Product_{n>=0} (1 + 1/a(n)) = cosh(sqrt(11)*Pi/2)*sech(sqrt(7)*Pi/2).
Product_{n>=0} (1  1/a(n)) = cosh(sqrt(3)*Pi/2)*sech(sqrt(7)*Pi/2). (End)


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



MATHEMATICA

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) x='x+O('x^100); Vec(2*x*(x^2x+1)/(1x)^3) \\ Altug Alkan, Nov 01 2015


CROSSREFS

Cf. A002061 (central polygonal numbers).


KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



