login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000918 a(n) = 2^n - 2.
(Formerly M1599 N0625)
108
-1, 0, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534, 131070, 262142, 524286, 1048574, 2097150, 4194302, 8388606, 16777214, 33554430, 67108862, 134217726, 268435454, 536870910, 1073741822, 2147483646, 4294967294, 8589934590, 17179869182, 34359738366, 68719476734, 137438953470 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

For n > 3, a(n) is the expected number of tosses of a fair coin to get (n - 1) consecutive heads. - Pratik Poddar, Feb 04 2011

For n > 2, Sum_{k =1..a(n)} (-1)^binomial(n, k) = A064405(a(n)) + 1 = 0. - Benoit Cloitre, Oct 18 2002

For n > 0, the number of nonempty proper subsets of an n element set. - Ross La Haye, Feb 07 2004

Numbers n such that abs( Sum_{k=0..n} (-1)^binomial(n, k)*binomial(n + k, n - k) ) = 1. - Benoit Cloitre, Jul 03 2004

For n > 2 this formula also counts edge rooted forests in a cycle of length n. - Woong Kook (andrewk(AT)math.uri.edu), Sep 08 2004

For n >= 1, conjectured to be the number of integers from 0 to (10^n)-1 that lack 0, 1, 2, 3, 4, 5, 6 and 7 as a digit. - Alexandre Wajnberg, Apr 25 2005

Beginning with a(2) = 2, these are the partial sums of the subsequence of A000079 = 2^n beginning with A000079(1) = 2. Hence for n >= 2 a(n) is the smallest possible sum of exactly one prime, one two-almost prime, one three-almost prime, ... and one (n - 1)-almost prime. A060389 (partial sums of the primorials, A002110, beginning with A002110(1)=2) is the analog when all the almost primes must also be squarefree. - Rick L. Shepherd, May 20 2005

From the second term on (n >= 1), the binary representation of these numbers is a 0 preceded by (n - 1) 1's. This pattern (0)111...1110 is the "opposite" of the binary 2^n+1: 1000...0001 (cf. A000051). - Alexandre Wajnberg, May 31 2005

The numbers 2^n - 2 (n >= 2) give the positions of 0's in A110146. Also numbers n such that n^(n + 1) = 0 mod (n + 2). - Zak Seidov, Feb 20 2006

Partial sums of A155559. - Zerinvary Lajos, Oct 03 2007

Number of surjections from an n-element set onto a two-element set, with n >= 2. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Dec 15 2007

It appears that these are the numbers n such that 3*A135013(n) = n*(n + 1), thus answering Problem 2 on the Mathematical Olympiad Foundation of Japan, Final Round Problems, Feb 11 1993.

Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if x is a proper subset of y or y is a proper subset of x and x and y are disjoint. Then a(n+1) = |R|. - Ross La Haye, Mar 19 2009

Apart the first term which is -1 the number of units of a(n) belongs to a periodic sequence: 0, 2, 6, 4. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 04 2009

The permutahedron Pi_n has 2^n - 2 facets [Pashkovich]. - Jonathan Vos Post, Dec 17 2009

First differences of A005803. - Reinhard Zumkeller, Oct 12 2011

For n >= 1, a(n + 1) is the smallest even number with bit sum n. Cf. A069532. - Jason Kimberley, Nov 01 2011

a(n) is the number of branches of a complete binary tree of n levels. - Denis Lorrain, Dec 16 2011

For n>=1, a(n) is the number of length-n words on alphabet {1,2,3} such that the gap(w)=1.  For a word w the gap g(w) is the number of parts missing between the minimal and maximal elements of w.  Generally for words on alphabet {1,2,...,m} with g(w)=g>0 the e.g.f. is: Sum_{k=g+2..m} (m - k + 1)*binomial((k - 2),g)*(exp(x) - 1)^(k - g).  a(3)=6 because we have: 113, 131, 133, 311, 313, 331. Cf. A240506. See the Heubach/Mansour reference. - Geoffrey Critzer, Apr 13 2014

For n > 0, a(n) is the minimal number of internal nodes of a red-black tree of height 2*n-2. See the Oct 02 2015 comment under A027383. - Herbert Eberle, Oct 02 2015

Conjecture: For n>0, a(n) is the least m such that A007814(A000108(m)) = n-1. - L. Edson Jeffery, Nov 27 2015

REFERENCES

H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 212.

Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134.  [From Mohammad K. Azarian, October 27 2011]

S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009 page 86, Exercise 3.16.

Mathematical Olympiad Foundation of Japan, Final Round Problems, Feb 11 1993, Problem 2.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.

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).

A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911, p. 31.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

