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

0, 0, 0, 1, 5, 16, 42, 99, 219, 466, 968, 1981, 4017, 8100, 16278, 32647, 65399, 130918, 261972, 524097, 1048365, 2096920, 4194050, 8388331, 16776915, 33554106, 67108512, 134217349, 268435049, 536870476, 1073741358, 2147483151, 4294966767, 8589934030

Offset: 0

Author

N. J. A. Sloane

Keywords

• easy
• nonn
• nice

Comments

Number of subsets with at least 3 elements of an n-element set.

For n>4, number of simple rank-(n-1) matroids over S_n.

Number of non-interval subsets of {1,2,3,...,n} (cf. A000124). - Jose Luis Arregui (arregui(AT)unizar.es), Jun 27 2006

The partial sums of the second diagonal of A008292 or third column of A123125. - Tom Copeland, Sep 09 2008

a(n) is the number of binary sequences of length n having at least three 0's. - Geoffrey Critzer, Feb 11 2009

Starting with "1" = eigensequence of a triangle with the tetrahedral numbers (1, 4, 10, 20, ...) as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010

a(n) is also the number of crossing set partitions of [n+1] with two blocks. - Peter Luschny, Apr 29 2011

The Kn24 sums, see A180662, of triangle A065941 equal the terms (doubled) of this sequence minus the three leading zeros. - Johannes W. Meijer, Aug 14 2011

From L. Edson Jeffery, Dec 28 2011: (Start)

Nonzero terms of this sequence can be found from the row sums of the fourth sub-triangle extracted from Pascal's triangle as indicated below by braces:

1;

1, 1;

1, 2, 1;

{1}, 3, 3, 1;

{1, 4}, 6, 4, 1;

{1, 5, 10}, 10, 5, 1;

{1, 6, 15, 20}, 15, 6, 1;

... (End)

Partial sums of A000295 (Eulerian Numbers, Column 2).

Second differences equal 2^(n-2) - 1, for n >= 4. - Richard R. Forberg, Jul 11 2013

Starting (0, 0, 1, 5, 16, ...) is the binomial transform of (0, 0, 1, 2, 2, 2, ...). - Gary W. Adamson, Jul 27 2015

a(n - 1) is the rank of the divisor class group of the moduli space of stable rational curves with n marked points, see Keel p. 550. - Harry Richman, Aug 10 2024

Examples

			a(4) = 5 is the number of crossing set partitions of {1,2,..,5}, card{13|245, 14|235, 24|135, 25|134, 35|124}. - _Peter Luschny_, Apr 29 2011
		

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• 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
• J. H. Conway and N. J. A. Sloane, Low-Dimensional Lattices VI: Voronoi Reduction of Three-Dimensional Lattices, Proc. Royal Soc. London, Series A, 436 (1992), 55-68. (See Table 1.)
• W. M. B. Dukes, On the number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.
• J. Eckhoff, Der Satz von Radon in konvexen Produktstrukturen II, Monat. f. Math., 73 (1969), 7-30.
• R. K. Guy, Letter to N. J. A. Sloane
• Sean Keel, Intersection theory of moduli space of stable n-pointed curves of genus zero, Trans. Amer. Math. Soc. 330 (1992), 545-574.
• Pablo Hueso Merino , The first problem from the 55th Spanish Mathematical Olympiad asks to find the value of a(2019) (see comment from Jose Luis Arregui).
• Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
• Sergey V. Muravyov, Liudmila I. Khudonogova, and Ekaterina Y. Emelyanova, Interval data fusion with preference aggregation, Measurement (2017), see page 5.
• 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
• Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Crossrefs

a(n) = A055248(n,3).

First differences are A000295.

Cf. A000079, A000124, A000217, A000225, A000247, A002663, A002664, A035038-A035042, A007318, A342352.

Cf. also A000290, A001045.

Programs

Haskell

a002662 n = a002662_list !! n
a002662_list = map (sum . drop 3) a007318_tabl
-- Reinhard Zumkeller, Jun 20 2015

Magma

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

Maple

A002662 := z**2/(2*z-1)/(z-1)**3; # conjectured by Simon Plouffe in his 1992 dissertation
A002662 := proc(n): 2^n - 1 - n*(n+1)/2 end: seq(A002662(n), n=0..33); # Johannes W. Meijer, Aug 14 2011

Mathematica

With[{nn=40},Join[{0},First[#]-1-Last[#]&/@Thread[{2^Range[nn], Accumulate[ Range[nn]]}]]] (* Harvey P. Dale, May 10 2012 *)
Table[2^n - Binomial[n, 2] - n - 1, {n, 1, 100}] (* Pablo Hueso Merino, Dec 17 2019 *)

PARI

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

Python

def A002662(n): return (1<>1) # Chai Wah Wu, Aug 29 2023

Formula

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

a(n) = Sum_{k=0..n} binomial(n,k+3) = Sum_{k=3..n} binomial(n,k). - Paul Barry, Jul 30 2004

a(n+1) = 2*a(n) + binomial(n,2). - Paul Barry, Aug 23 2004

(1, 5, 16, 42, 99, ...) = binomial transform of (1, 4, 7, 8, 8, 8, ...). - Gary W. Adamson, Sep 30 2007

E.g.f.: exp(x)*(exp(x)-x^2/2-x-1). - Geoffrey Critzer, Feb 11 2009

a(n) = n - 2 + 3*a(n-1) - 2*a(n-2), for n >= 2. - Richard R. Forberg, Jul 11 2013

For n>1, a(n) = (1/4)*Sum_{k=1..n-2} 2^k*(n-k-1)*(n-k). For example, (1/4)*(2^1*(4*5) + 2^2*(3*4) + 2^3*(2*3) + 2^4*(1*2)) = 168/4 = 42. - J. M. Bergot, May 27 2014 [edited by Danny Rorabaugh, Apr 19 2015]

Convolution of A001045 and (A000290 shifted by one place). - Oboifeng Dira, Aug 16 2016

a(n) = Sum_{k=1..n-2} Sum_{i=1..n} (n-k-1) * C(k,i). - Wesley Ivan Hurt, Sep 19 2017

a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n > 3. - Chai Wah Wu, Apr 03 2021

a(n) = a(n-1) + 1 + A000247(n-1). - Harry Richman, Aug 13 2024