A152947 a(n) = 1 + (n-2)*(n-1)/2.

1, 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, 704, 742, 781, 821, 862, 904, 947, 991, 1036, 1082, 1129, 1177, 1226, 1276, 1327, 1379

Offset: 1

Author

Vladimir Joseph Stephan Orlovsky, Dec 15 2008

Keywords

• nonn
• easy

Comments

The sequence is the sum of upward sloping terms in an infinite lower triangle with 1's in the leftmost column and the odd integers in all other columns. - Gary W. Adamson, Jan 29 2014

For n > 1, if Kruskal's algorithm is run on a weighted connected graph of n nodes, then a(n) is the maximum number of iterations required to reach a spanning tree. - Eric M. Schmidt, Jun 04 2016

It can be observed that A152947/A000079, whose reduced numerators are A213671, is identical to its inverse binomial transform (except for signs); this shows that it is an "autosequence" (more precisely, an autosequence of the second kind). - Jean-François Alcover (this remark is due to Paul Curtz), Jun 20 2016

Harnack's theorem (1876) states that the number of components of a plane algebraic curve of order n is at most a(n) and that this number can be achieved. For example, the zero set of a quadratic has at most 1 component (e.g. a circle); a cubic elliptic curve has at most 2 components. The number of topological arrangements (Hilbert's 16th problem) is only known for a few values of n. For quartics, a(4)=4 and there are 6 topological arrangements: 0 to 4 unnested ovals or 2 nested ovals. - Robert McLachlan, Aug 19 2024

a(n) is the number of permutations (cyclic or not) of length (n-1) that avoid both patterns 123 and 231. a(5) = 7: 1432, 2143, 3214, 4132, 4213, 4312, 4321. - Alois P. Heinz, Nov 20 2024

Links

• Shawn A. Broyles, Table of n, a(n) for n = 1..1000
• Christian Bean, Bjarki Gudmundsson, and Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.
• Murat Ersen Berberler, Onur Ugurlu, and Gozde Kizilates, On a Subroutine for Covering Zeros in Hungarian Algorithm, 2012, see section 5.1 on page 92.
• Miklos Bona, Michael Cory, Cyclic Permutations Avoiding Pairs of Patterns of Length Three, arXiv:1805.05196 [math.CO], 2018.
• Hayat Cheballah, Samuele Giraudo, and Rémi Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
• Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
• Loïc Foissy, The antipode of of [sic] a Com-PreLie Hopf algebra, arXiv:2406.01120 [math.CO], 2024. See p. 9.
• D. A. Gudkov, The topology of real projective algebraic varieties, Russ. Math. Surv. 29 (1974), 1-79.
• Lara Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012.
• Franck Ramaharo, Statistics on some classes of knot shadows, arXiv:1802.07701 [math.CO], 2018.
• Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A000124, A000217, A226985.

Programs

Magma

[1+(n-2)*(n-1)/2: n in [1..60]]; // Klaus Brockhaus, Nov 28 2010

Maple

A152947:=n->1+(n-2)*(n-1)/2: seq(A152947(n), n=1..100); # Wesley Ivan Hurt, Jun 20 2016

Mathematica

Table[1 + (n^2 - 3n + 2)/2, {n, 50}] (* Alonso del Arte, Jan 30 2014 *)

PARI

a(n)=1+(n-2)*(n-1)/2 \\ Charles R Greathouse IV, Oct 07 2015

Sage

[1+binomial(n,2) for n in range(0, 54)] # Zerinvary Lajos, Mar 12 2009

Formula

a(n) = 1 + A000217(n-2) = A000124(n-2), n > 1. - R. J. Mathar, Jan 03 2009

a(n) = a(n-1) + n - 2 for n>1, a(1) = 1. - Vincenzo Librandi, Nov 26 2010

G.f.: -x*(1-2*x+2*x^2)/(x-1)^3. - R. J. Mathar, Nov 28 2010

From Ilya Gutkovskiy, Jun 04 2016: (Start)

E.g.f.: (4 - 2*x + x^2)*exp(x)/2 - 2.

Sum_{n>=1} 1/a(n) = 2*Pi*tanh(sqrt(7)*Pi/2)/sqrt(7) + 1 = A226985 + 1. (End)

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>3. - Wesley Ivan Hurt, Jun 20 2016

Sum_{n>=1} (-1)^(n+1)/a(n) = 1 - A228918. - Amiram Eldar, Jan 08 2023