login
a(n) = 2^n - n - 2.
(Formerly M2836 N1141)
21

%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