%I M2836 N1141 #136 Aug 13 2024 05:28:41
%S 0,3,10,25,56,119,246,501,1012,2035,4082,8177,16368,32751,65518,
%T 131053,262124,524267,1048554,2097129,4194280,8388583,16777190,
%U 33554405,67108836,134217699,268435426,536870881,1073741792,2147483615
%N a(n) = 2^n - n - 2.
%C Ways of placing n+1 labeled balls into 2 indistinguishable boxes with at least 2 balls in each box.
%C 2^a(n) is an integer of the form 1/(2 - Sum_{i=1..m} i/2^i). - _Benoit Cloitre_, Oct 25 2002
%C Number of permutations avoiding 13-2 that contain the pattern 23-1 exactly twice.
%C Cost of ternary maximum height Huffman tree with N internal nodes (non-leaves) for minimizing absolutely ordered sequences of size n = 2N + 1. - Alex Vinokur (alexvn(AT)barak-online.net), Nov 02 2004
%C a(n) is the number of Dyck n-paths whose third upstep initiates the last long ascent, n >= 1. A long ascent is one consisting of 2 or more upsteps. For example, a(3)=3 counts UUDuUDDD, UDUDuUDD, UUDDuUDD (third upstep in small type). - _David Callan_, Dec 08 2004
%C Subsequence of A158581; A000120(a(n)) > 1. - _Reinhard Zumkeller_, Apr 16 2009
%C Number of vertices of the tropical Grassmannian simplicial complex G(2,n), related to phylogenetic trees. - _Tom Copeland_, Oct 03 2011
%C (Conjecture) Let a(2)=0. For n > 2, let N = 2*n + 1. For each n, define the n X n tridiagonal unit-primitive matrix (see [Jeffery]) A_{N,1}=[0,1,0,...,0; 1,0,1,0,...,0; 0,1,0,1,0,...,0; ...; 0,...,0,1,0,1; 0,...,0,1,1] associated with N. Define the n-dimensional column vectors V_N = [v_1,v_2,...,v_n]^T = [A_{N,1}]^n*[1,1,...,1]^T, where [.]^T denotes matrix transpose and [1,...,1] is the n-dimensional unit vector. Let (v_k)_N denote the k-th element of V_N, k in {1,...,n}. Then a(n) = (v_(n-2))_N. - _L. Edson Jeffery_, Jan 20 2012
%C For n>0, (a(n)) is row 3 of the convolution array A213568. - _Clark Kimberling_, Jun 20 2012
%C For n>2, a(n-2) is the number of connected induced (non-null) subgraphs of the n-centipede graph. - _Giovanni Resta_, May 04 2017
%C a(n) is the number of maximal boundary strata of the moduli space of stable rational curves with n+1 marked points. The closures of the maximal boundary strata are called the irreducible boundary divisors of the moduli space; see Cavalieri Section 2.1. - _Harry Richman_, Aug 13 2024
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
%D F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 296.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 76.
%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 T. D. Noe, <a href="/A000247/b000247.txt">Table of n, a(n) for n = 2..300</a>
%H Renzo Cavalieri, <a href="https://www.math.colostate.edu/~renzo/teaching/Moduli16/Fields.pdf">Moduli spaces of pointed rational curves</a>, (2016).
%H Antal E. Fekete, <a href="http://www.jstor.org/stable/2974533">Apropos Two Notes on Notation</a>, The Amer. Math. Monthly, Vol. 101, No. 8 (Oct., 1994), pp. 771-778. See p. 776.
%H Robert Israel et al, <a href="https://math.stackexchange.com/questions/4581358/primes-2n-n-2">Primes 2^n - n - 2</a>, Mathematics StackExchange.
%H L. E. Jeffery, <a href="/wiki/User:L._Edson_Jeffery/Unit-Primitive_Matrices">Unit-primitive matrices</a>
%H T. Mansour, <a href="https://arxiv.org/abs/math/0202219">Restricted permutations by patterns of type 2-1</a>, arXiv:math/0202219 [math.CO], 2002.
%H Mathoverflow, <a href="http://mathoverflow.net/questions/76978/face-numbers-for-tropical-grassmannian-g-2-7-simplicial-complex">Face numbers for tropical Grassmannian G'_2,7 simplicial complex?</a>
%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 Erik Vigren and Andreas Dieckmann, <a href="https://doi.org/10.3390/sym14061090">A New Result in Form of Finite Triple Sums for a Series from Ramanujan's Notebooks</a>, Symmetry (2022) Vol. 14, No. 6, 1090.
%H Alex Vinokur, <a href="http://arXiv.org/abs/cs/0411002">Fibonacci-like polynomials produced by m-ary Huffman codes for absolutely ordered sequences</a>, arXiv:cs/0411002 [cs.DM], 2004.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CentipedeGraph.html">Centipede Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedDominatingSet.html">Connected Dominating Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Vertex-InducedSubgraph.html">Vertex-Induced Subgraph</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).
%F E.g.f.: (exp(x)-1-x)*(exp(x)-1).
%F G.f.: x^3*(3-2*x)/((1-2*x)*(1-x)^2).
%F a(n) = 2*a(n-1) + n + 3 = a(n-1) + 2^(n-1) - 1 = A000295(n) - 1 = A000295(n+1) - 2^(n+1).
%F A107907(a(n)) = A000225(n). - _Reinhard Zumkeller_, May 28 2005
%F Starting (3, 10, 25, 56, ...) = binomial transform of [3, 7, 8, 8, 8, ...]. - _Gary W. Adamson_, Nov 07 2007
%F a(2)=0, a(3)=3, a(4)=10, a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3). - _Harvey P. Dale_, Aug 23 2011
%F a(n) = (Sum_{k=2..floor(n/2)} binomial(n+1,k)) + if(n odd, binomial(n+1,(n+1)/2)/2, 0).
%F a(n) = Sum_{k=0..n-3} Sum_{i=0..n-1} C(i,k). - _Wesley Ivan Hurt_, Sep 20 2017
%e a(3) = 4!/(2!*2!*2!) = 3.
%p A000247:=(-3+2*z)/((2*z-1)*(z-1)**2); # _Simon Plouffe_ in his 1992 dissertation
%t LinearRecurrence[{4,-5,2}, {0,3,10}, 40] (* _Harvey P. Dale_, Aug 23 2011 *)
%t Table[2^n -n-2, {n,2,40}] (* _Eric W. Weisstein_, Aug 09 2017 *)
%o (Maxima) A000247(n):=2^n-n-2$
%o makelist(A000247(n),n,2,30); /* _Martin Ettl_, Nov 08 2012 */
%o (PARI) a(n)=2^n-n-2 \\ _Charles R Greathouse IV_, Sep 28 2015
%o (Magma) [2^n -n-2: n in [2..40]]; // _G. C. Greubel_, Jul 26 2019
%o (Sage) [2^n -n-2 for n in (2..40)] # _G. C. Greubel_, Jul 26 2019
%o (GAP) List([2..40], n-> 2^n -n-2); # _G. C. Greubel_, Jul 26 2019
%Y Cf. A000478 (3 boxes), A058844 (4 boxes).
%K nonn,easy,nice
%O 2,2
%A _N. J. A. Sloane_
%E Additional comments from _Michael Steyer_, Dec 02 2000
%E More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000
%E I recently changed the beginning of this sequence so the formulas etc. may need to be adjusted. - _N. J. A. Sloane_, Jan 24 2006
%E Formulas and comments adjusted for offset by _Franklin T. Adams-Watters_, Nov 10 2011