login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002662 a(n) = 2^n - 1 - n*(n+1)/2.
(Formerly M3866 N1585)
18
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 (list; graph; refs; listen; history; text; internal format)
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

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

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

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

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

a=1; lst={}; s1=s2=s3=0; Do[s1+=a; s2+=s1; s3+=s2; AppendTo[lst, s3]; a=a*2, {n, 6!}]; lst (* Vladimir Joseph Stephan Orlovsky, Jan 10 2009 *)

With[{nn=40}, Join[{0}, First[#]-1-Last[#]&/@Thread[{2^Range[nn], Accumulate[ Range[nn]]}]]] (* Harvey P. Dale, May 10 2012 *)

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

CROSSREFS

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

Cf. A000079, A000225, A000295, A002663, A002664, A035038-A035042, A007318.

Cf. also A000290, A001045.

Sequence in context: A187004 A255135 A055796 * A143962 A066634 A241794

Adjacent sequences:  A002659 A002660 A002661 * A002663 A002664 A002665

KEYWORD

easy,nonn,nice

AUTHOR

N. J. A. Sloane, Apr 30 1991

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 22 06:11 EST 2017. Contains 295076 sequences.