|
%I M3866 N1585 #177 Aug 29 2023 17:18:40
%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
%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 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
%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 Cf. A000079, A000124, A000217, A000225, A000295, A002663, A002664, A035038-A035042, A007318, A342352.
%Y Cf. also A000290, A001045.
%K easy,nonn,nice
%O 0,5
%A _N. J. A. Sloane_
|