O. Bagdasar, On some functions involving the lcm and gcd of integer tuples, Scientific Publications of the State University of Novi Pazar, Appl. Maths. Inform. and Mech., Vol. 6, 2 (2014), 91--100.

R. B. Campbell, The effect of inbreeding constraints and offspring distribution on time to the most recent common ancestor, Journal of Theoretical Biology,  Volume 382, 7 October 2015, Pages 74-80.

Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From N. J. A. Sloane, Sep 17 2012

M. A. Hill, M. J. Hopkins and D. C. Ravenel, On the non-existence of elements of Kervaire invariant one [From N. J. A. Sloane, Sep 27 2010]

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 77

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

M. Janjic and B. Petkovic, A Counting Function, arXiv 1301.4550 [math.CO], 2013.

Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015.

Kanstantsin Pashkovich, Symmetry in Extended Formulations of the Permutahedron, arXiv:0912.3446 [math.CO], 2009-2013. [Jonathan Vos Post, Dec 17 2009]

P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.

P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Pratik Poddar, Consecutive Heads Puzzle, Dec 2009

A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911. [Annotated scans of pages 30-33 only]

Eric Weisstein's World of Mathematics, Sphere Line Picking

Index entries for linear recurrences with constant coefficients, signature (3,-2)

FORMULA

a(n) = 2*A000225(n-1).

G.f.: 1/(1 - 2x) - 2/(1 - x), e.g.f.: (e^x - 1)^2 - 1. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001

For n >= 1, a(n) = A008970(n + 1, 2). - Philippe Deléham, Feb 21 2004

G.f.: (3*x - 1)/((2*x - 1)(x - 1)). - Simon Plouffe in his 1992 dissertation for the sequence without the leading -1

a(n) = 2a(n - 1) + 2. - Alexandre Wajnberg, Apr 25 2005

a(n) = A000079(n) - 2. - Omar E. Pol, Dec 16 2008

a(n) = A058896(n)/A052548(n). - Reinhard Zumkeller, Feb 14 2009

a(n) = A164874(n - 1, n - 1) for n > 1. - Reinhard Zumkeller, Aug 29 2009

a(n) = A173787(n,1); a(n) = A028399(2*n)/A052548(n), n > 0. - Reinhard Zumkeller, Feb 28 2010

a(n + 1) = A027383(2n - 1). - Jason Kimberley, Nov 02 2011

G.f.: U(0) -1 , where U(k) = 1 + x/(2^k + 2^k/(x - 1 - x^2*2^(k + 1)/(x*2^(k + 1) - (k + 1)/U(k + 1) ))); (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Dec 01 2012

a(n+1) = sum of row n in triangle A051601. - Reinhard Zumkeller, Aug 05 2013

a(n+1) = A127330(n,0). - Reinhard Zumkeller, Nov 16 2013

a(n) = Sum_{k=1..n-1} binomial(n, k) for n > 0. - Dan McCandless, Nov 14 2015

From Miquel Cerda, Aug 16 2016: (Start)

a(n) = A000225(n) - 1.

a(n) = A125128(n-1) - A000325(n).

a(n) = A095151(n) - A125128(n) - 1. (End)

MAPLE

seq(2^n-2, n=0..20) ;

[-1, seq(Stirling2(n, 2)*2, n=1..28)]; # Zerinvary Lajos, Dec 06 2006

ZL := [S, {S=Prod(B, B), B=Set(Z, 1 <= card)}, labeled]: [-1, seq(combstruct[count](ZL, size=n), n=1..28)]; # Zerinvary Lajos, Mar 13 2007

MATHEMATICA

Table[2^n - 2, {n, 0, 29}] (* Alonso del Arte, Dec 01 2012 *)

PROG

(Sage) [gaussian_binomial(n, 1, 2)-1 for n in xrange(0, 29)] # Zerinvary Lajos, May 31 2009

(PARI) a(n)=2^n-2 \\ Charles R Greathouse IV, Jun 16 2011

(MAGMA) [2^n - 2: n in [0..40]]; // Vincenzo Librandi, Jun 23 2011

(Haskell)

a000918 = (subtract 2) . (2 ^)

a000918_list = iterate ((subtract 2) . (* 2) . (+ 2)) (- 1)

-- Reinhard Zumkeller, Apr 23 2013

CROSSREFS

Row sums of triangle A026998.

Cf. A000919, A001117, A001118, A095121, A110146.

Cf. A033484, A000225, A000325, A095151, A125128.

Sequence in context: A122958 A122959 A095121 * A059076 A237623 A232059

Adjacent sequences:  A000915 A000916 A000917 * A000919 A000920 A000921

KEYWORD

sign,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Maple programs fixed by Vaclav Kotesovec, Dec 13 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 19:46 EDT 2017. Contains 286926 sequences.