cp's OEIS Frontend

A016116 a(n) = 2^floor(n/2).

%I A016116 #256 May 30 2025 20:28:19
%S A016116 1,1,2,2,4,4,8,8,16,16,32,32,64,64,128,128,256,256,512,512,1024,1024,
%T A016116 2048,2048,4096,4096,8192,8192,16384,16384,32768,32768,65536,65536,
%U A016116 131072,131072,262144,262144,524288,524288,1048576,1048576,2097152
%N A016116 a(n) = 2^floor(n/2).
%C A016116 Powers of 2 doubled up. The usual OEIS policy is to omit the duplicates in such cases (when this would become A000079). This is an exception.
%C A016116 Number of symmetric compositions of n: e.g., 5 = 2+1+2 = 1+3+1 = 1+1+1+1+1 so a(5) = 4; 6 = 3+3 = 2+2+2 = 1+4+1 = 2+1+1+2 = 1+2+2+1 = 1+1+2+1+1 = 1+1+1+1+1+1 so a(6) = 8. - _Henry Bottomley_, Dec 10 2001
%C A016116 This sequence is the number of digits of each term of A061519. - _Dmitry Kamenetsky_, Jan 17 2009
%C A016116 Starting with offset 1 = binomial transform of [1, 1, -1, 3, -7, 17, -41, ...]; where A001333 = (1, 1, 3, 7, 17, 41, ...). - _Gary W. Adamson_, Mar 25 2009
%C A016116 a(n+1) is the number of symmetric subsets of [n]={1,2,...,n}. A subset S of [n] is symmetric if k is an element of S implies (n-k+1) is an element of S. - _Dennis P. Walsh_, Oct 27 2009
%C A016116 INVERT and inverse INVERT transforms give A006138, A039834(n-1).
%C A016116 The Kn21 sums, see A180662, of triangle A065941 equal the terms of this sequence. - _Johannes W. Meijer_, Aug 15 2011
%C A016116 First differences of A027383. - _Jason Kimberley_, Nov 01 2011
%C A016116 Run lengths in A079944. - _Jeremy Gardiner_, Nov 21 2011
%C A016116 Number of binary palindromes (A006995) between 2^(n-1) and 2^n (for n>1). - _Hieronymus Fischer_, Feb 17 2012
%C A016116 Pisano period lengths: 1, 1, 4, 1, 8, 4, 6, 1, 12, 8, 20, 4, 24, 6, 8, 1, 16, 12, 36, 8, ... . - _R. J. Mathar_, Aug 10 2012
%C A016116 Range of row n of the Circular Pascal array of order 4. - _Shaun V. Ault_, May 30 2014
%C A016116 a(n) is the number of permutations of length n avoiding both 213 and 312 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - _Manda Riehl_, Aug 05 2014
%C A016116 Also, the decimal representation of the diagonal from the origin to the corner (and from the corner to the origin except for the initial term) of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 190", based on the 5-celled von Neumann neighborhood when initialized with a single black (ON) cell at stage zero. - _Robert Price_, May 10 2017
%C A016116 a(n + 1) + n - 1, n > 0, is the number of maximal subsemigroups of the monoid of partial order-preserving or -reversing mappings on a set with n elements. See the East et al. link. - _James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017
%C A016116 Number of symmetric stairs with n cells. A stair is a snake polyomino allowing only two directions for adjacent cells: east and north. See A005418. - _Christian Barrientos_, May 11 2018
%C A016116 For n >= 4, a(n) is the exponent of the group of the Gaussian integers in a reduced system modulo (1+i)^(n+2). See A302254. - _Jianing Song_, Jun 27 2018
%C A016116 a(n) is the number of length-(n+1) binary sequences, denoted <s(1),...,s(n+1)>, with s(1)=1 and with s(i+1)=s(i) for odd i. - _Dennis P. Walsh_, Sep 06 2018
%C A016116 a(n+1) is the number of subsets of {1,2,..,n} in which all differences between successive elements of subsets are even.  For example, for n = 7, a(6) = 8 and the 8 subsets are {7}, {1,7}, {3,7}, {5,7}, {1,3,7}, {1,5,7}, {3,5,7}, {1,3,5,7}.  For odd differences between elements see Comment in A000045 (Fibonacci numbers). - _Enrique Navarrete_, Jul 01 2020
%C A016116 Also, the number of walks of length n on the graph x--y--z, starting at x. - _Sean A. Irvine_, May 30 2025
%H A016116 Vincenzo Librandi, <a href="/A016116/b016116.txt">Table of n, a(n) for n = 0..5000</a>
%H A016116 Shaun V. Ault and Charles Kicey, <a href="http://dx.doi.org/10.1016/j.disc.2014.05.020">Counting paths in corridors using circular Pascal arrays</a>, Discrete Mathematics, Volume 332, Oct 06 2014, Pages 45-54.
%H A016116 Shaun V. Ault and Charles Kicey, <a href="http://arxiv.org/abs/1407.2197">Counting paths in corridors using circular Pascal arrays</a>, arXiv:1407.2197 [math.CO], 2014.
%H A016116 Arvind Ayyer, Amritanshu Prasad, and Steven Spallone, <a href="http://arxiv.org/abs/1601.01776">Odd partitions in Young's lattice</a>, arXiv:1601.01776 [math.CO], 2016. See Theorem 6 p. 12.
%H A016116 Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.
%H A016116 Francesco Battistoni and Giuseppe Molteni, <a href="https://arxiv.org/abs/2101.06163">An elementary proof for a generalization of a Pohst's inequality</a>, arXiv:2101.06163 [math.NT], 2021.
%H A016116 Johann Cigler, <a href="http://arxiv.org/abs/1501.04750">Some remarks and conjectures related to lattice paths in strips along the x-axis</a>, arXiv:1501.04750 [math.CO], 2015.
%H A016116 Johann Cigler, <a href="https://arxiv.org/abs/2212.02118">Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials</a>, arXiv:2212.02118 [math.NT], 2022.
%H A016116 Emeric Deutsch, <a href="http://www.jstor.org/stable/2691040">Problem 1633</a>, Math. Mag., 74 #5 (2001), p. 403.
%H A016116 James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, <a href="https://arxiv.org/abs/1706.04967">Maximal subsemigroups of finite transformation and partition monoids</a>, arXiv:1706.04967 [math.GR], 2017.
%H A016116 A. Goupil, H. Cloutier, and F. Nouboud, <a href="https://doi.org/10.1016/j.dam.2010.08.011">Enumeration of polyominoes inscribed in a rectangle</a> Discrete Applied Mathematics 158(2010), pp. 2014-2023.
%H A016116 S. Heubach and T. Mansour, <a href="https://arxiv.org/abs/math/0310197">Counting rises, levels and drops in compositions</a>, arXiv:math/0310197 [math.CO], 2003.
%H A016116 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1067">Encyclopedia of Combinatorial Structures 1067</a>
%H A016116 D. Levin, L. Pudwell, M. Riehl, and A. Sandberg, <a href="http://www.etsu.edu/cas/math/pp2014/documents/talks/riehl.pdf">Pattern Avoidance on k-ary Heaps</a>, Slides of Talk, 2014.
%H A016116 D. Merlini, F. Uncini and M. C. Verri, <a href="http://www.emis.de/journals/INTEGERS/papers/e23/e23.Abstract.html">A unified approach to the study of general and palindromic compositions</a>, Integers 4 (2004), A23, 26 pp.
%H A016116 Agustín Moreno Cañadas, Hernán Giraldo, and Robinson Julian Serna Vanegas, <a href="http://dx.doi.org/10.17654/MS101122745">Some integer partitions induced by orbits of Dynkin type</a>, Far East Journal of Mathematical Sciences (FJMS), Vol. 101, No. 12 (2017), pp. 2745-2766.
%H A016116 Laurent Noé, <a href="http://www.lifl.fr/~noe/files/expose_JOV13.pdf">Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group</a>, in Rapide Bilan 2012-2013, Laurent, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013, Laurent, Année 2012-2013.
%H A016116 Valentin Ovsienko, <a href="http://images-archive.math.cnrs.fr/Villes-paires-et-impaires-Oddtown-2470.html">Villes paires et impaires (Oddtown and Eventown) I</a>, Images des Mathématiques, CNRS, 2013 (in French).
%H A016116 Dennis Walsh, <a href="http://capone.mtsu.edu/dwalsh/SYMMSUB.pdf">Notes on symmetric subsets of {1, 2, ..., n}</a>
%H A016116 A. Yajima, <a href="https://doi.org/10.1246/bcsj.20140204">How to calculate the number of stereoisomers of inositol-homologs</a>, Bull. Chem. Soc. Jpn. 2014, 87, 1260-1264 | doi:10.1246/bcsj.20140204. See Tables 1 and 2 (and text). - _N. J. A. Sloane_, Mar 26 2015
%H A016116 <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H A016116 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (0,2).
%F A016116 a(n) = a(n-1)*a(n-2)/a(n-3) = 2*a(n-2) = 2^A004526(n).
%F A016116 G.f.: (1+x)/(1-2*x^2).
%F A016116 a(n) = (1/2 + sqrt(1/8))*sqrt(2)^n + (1/2 - sqrt(1/8))*(-sqrt(2))^n. - _Ralf Stephan_, Mar 11 2003
%F A016116 E.g.f.: cosh(sqrt(2)*x) + sinh(sqrt(2)*x)/sqrt(2). - _Paul Barry_, Jul 16 2003
%F A016116 The signed sequence (-1)^n*2^floor(n/2) has a(n) = (sqrt(2))^n(1/2 - sqrt(2)/4) + (-sqrt(2))^n(1/2 + sqrt(2)/4). It is the inverse binomial transform of A000129(n-1). - _Paul Barry_, Apr 21 2004
%F A016116 Diagonal sums of A046854. a(n) = Sum_{k=0..n} binomial(floor(n/2), k). - _Paul Barry_, Jul 07 2004
%F A016116 a(n) = a(n-2) + 2^floor((n-2)/2). - _Paul Barry_, Jul 14 2004
%F A016116 a(n) = Sum_{k=0..floor(n/2)} binomial(floor(n/2), floor(k/2)). - _Paul Barry_, Jul 15 2004
%F A016116 E.g.f.: cosh(asinh(1) + sqrt(2)*x)/sqrt(2). - _Michael Somos_, Feb 28 2005
%F A016116 a(n) = Sum_{k=0..n} A103633(n,k). - _Philippe Deléham_, Dec 03 2006
%F A016116 a(n) = 2^(n/2)*((1 + (-1)^n)/2 + (1-(-1)^n)/(2*sqrt(2))). - _Paul Barry_, Nov 12 2009
%F A016116 a(n) = 2^((2*n - 1 + (-1)^n)/4). - _Luce ETIENNE_, Sep 20 2014
%e A016116 For n=5 the a(5)=4 symmetric subsets of [4] are {1,4}, {2,3}, {1,2,3,4} and the empty set. - _Dennis P. Walsh_, Oct 27 2009
%e A016116 For n=5 the a(5)=4 length-6 binary sequences are <1,1,0,0,0,0>, <1,1,0,0,1,1>, <1,1,1,1,0,0> and <1,1,1,1,1,1>. - _Dennis P. Walsh_, Sep 06 2018
%p A016116 A016116:= proc(n): 2^floor(n/2) end: seq(A016116(n), n=0..42); # _Dennis P. Walsh_, Oct 27 2009
%t A016116 Table[ 2^Floor[n/2], {n, 0, 42}] (* _Robert G. Wilson v_, Jun 05 2004 *)
%t A016116 With[{c=2^Range[0,30]},Riffle[c,c]] (* _Harvey P. Dale_, Jan 23 2015 *)
%t A016116 CoefficientList[Series[(1+x)/(1-2*x^2), {x, 0, 50}], x] (* _Stefano Spezia_, Sep 07 2018 *)
%o A016116 (PARI) a(n)=if(n<0,0,2^(n\2))
%o A016116 (Magma) [2^Floor(n/2): n in [0..50]]; // _Vincenzo Librandi_, Aug 16 2011
%o A016116 (Maxima) makelist(2^floor(n/2), n, 0, 50); /* _Martin Ettl_, Oct 17 2012 */
%o A016116 (Sage)
%o A016116 def A016116():
%o A016116     x, y = -1, 0
%o A016116     while True:
%o A016116         yield -x
%o A016116         x, y = x + y, x - y
%o A016116 a = A016116(); [next(a) for i in range(40)]  # _Peter Luschny_, Jul 11 2013
%o A016116 (GAP) List([0..45],n->2^Int(n/2)); # _Muniru A Asiru_, Apr 03 2018
%o A016116 (Python)
%o A016116 def A016116(n): return 1 << n//2 # _Chai Wah Wu_, Jun 07 2022
%Y A016116 Cf. A006995, A057148, A079944, A112030, A112033.
%Y A016116 a(n) = A094718(3, n).
%Y A016116 Cf. A001333.
%Y A016116 See A052955 for partial sums (without the initial term).
%Y A016116 A000079 gives the odd-indexed terms of a(n).
%Y A016116 The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - _N. J. A. Sloane_, Jul 14 2022
%K A016116 nonn,easy
%O A016116 0,3
%A A016116 _N. J. A. Sloane_, Dec 11 1999