A016116 - cp's OEIS frontend

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

1, 1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 8192, 8192, 16384, 16384, 32768, 32768, 65536, 65536, 131072, 131072, 262144, 262144, 524288, 524288, 1048576, 1048576, 2097152

Offset: 0

N. J. A. Sloane, Dec 11 1999

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.
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
This sequence is the number of digits of each term of A061519. - Dmitry Kamenetsky, Jan 17 2009
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
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
INVERT and inverse INVERT transforms give A006138, A039834(n-1).
The Kn21 sums, see A180662, of triangle A065941 equal the terms of this sequence. - Johannes W. Meijer, Aug 15 2011
First differences of A027383. - Jason Kimberley, Nov 01 2011
Run lengths in A079944. - Jeremy Gardiner, Nov 21 2011
Number of binary palindromes (A006995) between 2^(n-1) and 2^n (for n>1). - Hieronymus Fischer, Feb 17 2012
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
Range of row n of the Circular Pascal array of order 4. - Shaun V. Ault, May 30 2014
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
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
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
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
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
a(n) is the number of length-(n+1) binary sequences, denoted , with s(1)=1 and with s(i+1)=s(i) for odd i. - Dennis P. Walsh, Sep 06 2018
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
Also, the number of walks of length n on the graph x--y--z, starting at x. - Sean A. Irvine, May 30 2025

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

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332, Oct 06 2014, Pages 45-54.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], 2014.
Arvind Ayyer, Amritanshu Prasad, and Steven Spallone, Odd partitions in Young's lattice, arXiv:1601.01776 [math.CO], 2016. See Theorem 6 p. 12.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.
Francesco Battistoni and Giuseppe Molteni, An elementary proof for a generalization of a Pohst's inequality, arXiv:2101.06163 [math.NT], 2021.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Emeric Deutsch, Problem 1633, Math. Mag., 74 #5 (2001), p. 403.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017.
A. Goupil, H. Cloutier, and F. Nouboud, Enumeration of polyominoes inscribed in a rectangle Discrete Applied Mathematics 158(2010), pp. 2014-2023.
S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1067
D. Levin, L. Pudwell, M. Riehl, and A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
D. Merlini, F. Uncini and M. C. Verri, A unified approach to the study of general and palindromic compositions, Integers 4 (2004), A23, 26 pp.
Agustín Moreno Cañadas, Hernán Giraldo, and Robinson Julian Serna Vanegas, Some integer partitions induced by orbits of Dynkin type, Far East Journal of Mathematical Sciences (FJMS), Vol. 101, No. 12 (2017), pp. 2745-2766.
Laurent Noé, Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group, 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.
Valentin Ovsienko, Villes paires et impaires (Oddtown and Eventown) I, Images des Mathématiques, CNRS, 2013 (in French).
Dennis Walsh, Notes on symmetric subsets of {1, 2, ..., n}
A. Yajima, How to calculate the number of stereoisomers of inositol-homologs, 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
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (0,2).

Cf. A006995, A057148, A079944, A112030, A112033.
a(n) = A094718(3, n).
Cf. A001333.
See A052955 for partial sums (without the initial term).
A000079 gives the odd-indexed terms of a(n).
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

List([0..45],n->2^Int(n/2)); # Muniru A Asiru, Apr 03 2018

[2^Floor(n/2): n in [0..50]]; // Vincenzo Librandi, Aug 16 2011

A016116:= proc(n): 2^floor(n/2) end: seq(A016116(n), n=0..42); # Dennis P. Walsh, Oct 27 2009

Table[ 2^Floor[n/2], {n, 0, 42}] (* Robert G. Wilson v, Jun 05 2004 *)
With[{c=2^Range[0,30]},Riffle[c,c]] (* Harvey P. Dale, Jan 23 2015 *)
CoefficientList[Series[(1+x)/(1-2*x^2), {x, 0, 50}], x] (* Stefano Spezia, Sep 07 2018 *)

makelist(2^floor(n/2), n, 0, 50); /* Martin Ettl, Oct 17 2012 */

PARI
```
a(n)=if(n<0,0,2^(n\2))
```

def A016116(n): return 1 << n//2 # Chai Wah Wu, Jun 07 2022

def A016116():
    x, y = -1, 0
    while True:
        yield -x
        x, y = x + y, x - y
a = A016116(); [next(a) for i in range(40)]  # Peter Luschny, Jul 11 2013

a(n) = a(n-1)*a(n-2)/a(n-3) = 2*a(n-2) = 2^A004526(n).
G.f.: (1+x)/(1-2*x^2).
a(n) = (1/2 + sqrt(1/8))*sqrt(2)^n + (1/2 - sqrt(1/8))*(-sqrt(2))^n. - Ralf Stephan, Mar 11 2003
E.g.f.: cosh(sqrt(2)*x) + sinh(sqrt(2)*x)/sqrt(2). - Paul Barry, Jul 16 2003
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
Diagonal sums of A046854. a(n) = Sum_{k=0..n} binomial(floor(n/2), k). - Paul Barry, Jul 07 2004
a(n) = a(n-2) + 2^floor((n-2)/2). - Paul Barry, Jul 14 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(floor(n/2), floor(k/2)). - Paul Barry, Jul 15 2004
E.g.f.: cosh(asinh(1) + sqrt(2)*x)/sqrt(2). - Michael Somos, Feb 28 2005
a(n) = Sum_{k=0..n} A103633(n,k). - Philippe Deléham, Dec 03 2006
a(n) = 2^(n/2)*((1 + (-1)^n)/2 + (1-(-1)^n)/(2*sqrt(2))). - Paul Barry, Nov 12 2009
a(n) = 2^((2*n - 1 + (-1)^n)/4). - Luce ETIENNE, Sep 20 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Maxima

PARI

Python

Sage

Formula