A000337 - OEIS

%I M3874 N1587 #240 Sep 21 2024 02:24:22

%S 0,1,5,17,49,129,321,769,1793,4097,9217,20481,45057,98305,212993,

%T 458753,983041,2097153,4456449,9437185,19922945,41943041,88080385,

%U 184549377,385875969,805306369,1677721601,3489660929,7247757313,15032385537,31138512897,64424509441

%N a(n) = (n-1)*2^n + 1.

%C a(n) also gives number of 0's in binary numbers 1 to 111..1 (n+1 bits). - _Stephen G Penrice_, Oct 01 2000

%C Numerator of m(n) = (m(n-1)+n)/2, m(0)=0. Denominator is A000079. - _Reinhard Zumkeller_, Feb 23 2002

%C a(n) is the number of directed column-convex 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

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

%C Genus of graph of n-cube = a(n-3) = 1+(n-4)*2^(n-3), n>1.

%C Sum of ordered partitions of n where each element is summed via T(e-1). See A066185 for more information. - _Jon Perry_, Dec 12 2003

%C a(n-2) is the number of Dyck n-paths 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

%C Permutations in S_{n+2} avoiding 12-3 that contain the pattern 13-2 exactly once.

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

%C A member of the family of sequences defined by a(n) = Sum_{i=1..n} i*[c(1)*...*c(r)]^(i-1). This sequence has c(1)=2, A014915 has c(1)=3. - _Ctibor O. Zizka_, Feb 23 2008

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

%C 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^(q-3))*(q-4) + 1 such that M_q and its dual have polyhedral embeddings in R^3 [McMullen et al.]. - _Jonathan Vos Post_, Jul 25 2009

%C Sums of rows of the triangle in A173787. - _Reinhard Zumkeller_, Feb 28 2010

%C This sequence is related to A000079 by a(n) = n*A000079(n)-Sum_{i=0..n-1} A000079(i). - _Bruno Berselli_, Mar 06 2012

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

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

%C a(n) is the n-th number that is a sum of n positive n-th powers for n >= 1. a(4) = 49 = A003338(4). - _Alois P. Heinz_, Aug 01 2020

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

%C a(n-1) 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

%C a(n-1) 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

%C a(n-1) 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. 10-11 in Kiah et al.). - _Stefano Spezia_, Nov 02 2021

%D F. Harary, Topological concepts in graph theory, pp. 13-17 of F. Harary and L. Beineke, editors, A seminar on Graph Theory, Holt, Rinehart and Winston, New York, 1967.

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

%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 119.

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

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

%H Indranil Ghosh, <a href="/A000337/b000337.txt">Table of n, a(n) for n = 0..1000</a> (first 301 terms from T. D. Noe)

%H H. H. Bauschke and R. M. Corless, <a href="https://www.researchgate.net/publication/322200645_MapleTech_Volume_4_no_1_Spring_1997">Analyzing a Projection Method with Maple</a>, MapleTech Journal, 4:1 (1997), 2-7.

%H L. W. Beineke and F. Harary, <a href="http://dx.doi.org/10.4153/CJM-1965-048-6">The genus of the n-cube</a>, Canad. J. Math., 17 (1965), 494-496.

%H Ulrich Brehm and Egon Schulte, <a href="http://www.math.neu.edu/~schulte/polyhedmaps.pdf">Polyhedral Maps</a>. [_Jonathan Vos Post_, Jul 25 2009]

%H Harry Crane, <a href="https://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p057.pdf">Left-right arrangements, set partitions, and pattern avoidance</a>, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.

%H Pedro Fernando Fernández Espinosa and Agustín Moreno Cañadas, <a href="https://arxiv.org/abs/2104.00050">Homological Ideals as Integer Specializations of Some Brauer Configuration Algebras</a>, arXiv:2104.00050 [math.RT], 2021.

%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See p. 23.

%H R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

%H Christian Kassel and Christophe Reutenauer, <a href="https://arxiv.org/abs/1505.07229v3">The zeta function of the Hilbert scheme of n points on a two-dimensional torus</a>, arXiv:1505.07229v3 [math.AG], 2015. [A later version of this paper has a different title and different contents, and the number-theoretical part of the paper was moved to the publication below.]

%H Christian Kassel and Christophe Reutenauer, <a href="https://arxiv.org/abs/1610.07793">Complete determination of the zeta function of the Hilbert scheme of n points on a two-dimensional torus</a>, arXiv:1610.07793 [math.NT], 2016.

%H Han Mao Kiah, Alexander Vardy, and Hanwen Yao, <a href="https://arxiv.org/abs/2107.07377">Computing Permanents on a Trellis</a>, arXiv:2107.07377 [cs.IT], 2021.

%H S. Kitaev, J. Remmel, and M. Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I</a>, arXiv preprint arXiv:1201.6243 [math.CO], 2012.

