

A000337


a(n) = (n1)*2^n + 1.
(Formerly M3874 N1587)


67



0, 1, 5, 17, 49, 129, 321, 769, 1793, 4097, 9217, 20481, 45057, 98305, 212993, 458753, 983041, 2097153, 4456449, 9437185, 19922945, 41943041, 88080385, 184549377, 385875969, 805306369, 1677721601, 3489660929, 7247757313, 15032385537, 31138512897, 64424509441
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

a(n) also gives number of 0's in binary numbers 1 to 111..1 (n+1 bits).  Stephen G. Penrice (spenrice(AT)ets.org), Oct 01 2000
Numerator of m(n) = (m(n1)+n)/2, m(0)=0. Denominator is A000079.  Reinhard Zumkeller, Feb 23 2002
a(n) is the number of directed columnconvex polyominoes of area n+2 having along the lower contour exactly one vertical step that is followed by a horizontal step (a reentrant corner).  Emeric Deutsch, May 21 2003
a(n) is the number of bits in binary numbers from 1 to 111...1 (n bits). Partial sums of A001787.  Emeric Deutsch, May 24 2003
Genus of graph of ncube = a(n3) = 1+(n4)*2^(n3), n>1.
Sum of ordered partitions of n where each element is summed via T(e1). See A066185 for more information.  Jon Perry, Dec 12 2003
a(n2) is the number of Dyck npaths with exactly one peak at height >= 3. For example, there are 5 such paths with n=4: UUUUDDDD, UUDUUDDD, UUUDDUDD, UDUUUDDD, UUUDDDUD.  David Callan, Mar 23 2004
Permutations in S_{n+2} avoiding 123 that contain the pattern 132 exactly once.
a(n) is prime for n = 2, 3, 7, 27, 51, 55, 81. a(n) is semiprime for n = 4, 5, 6, 8, 9, 10, 11, 13, 15, 19, 28, 32, 39, 57, 63, 66, 75, 97.  Jonathan Vos Post, Jul 18 2005
A member of the family of sequences defined by a(n) = Sum_{i=1..n} i*[c(1)*...*c(r)]^(i1). This sequence has c(1)=2, A014915 has c(1)=3.  Ctibor O. Zizka, Feb 23 2008
Starting with 1 = row sums of A023758 as a triangle by rows: [1; 2,3; 4,6,7; 8,12,14,15; ...].  Gary W. Adamson, Jul 18 2008
Equivalent formula given in Brehm: for each q >= 3 there exists a polyhedral map M_q of type {4, q} with [number of vertices] f_0 = 2^q and [genus] g = (2^(q3))*(q4) + 1 such that M_q and its dual have polyhedral embeddings in R^3 [McMullen et al.].  Jonathan Vos Post, Jul 25 2009
Sums of rows of the triangle in A173787.  Reinhard Zumkeller, Feb 28 2010
This sequence is related to A000079 by a(n) = n*A000079(n)Sum_{i=0..n1} A000079(i).  Bruno Berselli, Mar 06 2012
(1+ 5*x + 17*x^2 + 49*x^3 + ...) = (1 + 2*x + 4*x^2 + 8*x^3 + ...) * (1 + 3*x + 7*x^2 + 15*x^3) + ...).  Gary W. Adamson, Mar 14 2012
The first barycentric coordinate of the centroid of Pascal triangles, assuming that numbers are weights, is A000295(n+1)/A000337(n), no matter what the triangle sides are. See attached figure.  César Eliud Lozada, Nov 14 2014
a(n) is the nth number that is a sum of n positive nth powers for n >= 1. a(4) = 49 = A003338(4).  Alois P. Heinz, Aug 01 2020
a(n) is the sum of the largest elements of all subsets of {1,2,..,n}. For example, a(3)=17; the subsets of {1,2,3} are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, and the sum of the largest elements is 17.  Enrique Navarrete, Aug 20 2020
a(n1) is the sum of the second largest elements of the subsets of {1,2,..,n} that contain n. For example, for n = 4, a(3)=17; the subsets of {1,2,3,4} that contain 4 are {4}, {1,4}, {2,4}, {3,4}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}, and the sum of the second largest elements is 17.  Enrique Navarrete, Aug 24 2020
a(n1) is also the sum of diameters of all subsets of {1,2,...,n} that contain n. For example, for n = 4, a(3)=17; the subsets of {1,2,3,4} that contain 4 are {4}, {1,4}, {2,4}, {3,4}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}; the diameters of these sets are 0,3,2,1,3,3,2,3 and the sum is 17.  Enrique Navarrete, Sep 07 2020
a(n1) is also the number of additions required to compute the permanent of general n X n matrices using trellis methods (see Theorems 5 and 6, pp. 1011 in Kiah et al.).  Stefano Spezia, Nov 02 2021


REFERENCES

