|
|
A002662
|
|
a(n) = 2^n - 1 - n*(n+1)/2.
(Formerly M3866 N1585)
|
|
39
|
|
|
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
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
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).
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
|
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).
|
|
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
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]
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
|
|
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
|
|
|
MATHEMATICA
|
With[{nn=40}, Join[{0}, First[#]-1-Last[#]&/@Thread[{2^Range[nn], Accumulate[ Range[nn]]}]]] (* Harvey P. Dale, May 10 2012 *)
|
|
PROG
|
(Haskell)
a002662 n = a002662_list !! n
a002662_list = map (sum . drop 3) a007318_tabl
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|