A000918 - OEIS

%I M1599 N0625 #340 Mar 01 2024 05:26:27

%S -1,0,2,6,14,30,62,126,254,510,1022,2046,4094,8190,16382,32766,65534,

%T 131070,262142,524286,1048574,2097150,4194302,8388606,16777214,

%U 33554430,67108862,134217726,268435454,536870910,1073741822,2147483646,4294967294,8589934590,17179869182,34359738366,68719476734,137438953470

%N a(n) = 2^n - 2.

%C For n > 1, a(n) is the expected number of tosses of a fair coin to get n-1 consecutive heads. - _Pratik Poddar_, Feb 04 2011

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

%C For n > 0, the number of nonempty proper subsets of an n-element set. - _Ross La Haye_, Feb 07 2004

%C Numbers j such that abs( Sum_{k=0..j} (-1)^binomial(j, k)*binomial(j + k, j - k) ) = 1. - _Benoit Cloitre_, Jul 03 2004

%C 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

%C 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

%C 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 semiprime, one triprime, ... and one product of exactly n-1 primes. 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

%C 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

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

%C Partial sums of A155559. - _Zerinvary Lajos_, Oct 03 2007

%C Number of surjections from an n-element set onto a two-element set, with n >= 2. - _Mohamed Bouhamida_, Dec 15 2007

%C 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 (see link Japanese Mathematical Olympiad).

%C 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

%C The permutohedron Pi_n has 2^n - 2 facets [Pashkovich]. - _Jonathan Vos Post_, Dec 17 2009

%C First differences of A005803. - _Reinhard Zumkeller_, Oct 12 2011

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

%C a(n) is the number of branches of a complete binary tree of n levels. - _Denis Lorrain_, Dec 16 2011

%C 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

%C 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

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

%C Actually this follows from the procedure for determining the multiplicity of prime p in C(n) given in A000108 by _Franklin T. Adams-Watters_: For p=2, the multiplicity is the number of 1 digits minus 1 in the binary representation of n+1. Obviously, the smallest k achieving "number of 1 digits" = k is 2^k-1. Therefore C(2^k-2) is divisible by 2^(k-1) for k > 0 and there is no smaller m for which 2^(k-1) divides C(m) proving the conjecture. - _Peter Schorn_, Feb 16 2020

%C For n >= 0, a(n) is the largest number you can write in bijective base-2 (a.k.a. the dyadic system, A007931) with n digits. - _Harald Korneliussen_, May 18 2019

%C The terms of this sequence are also the sum of the terms in each row of Pascal's triangle other than the ones. - _Harvey P. Dale_, Apr 19 2020

%C For n > 1, binomial(a(n),k) is odd if and only if k is even. - _Charlie Marion_, Dec 22 2020

%C For n >= 2, a(n+1) is the number of n X n arrays of 0's and 1's with every 2 X 2 square having density exactly 2. - _David desJardins_, Oct 27 2022

%C For n >= 1, a(n+1) is the number of roots of unity in the unique degree-n unramified extension of the 2-adic field Q_2. Note that for each p, the unique degree-n unramified extension of Q_p is the splitting field of x^(p^n) - x, hence containing p^n - 1 roots of unity for p > 2 and 2*(2^n - 1) for p = 2. - _Jianing Song_, Nov 08 2022

%D 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.

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

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

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

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

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

%H Vincenzo Librandi, <a href="/A000918/b000918.txt">Table of n, a(n) for n = 0..1000</a>

%H Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, <a href="https://arxiv.org/abs/2003.04912">Flip-sort and combinatorial aspects of pop-stack sorting</a>, arXiv:2003.04912 [math.CO], 2020.

%H O. Bagdasar, <a href="http://www.np.ac.rs/downloads/publications/VOL6_Br_2/vol6br2-3.pdf">On some functions involving the lcm and gcd of integer tuples</a>, Scientific Publications of the State University of Novi Pazar, Appl. Maths. Inform. and Mech., Vol. 6, 2 (2014), 91--100.

%H S. Bilotta, E. Grazzini, and E. Pergola, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Grazzini/graz3.html">Enumeration of Two Particular Sets of Minimal Permutations</a>, J. Int. Seq. 18 (2015) 15.10.2

%H R. B. Campbell, <a href="http://dx.doi.org/10.1016/j.jtbi.2015.06.037">The effect of inbreeding constraints and offspring distribution on time to the most recent common ancestor</a>, Journal of Theoretical Biology,  Volume 382, 7 October 2015, Pages 74-80.

%H Adam M. Goyt and Lara K. Pudwell, <a href="http://arxiv.org/abs/1203.3786">Avoiding colored partitions of two elements in the pattern sense</a>, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012

%H M. A. Hill, M. J. Hopkins and D. C. Ravenel, <a href="http://www.math.rochester.edu/u/faculty/doug/kervaire_082609.pdf">On the non-existence of elements of Kervaire invariant one</a> [From _N. J. A. Sloane_, Sep 27 2010]

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=77">Encyclopedia of Combinatorial Structures 77</a>

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Enumerative Formulas for Some Functions on Finite Sets</a>