%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 2015, #A16. (<a href="http://arxiv.org/abs/1302.2274">arXiv</a>, arXiv:1302.2274 [math.CO], 2013)

%H Santiago López de Medrano, <a href="https://arxiv.org/abs/2003.07508">On the genera of moment-angle manifolds associated to dual-neighborly polytopes, combinatorial formulas and sequences</a>, arXiv:2003.07508 [math.GT], 2020.

%H César Eliud Lozada, <a href="/A000337/a000337.jpg">Centroids of Pascal triangles</a>

%H P. McMullen, Ch. Schulz and J.M. Wills, <a href="http://dx.doi.org/10.1007/BF02760627">Polyhedral manifolds in E^3 with unusually large genus</a>, Israel J. Math. 46:127-144, 1983. [From _Jonathan Vos Post_, Jul 25 2009]

%H Toufik Mansour, <a href="https://arxiv.org/abs/math/0202219">Restricted permutations by patterns of type (2,1)</a>, arXiv:math/0202219 [math.CO], 2002.

%H Michael Penn, <a href="https://www.youtube.com/watch?v=iGCMCwlh_M4">An awesome number theory contest problem</a>, YouTube video, 2022.

%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 Len Smiley, <a href="http://www.math.uaa.alaska.edu/~smiley/hardy.html">Hardy's algorithm</a>.

%H Nsibiet E. Udo, Praise Adeyemo, Balazs Szendroi, and Stavros Argyrios Papadakis, <a href="https://arxiv.org/abs/2409.10278">Ideals, representations and a symmetrised Bernoulli triangle</a>, arXiv:2409.10278 [math.AC], 2024. See pp. 2,4,8.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphGenus.html">Graph Genus</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>.

%H A. F. Y. Zhao, <a href="http://www.emis.de/journals/JIS/VOL17/Zhao/zhao3.html">Pattern Popularity in Multiply Restricted Permutations</a>, Journal of Integer Sequences, 17 (2014), #14.10.3.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-8,4).

%F Binomial transform of A004273. Binomial transform of A008574 if the leading zero is dropped.

%F G.f.: x/((1-x)*(1-2*x)^2). - _Simon Plouffe_ in his 1992 dissertation

%F E.g.f.: exp(x) - exp(2*x)*(1-2*x). a(n) = 4*a(n-1) - 4*a(n-2)+1, n>0. Series reversion of g.f. A(x) is x*A034015(-x). - _Michael Somos_

%F Binomial transform of n/(n+1) is a(n)/(n+1). - _Paul Barry_, Aug 19 2005

%F a(n) = A119258(n+1,n-1) for n>0. - _Reinhard Zumkeller_, May 11 2006

%F Convolution of "Number of fixed points in all 231-avoiding involutions in S_n" (A059570) with "The odd numbers" (A005408), treating the result as if offset=0. - _Graeme McRae_, Jul 12 2006

%F a(n) = Sum_{k=1..n} k*2^(k-1), partial sums of A001787. - _Zerinvary Lajos_, Oct 19 2006

%F a(n) = 5*a(n-1) - 8*a(n-2) + 4*a(n-3), n > 2. - _Harvey P. Dale_, Jun 21 2011

%F a(n) = Sum_{k=1..n} Sum_{i=1..n} i * C(k,i). - _Wesley Ivan Hurt_, Sep 19 2017

%F a(n) = A000295(n+1)^2 - A000295(n)*A000295(n+2). - _Gregory Gerard Wojnar_, Oct 23 2018

%p A000337 := proc(n) 1+(n-1)*2^n ; end proc: # _R. J. Mathar_, Oct 10 2011

%t 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 *)

%t Table[(n - 1) 2^n + 1, {n, 0, 40}] (* _Harvey P. Dale_, Jun 21 2011 *)

%t LinearRecurrence[{5, -8, 4}, {0, 1, 5}, 40] (* _Harvey P. Dale_, Jun 21 2011 *)

%t CoefficientList[Series[x / ((1 - x) (1 - 2 x)^2), {x, 0, 50}], x] (* _Vincenzo Librandi_, Nov 21 2014 *)

%o (PARI) a(n)=if(n<0,0,(n-1)*2^n+1)

%o (Magma) [(n-1)*2^n + 1: n in [0..40]]; // _Vincenzo Librandi_, Nov 21 2014

%o (Python) a=lambda n:((n-1)<<(n))+1 # _Indranil Ghosh_, Jan 05 2017

%o (GAP) List([0..30],n->(n-1)*2^n+1); # _Muniru A Asiru_, Oct 24 2018

%Y a(n) = T(3, n), array T given by A048472. A036799/2.

%Y Cf. A001787, A066185, A077436, A023758, A014915.

%Y Cf. A000079, A209359.

%Y Cf. A000295, A008292.

%Y Cf. A003338.

%Y Main diagonal of A336725.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_