A000247 a(n) = 2^n - n - 2.

0, 3, 10, 25, 56, 119, 246, 501, 1012, 2035, 4082, 8177, 16368, 32751, 65518, 131053, 262124, 524267, 1048554, 2097129, 4194280, 8388583, 16777190, 33554405, 67108836, 134217699, 268435426, 536870881, 1073741792, 2147483615

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Ways of placing n+1 labeled balls into 2 indistinguishable boxes with at least 2 balls in each box.

2^a(n) is an integer of the form 1/(2 - Sum_{i=1..m} i/2^i). - Benoit Cloitre, Oct 25 2002

Number of permutations avoiding 13-2 that contain the pattern 23-1 exactly twice.

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

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

Subsequence of A158581; A000120(a(n)) > 1. - Reinhard Zumkeller, Apr 16 2009

Number of vertices of the tropical Grassmannian simplicial complex G(2,n), related to phylogenetic trees. - Tom Copeland, Oct 03 2011

(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

For n>0, (a(n)) is row 3 of the convolution array A213568. - Clark Kimberling, Jun 20 2012

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

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

Examples

			a(3) = 4!/(2!*2!*2!) = 3.
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
• F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 296.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 76.
• 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

• T. D. Noe, Table of n, a(n) for n = 2..300
• Renzo Cavalieri, Moduli spaces of pointed rational curves, (2016).
• Antal E. Fekete, Apropos Two Notes on Notation, The Amer. Math. Monthly, Vol. 101, No. 8 (Oct., 1994), pp. 771-778. See p. 776.
• Robert Israel et al, Primes 2^n - n - 2, Mathematics StackExchange.
• L. E. Jeffery, Unit-primitive matrices
• T. Mansour, Restricted permutations by patterns of type 2-1, arXiv:math/0202219 [math.CO], 2002.
• Mathoverflow, Face numbers for tropical Grassmannian G'_2,7 simplicial complex?
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
• Erik Vigren and Andreas Dieckmann, A New Result in Form of Finite Triple Sums for a Series from Ramanujan's Notebooks, Symmetry (2022) Vol. 14, No. 6, 1090.
• Alex Vinokur, Fibonacci-like polynomials produced by m-ary Huffman codes for absolutely ordered sequences, arXiv:cs/0411002 [cs.DM], 2004.
• Eric Weisstein's World of Mathematics, Centipede Graph
• Eric Weisstein's World of Mathematics, Connected Dominating Set
• Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

Cf. A000478 (3 boxes), A058844 (4 boxes).

Programs

GAP

List([2..40], n-> 2^n -n-2); # G. C. Greubel, Jul 26 2019

Magma

[2^n -n-2: n in [2..40]]; // G. C. Greubel, Jul 26 2019

Maple

A000247:=(-3+2*z)/((2*z-1)*(z-1)**2); # Simon Plouffe in his 1992 dissertation

Mathematica

LinearRecurrence[{4,-5,2}, {0,3,10}, 40] (* Harvey P. Dale, Aug 23 2011 *)
Table[2^n -n-2, {n,2,40}] (* Eric W. Weisstein, Aug 09 2017 *)

Maxima

A000247(n):=2^n-n-2$
makelist(A000247(n),n,2,30); /* Martin Ettl, Nov 08 2012 */

PARI

a(n)=2^n-n-2 \\ Charles R Greathouse IV, Sep 28 2015

Sage

[2^n -n-2 for n in (2..40)] # G. C. Greubel, Jul 26 2019

Formula

E.g.f.: (exp(x)-1-x)*(exp(x)-1).

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

a(n) = 2*a(n-1) + n + 3 = a(n-1) + 2^(n-1) - 1 = A000295(n) - 1 = A000295(n+1) - 2^(n+1).

A107907(a(n)) = A000225(n). - Reinhard Zumkeller, May 28 2005

Starting (3, 10, 25, 56, ...) = binomial transform of [3, 7, 8, 8, 8, ...]. - Gary W. Adamson, Nov 07 2007

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

a(n) = (Sum_{k=2..floor(n/2)} binomial(n+1,k)) + if(n odd, binomial(n+1,(n+1)/2)/2, 0).

a(n) = Sum_{k=0..n-3} Sum_{i=0..n-1} C(i,k). - Wesley Ivan Hurt, Sep 20 2017

Extensions

Additional comments from Michael Steyer, Dec 02 2000

More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000

I recently changed the beginning of this sequence so the formulas etc. may need to be adjusted. - N. J. A. Sloane, Jan 24 2006

Formulas and comments adjusted for offset by Franklin T. Adams-Watters, Nov 10 2011