%H Milan Janjic and B. Petkovic, <a href="http://arxiv.org/abs/1301.4550">A Counting Function</a>, arXiv 1301.4550 [math.CO], 2013.

%H Japanese Mathematical Olympiad 1993, <a href="https://imomath.com/othercomp/Jap/JapMO93.pdf">Final Round - Problem 2</a>, Feb 11 1993.

%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

%H T. Manneville, V. Pilaud, <a href="http://arxiv.org/abs/1501.07152">Compatibility fans for graphical nested complexes</a>, arXiv preprint arXiv:1501.07152 [math.CO], 2015.

%H Kanstantsin Pashkovich, <a href="http://arxiv.org/abs/0912.3446">Symmetry in Extended Formulations of the Permutahedron [sic]</a>, arXiv:0912.3446 [math.CO], 2009-2013. [_Jonathan Vos Post_, Dec 17 2009]

%H P. A. Piza, <a href="http://www.jstor.org/stable/3029339">Kummer numbers</a>, Mathematics Magazine, 21 (1947/1948), 257-260.

%H P. A. Piza, <a href="/A001117/a001117.pdf">Kummer numbers</a>, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]

%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 Pratik Poddar, <a href="http://pratikpoddarcse.blogspot.com/2009/10/lets-say-keep-tossing-fair-coin-until.html">Consecutive Heads Puzzle</a>, Oct 2009.

%H H. P. Robinson, <a href="/A001466/a001466.pdf">Letter to N. J. A. Sloane, Sep 1975</a>

%H A. H. Voigt, <a href="/A000918/a000918.pdf">Theorie der Zahlenreihen und der Reihengleichungen</a>, Goschen, Leipzig, 1911. [Annotated scans of pages 30-33 only]

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SphereLinePicking.html">Sphere Line Picking</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2).

%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.

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

%F G.f.: 1/(1 - 2*x) - 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

%F For n >= 1, a(n) = A008970(n + 1, 2). - _Philippe Deléham_, Feb 21 2004

%F G.f.: (3*x - 1)/((2*x - 1)*(x - 1)). - _Simon Plouffe_ in his 1992 dissertation for the sequence without the leading -1

%F a(n) = 2*a(n - 1) + 2. - _Alexandre Wajnberg_, Apr 25 2005

%F a(n) = A000079(n) - 2. - _Omar E. Pol_, Dec 16 2008

%F a(n) = A058896(n)/A052548(n). - _Reinhard Zumkeller_, Feb 14 2009

%F a(n) = A164874(n - 1, n - 1) for n > 1. - _Reinhard Zumkeller_, Aug 29 2009

%F a(n) = A173787(n,1); a(n) = A028399(2*n)/A052548(n), n > 0. - _Reinhard Zumkeller_, Feb 28 2010

%F a(n + 1) = A027383(2*n - 1). - _Jason Kimberley_, Nov 02 2011

%F 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

%F a(n+1) is the sum of row n in triangle A051601. - _Reinhard Zumkeller_, Aug 05 2013

%F a(n+1) = A127330(n,0). - _Reinhard Zumkeller_, Nov 16 2013

%F a(n) = Sum_{k=1..n-1} binomial(n, k) for n > 0. - _Dan McCandless_, Nov 14 2015

%F From _Miquel Cerda_, Aug 16 2016: (Start)

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

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

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

%F a(n+1) = 2*(n + Sum_{j=1..n-1} (n-j)*2^(j-1)), n >= 1. This is the number of the rationals k/2, k = 1..2*n for n >= 1 and (2*k+1)/2^j for j = 2..n, n >= 2, and 2*k+1 < n-(j-1). See the example for n = 3 below. Motivated by the proposal A287012 by _Mark Rickert_. - _Wolfdieter Lang_, Jun 14 2017

%e a(4) = 14 because the 14 = 6 + 4 + 4 rationals (in lowest terms) for n = 3 are (see the Jun 14 2017 formula above): 1/2, 1, 3/2, 2, 5/2, 3; 1/4, 3/4, 5/4, 7/4; 1/8, 3/8, 5/8, 7/8. - _Wolfdieter Lang_, Jun 14 2017

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

%p [-1, seq(Stirling2(n,2)*2,n=1..28)]; # _Zerinvary Lajos_, Dec 06 2006

%p 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

%t Table[2^n - 2, {n, 0, 29}] (* _Alonso del Arte_, Dec 01 2012 *)

%o (Sage) [gaussian_binomial(n,1,2)-1 for n in range(0,29)] # _Zerinvary Lajos_, May 31 2009

%o (PARI) a(n)=2^n-2 \\ _Charles R Greathouse IV_, Jun 16 2011

%o (Magma) [2^n - 2: n in [0..40]]; // _Vincenzo Librandi_, Jun 23 2011

%o (Haskell)

%o a000918 = (subtract 2) . (2 ^)

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

%o -- _Reinhard Zumkeller_, Apr 23 2013

%Y Row sums of triangle A026998.

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

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

%Y Cf. A058809 (3^n-3, n>0).

%K sign,easy

%O 0,3

%A _N. J. A. Sloane_

%E Maple programs fixed by _Vaclav Kotesovec_, Dec 13 2014