A002662 - OEIS

%I M3866 N1585 #188 Aug 17 2024 23:02:54

%S 0,0,0,1,5,16,42,99,219,466,968,1981,4017,8100,16278,32647,65399,

%T 130918,261972,524097,1048365,2096920,4194050,8388331,16776915,

%U 33554106,67108512,134217349,268435049,536870476,1073741358,2147483151,4294966767,8589934030

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

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

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

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

%C The partial sums of the second diagonal of A008292 or third column of A123125. - _Tom Copeland_, Sep 09 2008

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

%C 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

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

%C 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

%C From _L. Edson Jeffery_, Dec 28 2011: (Start)

%C 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:

%C                      1;

%C                   1,    1;

%C                1,    2,    1;

%C            {1},   3,    3,    1;

%C         {1,    4},   6,    4,    1;

%C      {1,    5,   10},  10,    5,    1;

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

%C   ... (End)

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

%C Second differences equal 2^(n-2) - 1, for n >= 4. - _Richard R. Forberg_, Jul 11 2013

%C Starting (0, 0, 1, 5, 16, ...) is the binomial transform of (0, 0, 1, 2, 2, 2, ...). - _Gary W. Adamson_, Jul 27 2015

%C 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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A002662/b002662.txt">Table of n, a(n) for n = 0..1000</a>

%H J. H. Conway and N. J. A. Sloane, <a href="http://www.jstor.org/stable/52019">Low-Dimensional Lattices VI: Voronoi Reduction of Three-Dimensional Lattices</a>, Proc. Royal Soc. London, Series A, 436 (1992), 55-68. (See Table 1.)

%H W. M. B. Dukes, <a href="https://arxiv.org/abs/math/0411557">On the number of matroids on a finite set</a>, arXiv:math/0411557 [math.CO], 2004.

%H J. Eckhoff, <a href="http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002476398">Der Satz von Radon in konvexen Produktstrukturen II</a>, Monat. f. Math., 73 (1969), 7-30.

%H R. K. Guy, <a href="/A000346/a000346.pdf">Letter to N. J. A. Sloane</a>

%H Sean Keel, <a href="http://dx.doi.org/10.1090/S0002-9947-1992-1034665-0">Intersection theory of moduli space of stable n-pointed curves of genus zero</a>, Trans. Amer. Math. Soc. 330 (1992), 545-574.

%H Pablo Hueso Merino <a href="http://www.olimpiadamatematica.es/platea.pntic.mec.es/_csanchez/olimp2019.htm"></a>, The first problem from the 55th Spanish Mathematical Olympiad asks to find the value of a(2019) (see comment from Jose Luis Arregui).

%H Ângela Mestre and José Agapito, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL22/Mestre/mestre2.html">Square Matrices Generated by Sequences of Riordan Arrays</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.

%H Sergey V. Muravyov, Liudmila I. Khudonogova, and Ekaterina Y. Emelyanova, <a href="https://doi.org/10.1016/j.measurement.2017.08.045"> Interval data fusion with preference aggregation</a>, Measurement (2017), see page 5.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-9,7,-2).

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

%F a(n) = Sum_{k=0..n} binomial(n,k+3) = Sum_{k=3..n} binomial(n,k). - _Paul Barry_, Jul 30 2004

%F a(n+1) = 2*a(n) + binomial(n,2). - _Paul Barry_, Aug 23 2004

%F (1, 5, 16, 42, 99, ...) = binomial transform of (1, 4, 7, 8, 8, 8, ...). - _Gary W. Adamson_, Sep 30 2007

%F E.g.f.: exp(x)*(exp(x)-x^2/2-x-1). - _Geoffrey Critzer_, Feb 11 2009

%F a(n) = n - 2 + 3*a(n-1) - 2*a(n-2), for n >= 2. - _Richard R. Forberg_, Jul 11 2013

%F 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]

%F Convolution of A001045 and (A000290 shifted by one place). - _Oboifeng Dira_,  Aug 16 2016

%F a(n) = Sum_{k=1..n-2} Sum_{i=1..n} (n-k-1) * C(k,i). - _Wesley Ivan Hurt_, Sep 19 2017

%F 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

%F a(n) = a(n-1) + 1 + A000247(n-1). - _Harry Richman_, Aug 13 2024

%e 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

%p A002662 := z**2/(2*z-1)/(z-1)**3; # conjectured by _Simon Plouffe_ in his 1992 dissertation

%p A002662 := proc(n): 2^n - 1 - n*(n+1)/2 end: seq(A002662(n), n=0..33); # _Johannes W. Meijer_, Aug 14 2011

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

%t Table[2^n - Binomial[n, 2] - n - 1, {n, 1, 100}] (* _Pablo Hueso Merino_, Dec 17 2019 *)

%o (Magma) [2^n - 1 - n*(n+1)/2: n in [0..35]]; // _Vincenzo Librandi_, May 20 2011

%o (Haskell)

%o a002662 n = a002662_list !! n

%o a002662_list = map (sum . drop 3) a007318_tabl

%o -- _Reinhard Zumkeller_, Jun 20 2015

%o (PARI) a(n)=2^n-1-n*(n+1)/2 \\ _Charles R Greathouse IV_, Oct 11 2015

%o (Python)

%o def A002662(n): return (1<<n)-1-(n*(n+1)>>1) # _Chai Wah Wu_, Aug 29 2023

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

%Y First differences are A000295.

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

%Y Cf. also A000290, A001045.

%K easy,nonn,nice

%O 0,5

%A _N. J. A. Sloane_