F. Harary, Topological concepts in graph theory, pp. 1317 of F. Harary and L. Beineke, editors, A seminar on Graph Theory, Holt, Rinehart and Winston, New York, 1967.
V. G. Gutierrez and S. L. de Medrano, Surfaces as complete intersections, in Riemann and Klein Surfaces, Automorphisms, Symmetries and Moduli Spaces, edited by Milagros Izquierdo, S. Allen Broughton, Antonio F. Costa, Contemp. Math. vol. 629, 2014, pp. 171.
F. Harary, Graph Theory. AddisonWesley, Reading, MA, 1969, p. 119.
G. H. Hardy, A Theorem Concerning the Infinite Cardinal Numbers, Quart. J. Math., 35 (1904), p. 90 = Collected Papers of G. H. Hardy, Vol. VII, p. 430.
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 and Indranil Ghosh, Table of n, a(n) for n = 0..1000 (first 301 terms from T. D. Noe)
H. H. Bauschke and R. M. Corless, Analyzing a Projection Method with Maple, MapleTech Journal, 4:1 (1997), 27.
L. W. Beineke and F. Harary, The genus of the ncube, Canad. J. Math., 17 (1965), 494496.
Ulrich Brehm and Egon Schulte, Polyhedral Maps. [Jonathan Vos Post, Jul 25 2009]
Harry Crane, Leftright arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 5772.
Pedro Fernando Fernández Espinosa and Agustín Moreno Cañadas, Homological Ideals as Integer Specializations of Some Brauer Configuration Algebras, arXiv:2104.00050 [math.RT], 2021.
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
Christian Kassel and Christophe Reutenauer, The zeta function of the Hilbert scheme of n points on a twodimensional torus, arXiv:1505.07229v3 [math.AG], 2015. [A later version of this paper has a different title and different contents, and the numbertheoretical part of the paper was moved to the publication below.]
Christian Kassel and Christophe Reutenauer, Complete determination of the zeta function of the Hilbert scheme of n points on a twodimensional torus, arXiv:1610.07793 [math.NT], 2016.
Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021.
S. Kitaev, J. Remmel and M. Tiefenbruck, Marked mesh patterns in 132avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 2015, #A16. (arXiv, arXiv:1302.2274 [math.CO], 2013)
Santiago López de Medrano, On the genera of momentangle manifolds associated to dualneighborly polytopes, combinatorial formulas and sequences, arXiv:2003.07508 [math.GT], 2020.
César Eliud Lozada, Centroids of Pascal triangles
P. McMullen, Ch. Schulz and J.M. Wills, Polyhedral manifolds in E^3 with unusually large genus, Israel J. Math. 46:127144, 1983. [From Jonathan Vos Post, Jul 25 2009]
T. Mansour, Restricted permutations by patterns of type (2,1), arXiv:math/0202219 [math.CO], 2002.
Michael Penn, An awesome number theory contest problem, YouTube video, 2022.
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
Len Smiley, Hardy's algorithm
Eric Weisstein's World of Mathematics, Graph Genus
Eric Weisstein's World of Mathematics, Hypercube Graph
A. F. Y. Zhao, Pattern Popularity in Multiply Restricted Permutations, Journal of Integer Sequences, 17 (2014), #14.10.3.
Index entries for linear recurrences with constant coefficients, signature (5,8,4).


FORMULA

Binomial transform of A004273. Binomial transform of A008574 if the leading zero is dropped.
G.f.: x/((1x)*(12*x)^2).  Simon Plouffe in his 1992 dissertation
E.g.f.: exp(x)  exp(2*x)*(12*x). a(n) = 4*a(n1)  4*a(n2)+1, n>0. Series reversion of g.f. A(x) is x*A034015(x).  Michael Somos
Binomial transform of n/(n+1) is a(n)/(n+1).  Paul Barry, Aug 19 2005
a(n) = A119258(n+1,n1) for n>0.  Reinhard Zumkeller, May 11 2006
Convolution of "Number of fixed points in all 231avoiding involutions in S_n" (A059570) with "The odd numbers" (A005408), treating the result as if offset=0.  Graeme McRae, Jul 12 2006
a(n) = Sum_{k=1..n} k*2^(k1), partial sums of A001787.  Zerinvary Lajos, Oct 19 2006
a(n) = 5*a(n1)  8*a(n2) + 4*a(n3), n > 2.  Harvey P. Dale, Jun 21 2011
a(n) = Sum_{k=1..n} Sum_{i=1..n} i * C(k,i).  Wesley Ivan Hurt, Sep 19 2017
a(n) = A000295(n+1)^2  A000295(n)*A000295(n+2).  Gregory Gerard Wojnar, Oct 23 2018


MAPLE

A000337 := proc(n) 1+(n1)*2^n ; end proc: # R. J. Mathar, Oct 10 2011


MATHEMATICA

Table[Sum[(1)^(n  k) k (1)^(n  k) Binomial[n + 1, k + 1], {k, 0, n}], {n, 0, 28}] (* Zerinvary Lajos, Jul 08 2009 *)
Table[(n  1) 2^n + 1, {n, 0, 40}] (* Harvey P. Dale, Jun 21 2011 *)
LinearRecurrence[{5, 8, 4}, {0, 1, 5}, 40] (* Harvey P. Dale, Jun 21 2011 *)
CoefficientList[Series[x / ((1  x) (1  2 x)^2), {x, 0, 50}], x] (* Vincenzo Librandi, Nov 21 2014 *)


PROG

(PARI) a(n)=if(n<0, 0, (n1)*2^n+1)
(Magma) [(n1)*2^n + 1: n in [0..40]]; // Vincenzo Librandi, Nov 21 2014
(Python) a=lambda n:((n1)<<(n))+1 # Indranil Ghosh, Jan 05 2017
(GAP) List([0..30], n>(n1)*2^n+1); # Muniru A Asiru, Oct 24 2018


CROSSREFS

a(n) = T(3, n), array T given by A048472. A036799/2.
Cf. A001787, A066185, A077436, A023758, A014915.
Cf. A000079, A209359.
Cf. A000295, A008292.
Cf. A003338.
Main diagonal of A336725.
Sequence in context: A083091 A176953 A082753 * A147260 A273688 A146045
Adjacent sequences: A000334 A000335 A000336 * A000338 A000339 A000340


KEYWORD

nonn,easy,nice,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



