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

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,5

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

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

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

Example

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

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

Prog

(Magma) [2^n - 1 - n*(n+1)/2: n in [0..35]]; // Vincenzo Librandi, May 20 2011
(Haskell)
a002662 n = a002662_list !! n
a002662_list = map (sum . drop 3) a007318_tabl
-- Reinhard Zumkeller, Jun 20 2015
(PARI) a(n)=2^n-1-n*(n+1)/2 \\ Charles R Greathouse IV, Oct 11 2015
(Python)
def A002662(n): return (1<<n)-1-(n*(n+1)>>1) # Chai Wah Wu, Aug 29 2023

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.

Sequence in context: A187004 A255135 A055796 * A143962 A321959 A066634

Adjacent sequences: A002659 A002660 A002661 * A002663 A002664 A002665

Keyword

easy,nonn,nice

Author

N. J. A. Sloane

Status

approved