

A000918


a(n) = 2^n  2.
(Formerly M1599 N0625)


126



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 n1 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 semiprime, one triprime, ... and one product of exactly n1 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
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 nelement set onto a twoelement set, with n >= 2.  Mohamed Bouhamida, 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 (see link Japanese Mathematical Olympiad).
Let P(A) be the power set of an nelement 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, 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 lengthn 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 redblack tree of height 2*n2. 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)) = n1.  L. Edson Jeffery, Nov 27 2015
Actually this follows from the procedure for determining the multiplicity of prime p in C(n) given in A000108 by Franklin T. AdamsWatters: 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^k1. Therefore C(2^k2) is divisible by 2^(k1) for k > 0 and there is no smaller m for which 2^(k1) divides C(m) proving the conjecture.  Peter Schorn, Feb 16 2020
For n >= 0, a(n) is the largest number you can write in bijective base2 (a.k.a. the dyadic system, A007931) with n digits.  Harald Korneliussen, May 18 2019
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


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, AddisonWesley, 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.
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
Andrei Asinowski, Cyril Banderier, Benjamin Hackl, Flipsort and combinatorial aspects of popstack sorting, arXiv:2003.04912 [math.CO], 2020.
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), 91100.
S. Bilotta, E. Grazzini, E. Pergola, Enumeration of Two Particular Sets of Minimal Permutations, J. Int. Seq. 18 (2015) 15.10.2
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 7480.
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 nonexistence 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.
Japanese Mathematical Olympiad 1993, Final Round  Problem 2, Feb 11 1993.
Ross La Haye, Binary Relations on the Power Set of an nElement 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], 20092013. [Jonathan Vos Post, Dec 17 2009]
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257260. [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
H. P. Robinson, Letter to N. J. A. Sloane, Sep 1975
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911. [Annotated scans of pages 3033 only]
Eric Weisstein's World of Mathematics, Sphere Line Picking
Index entries for linear recurrences with constant coefficients, signature (3,2)
Index to sequences related to Olympiads.


FORMULA

a(n) = 2*A000225(n1).
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, 4step).  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..n1} 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(n1)  A000325(n).
a(n) = A095151(n)  A125128(n)  1. (End)
a(n+1) = 2*(n + Sum_{j=1..n1} (nj)*2^(j1)), 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(j1). See the example for n = 3 below. Motivated by the proposal A287012 by Mark Rickert.  Wolfdieter Lang, Jun 14 2017


EXAMPLE

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


MAPLE

seq(2^n2, 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 range(0, 29)] # Zerinvary Lajos, May 31 2009
(PARI) a(n)=2^n2 \\ 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.
Cf. A058809 (3^n3, n>0).
Sequence in context: A122959 A095121 A296965 * 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



