A060546 -id:A060546 - 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

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, 1534, 2046, 3070, 4094, 6142, 8190, 12286, 16382, 24574, 32766, 49150, 65534, 98302, 131070, 196606, 262142, 393214, 524286, 786430, 1048574, 1572862, 2097150, 3145726, 4194302, 6291454

Offset: 0

R. K. Guy

Number of balanced strings of length n: let d(S) = #(1's) - #(0's), # == count in S, then S is balanced if every substring T of S has -2 <= d(T) <= 2.
Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded. - Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999
Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.) - Jeffrey Shallit, Sep 02 2002
a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
Partial sums of A016116. - Hieronymus Fischer, Sep 15 2007
Equals row sums of triangle A152201. - Gary W. Adamson, Nov 29 2008
From John P. McSorley, Sep 28 2010: (Start)
a(n) = DPE(n+1) is the total number of k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of k-double-palindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.
The 6 double-palindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one double-palindrome.
(End)
From Herbert Eberle, Oct 02 2015: (Start)
For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.
In order a red-black tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.
Consider:
mrbt5                R
                    / \
                   /   \
                  /     \
                 /       B
                /       / \
mrbt4          B       /   B
              / \     B   E E
             /   B   E E
mrbt3       R   E E
           / \
          /   B
mrbt2    B   E E
        / E
mrbt1  R
      E E
(Red nodes shown as R, blacks as B, externals as E.)
Red-black trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.
Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.
(End)
Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121. - Herbert Kociemba, Apr 29 2017
a(n-2) is the number of achiral n-bead necklaces or bracelets using exactly two colors.  For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB. - Robert A. Russell, Sep 26 2018
Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - Yuchun Ji, Nov 16 2018
Also the number of binary words of length n with cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019
Also the number of up-down paths with n steps such that the height difference between the highest and lowest points is at most 2. - Jeremy Dover, Jun 17 2020
Also the number of non-singleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i. - Gus Wiseman, Feb 19 2022

			After 3 folds one sees 4 fold lines.
Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
Binary: 1, 10, 100, 110, 1010, 1110, 10110, 11110, 101110, 111110, 1011110, 1111110, 10111110, 11111110, 101111110, 111111110, 1011111110, 1111111110, 10111111110, ... - _Jason Kimberley_, Nov 02 2011
Example: Partial sums of powers of 2 repeated 2 times:
a(3) = 1+1+2 = 4;
a(4) = 1+1+2+2 = 6;
a(5) = 1+1+2+2+4 = 10.
_Yuchun Ji_, Nov 16 2018

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [John P. McSorley, Sep 28 2010]

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, Under misprinted head B3, Amer Math. Monthly, 104(1997) 753-754.
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, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013.
Eric Weisstein's World of Mathematics, Cage Graph
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A132666, A152201.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), this sequence (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A000066 (actual order of a (3,g)-cage).
Bisections are A033484 (even) and A000918 (odd).
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A062011, A329862, A329863.
The complementary compositions are counted by A274230(n-1) + 1, with bisections A060867 (even) and A134057 (odd).
Cf. A000346, A000984, A001405, A001700, A011782 (compositions).
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

import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
-- Reinhard Zumkeller, Jun 17 2015

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

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n], n=1..41); # Zerinvary Lajos, Mar 16 2008

a[n_?EvenQ] := 3*2^(n/2)-2; a[n_?OddQ] := 2^(2+(n-1)/2)-2; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 21 2011, after Quim Castellsaguer *)
LinearRecurrence[{1, 2, -2}, {1, 2, 4}, 41] (* Robert G. Wilson v, Oct 06 2014 *)
Table[Length[Select[Tuples[{0,1},n],And[Max@@Length/@Split[#]<=2,!MatchQ[Length/@Split[#],{_,2,ins:1..,2,_}/;OddQ[Plus[ins]]]]&]],{n,0,15}] (* Gus Wiseman, Nov 28 2019 *)

a(n)=2^(n\2+1)+2^((n+1)\2)-2 \\ Charles R Greathouse IV, Oct 21 2011

def a(n): return 2**((n+2)//2) + 2**((n+1)//2) - 2
print([a(n) for n in range(43)]) # Michael S. Branicky, Feb 19 2022

a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
a(2n) = 3*2^n - 2 = A033484(n);
a(2n-1) = 2^(n+1) - 2 = A000918(n+1).
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = Sum_{k=0..n} 2^min(k, n-k).
a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2) - 2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es)
a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (3-2*sqrt(2))*(-1)^n)/2 - 2. - Paul Barry, Apr 23 2004
a(n) = A132340(A052955(n)). - Reinhard Zumkeller, Aug 20 2007
a(n) = A052955(n+1) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n+1)) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n-1)+1) for n > 0. - Hieronymus Fischer, Sep 15 2007
A132666(a(n)) = a(n-1) + 1 for n > 0. - Hieronymus Fischer, Sep 15 2007
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = 2*( (a(n-2)+1) mod (a(n-1)+1) ), n > 1. - Pierre Charland, Dec 12 2010
a(n) = A136252(n-1) + 1, for n > 0. - Jason Kimberley, Nov 01 2011
G.f.: (1+x*R(0))/(1-x), where R(k) = 1 + 2*x/( 1 - x/(x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013
a(n) = 2^((2*n + 3*(1-(-1)^n))/4)*3^((1+(-1)^n)/2) - 2. - Luce ETIENNE, Sep 01 2014
a(n) = a(n-1) + 2^floor((n-1)/2) for n>0, a(0)=1. - Yuchun Ji, Nov 23 2018
E.g.f.: 3*cosh(sqrt(2)*x) - 2*cosh(x) + 2*sqrt(2)*sinh(sqrt(2)*x) - 2*sinh(x). - Stefano Spezia, Apr 06 2022

More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000

Replaced definition with a simpler one. - N. J. A. Sloane, Jul 09 2022

A029744 Numbers of the form 2^n or 3*2^n.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864, 2097152, 3145728, 4194304

Offset: 1

N. J. A. Sloane

This entry is a list, and so has offset 1. WARNING: However, in this entry several comments, formulas and programs seem to refer to the original version of this sequence which had offset 0. - M. F. Hasler, Oct 06 2014
Number of necklaces with n-1 beads and two colors that are the same when turned over and hence have reflection symmetry. [edited by Herbert Kociemba, Nov 24 2016]
The subset {a(1),...,a(2k)} contains all proper divisors of 3*2^k. - Ralf Stephan, Jun 02 2003
Let k = any nonnegative integer and j = 0 or 1. Then n+1 = 2k + 3j and a(n) = 2^k*3^j. - Andras Erszegi (erszegi.andras(AT)chello.hu), Jul 30 2005
Smallest number having no fewer prime factors than any predecessor, a(0)=1; A110654(n) = A001222(a(n)); complement of A116451. - Reinhard Zumkeller, Feb 16 2006
A093873(a(n)) = 1. - Reinhard Zumkeller, Oct 13 2006
a(n) = a(n-1) + a(n-2) - gcd(a(n-1), a(n-2)), n >= 3, a(1)=2, a(2)=3. - Ctibor O. Zizka, Jun 06 2009
Where records occur in A048985: A193652(n) = A048985(a(n)) and A193652(n) < A048985(m) for m < a(n). - Reinhard Zumkeller, Aug 08 2011
A002348(a(n)) = A000079(n-3) for n > 2. - Reinhard Zumkeller, Mar 18 2012
Without initial 1, third row in array A228405. - Richard R. Forberg, Sep 06 2013
Also positions of records in A048673. A246360 gives the record values. - Antti Karttunen, Sep 23 2014
Known in numerical mathematics as "Bulirsch sequence", used in various extrapolation methods for step size control. - Peter Luschny, Oct 30 2019
For n > 1, squares of the terms can be expressed as the sum of two powers of two: 2^x + 2^y. - Karl-Heinz Hofmann, Sep 08 2022

Vincenzo Librandi, Table of n, a(n) for n = 1..2000
Spencer Daugherty, Pamela E. Harris, Ian Klein, and Matt McClinton, Metered Parking Functions, arXiv:2406.12941 [math.CO], 2024. See pp. 11, 22.
Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, The Binary Two-Up Sequence, arXiv:2209.04108 [math.CO], Sep 11 2022.
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Guo-Niu Han, Enumeration of Standard Puzzles. [Cached copy]
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From _N. J. A. Sloane_, Nov 26 2012
Index entries for linear recurrences with constant coefficients, signature (0,2).
Index entries for sequences related to necklaces

Cf. A056493, A038754, A063759. Union of A000079 and A007283.
First differences are in A016116(n-1).
Cf. A082125, A094958, A048739, A048985, A193652, A048673, A064216, A246360, A354785.
Row sums of the triangle in sequence A119963. - John P. McSorley, Aug 31 2010
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. There may be minor differences from (s(n)) at the start, and a shift of indices. A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A060482 (s(n)-3); A136252 (s(n)-3); A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4);   A354785 (3*s(n)), A061776 (3*s(n)-6); 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

a029744 n = a029744_list !! (n-1)
a029744_list = 1 : iterate
   (\x -> if x `mod` 3 == 0 then 4 * x `div` 3 else 3 * x `div` 2) 2
-- Reinhard Zumkeller, Mar 18 2012

1,seq(op([2^i,3*2^(i-1)]),i=1..100); # Robert Israel, Sep 23 2014

CoefficientList[Series[(-x^2 - 2*x - 1)/(2*x^2 - 1), {x, 0, 200}], x] (* Vladimir Joseph Stephan Orlovsky, Jun 10 2011 *)
Function[w, DeleteCases[Union@ Flatten@ w, k_ /; k > Max@ First@ w]]@ TensorProduct[{1, 3}, 2^Range[0, 22]] (* Michael De Vlieger, Nov 24 2016 *)
LinearRecurrence[{0,2},{1,2,3},50] (* Harvey P. Dale, Jul 04 2017 *)

PARI
```
a(n)=if(n%2,3/2,2)<<((n-1)\2)\1
```

def A029744(n):
    if n == 1: return 1
    elif n % 2 == 0: return 2**(n//2)
    else: return 3 * 2**((n-3)//2) # Karl-Heinz Hofmann, Sep 08 2022

(define (A029744 n) (cond ((<= n 1) n) ((even? n) (expt 2 (/ n 2))) (else (* 3 (expt 2 (/ (- n 3) 2)))))) ;; Antti Karttunen, Sep 23 2014

a(n) = 2*A000029(n) - A000031(n).
For n > 2, a(n) = 2*a(n - 2); for n > 3, a(n) = a(n - 1)*a(n - 2)/a(n - 3). G.f.: (1 + x)^2/(1 - 2*x^2). - Henry Bottomley, Jul 15 2001, corrected May 04 2007
a(0)=1, a(1)=1 and a(n) = a(n-2) * ( floor(a(n-1)/a(n-2)) + 1 ). - Benoit Cloitre, Aug 13 2002
(3/4 + sqrt(1/2))*sqrt(2)^n + (3/4 - sqrt(1/2))*(-sqrt(2))^n. a(0)=1, a(2n) = a(n-1)*a(n), a(2n+1) = a(n) + 2^floor((n-1)/2). - Ralf Stephan, Apr 16 2003 [Seems to refer to the original version with offset=0. - M. F. Hasler, Oct 06 2014]
Binomial transform is A048739. - Paul Barry, Apr 23 2004
E.g.f.: (cosh(x/sqrt(2)) + sqrt(2)sinh(x/sqrt(2)))^2.
a(1) = 1; a(n+1) = a(n) + A000010(a(n)). - Stefan Steinerberger, Dec 20 2007
u(2)=1, v(2)=1, u(n)=2*v(n-1), v(n)=u(n-1), a(n)=u(n)+v(n). - Jaume Oliver Lafont, May 21 2008
For n => 3, a(n) = sqrt(2*a(n-1)^2 + (-2)^(n-3)). - Richard R. Forberg, Aug 20 2013
a(n) = A064216(A246360(n)). - Antti Karttunen, Sep 23 2014
a(n) = sqrt((17 - (-1)^n)*2^(n-4)) for n >= 2. - Anton Zakharov, Jul 24 2016
Sum_{n>=1} 1/a(n) = 8/3. - Amiram Eldar, Nov 12 2020
a(n) = 2^(n/2) if n is even. a(n) = 3 * 2^((n-3)/2) if n is odd and for n>1. - Karl-Heinz Hofmann, Sep 08 2022

Corrected and extended by Joe Keane (jgk(AT)jgk.org), Feb 20 2000

A005418 Number of (n-1)-bead black-white reversible strings; also binary grids; also row sums of Losanitsch's triangle A034851; also number of caterpillar graphs on n+2 vertices.

Original entry on oeis.org

1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, 8256, 16512, 32896, 65792, 131328, 262656, 524800, 1049600, 2098176, 4196352, 8390656, 16781312, 33558528, 67117056, 134225920, 268451840, 536887296, 1073774592, 2147516416, 4295032832

Offset: 1

N. J. A. Sloane, R. K. Guy

Equivalently, walks on triangle, visiting n+2 vertices, so length n+1, n "corners"; the symmetry group is S3, reversing a walk does not count as different. Walks are not self-avoiding. - Colin Mallows
Slavik V. Jablan observes that this is also the number of rational knots and links with n+2 crossings (cf. A018240). See reference. [Corrected by Andrey Zabolotskiy, Jun 18 2020]
Number of bit strings of length (n-1), not counting strings which are the end-for-end reversal or the 0-for-1 reversal of each other as different. - Carl Witty (cwitty(AT)newtonlabs.com), Oct 27 2001
The formula given in page 1095 of the Balasubramanian reference can be used to derive this sequence. - Parthasarathy Nambi, May 14 2007
Also number of compositions of n up to direction, where a composition is considered equivalent to its reversal, see example. - Franklin T. Adams-Watters, Oct 24 2009
Number of normally non-isomorphic realizations of the associahedron of type I starting with dimension 2 in Ceballos et al. - Tom Copeland, Oct 19 2011
Number of fibonacenes with n+2 hexagons. See the Balaban and the Dobrynin references. - Emeric Deutsch, Apr 21 2013
From the point of view of binary grids, it is a (1,n)-rectangular grid. A225826 to A225834 are the numbers of binary pattern classes in the (m,n)-rectangular grid, 1 < m < 11. - Yosu Yurramendi, May 19 2013
Number of n-vertex difference graphs (bipartite 2K_2-free graphs) [Peled & Sun, Thm. 9]. - Falk Hüffner, Jan 10 2016
The offset should be 0, since the first row of A034851 is row 0. The name would then be: "Number of n bead...". - Daniel Forgues, Jul 26 2018
a(n) is the number of non-isomorphic generalized rigid ladders with n cells. A generalized rigid ladder with n cells is a graph with vertex set is the union of {u_0, u_1, ..., u_n} and {v_0, v_1, ..., v_n}, and for every 0 <= i <= n-1, the edges are of the form {u_i,u_i+1}, {v_i, v_i+1}, {u_i,v_i} and either {u_i,v_i+1} or {u_i+1,v_i}. - Christian Barrientos, Jul 29 2018
Also number of non-isomorphic stairs with n+1 cells. A stair is a snake polyomino allowing only two directions for adjacent cells: east and north. - Christian Barrientos and Sarah Minion, Jul 29 2018
From Robert A. Russell, Oct 28 2018: (Start)
There are two different unoriented row colorings using two colors that give us very similar results here, a difference of one in the offset. In an unoriented row, chiral pairs are counted as one.
a(n) is the number of color patterns (set partitions) of an unoriented row of length n using two or fewer colors (subsets). Two color patterns are equivalent if the colors are permutable.
a(n+1) is the number of ways to color an unoriented row of length n using two noninterchangeable colors (one need not use both colors).
See the examples below of these two different colorings. (End)
Also arises from the enumeration of types of based polyhedra with exactly two triangular faces [Rademacher]. - N. J. A. Sloane, Apr 24 2020
a(n) is the number of (unlabeled) 2-paths with n+4 vertices. (A 2-path with order n at least 4 can be constructed from a 3-clique by iteratively adding a new 2-leaf (vertex of degree 2) adjacent to an existing 2-clique containing an existing 2-leaf.) - Allan Bickle, Apr 05 2022
a(n) is the number of caterpillars with a perfect matching and order 2n+2. - Christian Barrientos, Sep 12 2023
a(n) is also the number of distinct planar embeddings of the (n+2)-centipede graph (up to at least n=8 and likely for all larger n). - Eric W. Weisstein, May 21 2024
a(n) is also the number of distinct planar embeddings of the 2 X (n+2) grid graph i.e., the (n+2)-ladder graph. - Eric W. Weisstein, May 21 2024
Dimension of the homogeneous component of degree n of the free Jordan algebra on two generators (or, in this case, the free special Jordan algebra on two generators). It follows from (Shirshov 1956, Cohn 1959). - Vladimir Dotsenko, Mar 29 2025

			a(5) = 10 because there are 16 compositions of 5 (shown as <vectors>) but only 10 equivalence classes (shown as {sets}): {<5>}, {<4,1>,<1,4>}, {<3,2>,<2,3>}, {<3,1,1>,<1,1,3>}, {<1,3,1>},{<2,2,1>,<1,2,2>}, {<2,1,2>}, {<2,1,1,1>,<1,1,1,2>}, {<1,2,1,1>,<1,1,2,1>}, {<1,1,1,1,1>}. - _Geoffrey Critzer_, Nov 02 2012
G.f. = x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 36*x^7 + 72*x^8 + ... - _Michael Somos_, Jun 24 2018
From _Robert A. Russell_, Oct 28 2018: (Start)
For a(5)=10, the 4 achiral patterns (set partitions) are AAAAA, AABAA, ABABA, and ABBBA. The 6 chiral pairs are AAAAB-ABBBB, AAABA-ABAAA, AAABB-AABBB, AABAB-ABABB, AABBA-ABBAA, and ABAAB-ABBAB. The colors are permutable.
For n=4 and a(n+1)=10, the 4 achiral colorings are AAAA, ABBA, BAAB, and BBBB. The 6 achiral pairs are AAAB-BAAA, AABA-ABAA, AABB-BBAA, ABAB-BABA, ABBB-BBBA, and BABB-BBAB. The colors are not permutable. (End)

K. Balasubramanian, "Combinatorial Enumeration of Chemical Isomers", Indian J. Chem., (1978) vol. 16B, pp. 1094-1096. See page 1095.
Wayne M. Dymacek, Steinhaus graphs. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 399--412, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561065 (81f:05120)
Jablan S. and Sazdanovic R., LinKnot: Knot Theory by Computer, World Scientific Press, 2007.
Joseph S. Madachy: Madachy's Mathematical Recreations. New York: Dover Publications, Inc., 1979, p. 46 (first publ. by Charles Scribner's Sons, New York, 1966, under the title: Mathematics on Vacation)
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]
C. A. Pickover, Keys to Infinity, Wiley 1995, p. 75.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 151 and 733.
Andrei Asinowski and Alon Regev, Triangulations with Few Ears: Symmetry Classes and Disjointness, Integers 16 (2016), #A5.
A. T. Balaban, Chemical graphs. Part 50. Symmetry and enumeration of fibonacenes (unbranched catacondensed benzenoids isoarithmic with helicenes and zigzag catafusenes), MATCH: Commun. Math. Comput. Chem., 24 (1989) 29-38.
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
A. P. Burger, M. Van Der Merwe, and J. H. Van Vuuren, An asymptotic analysis of the evolutionary spatial prisoner's dilemma on a path, Discrete Appl. Math. 160, No. 15, 2075-2088 (2012), Table 3.1.
C. Ceballos, F. Santos, and G. Ziegler, Many Non-equivalent Realizations of the Associahedron, arXiv:1109.5544 [math.MG], 2011-2013; pp. 15 and 26.
P. M. Cohn, Two embedding theorems for Jordan algebras, Proceedings of the London Mathematical Society, Volume s3-9, Issue 4, October 1959, pp. 503-524.
Jacob Crabtree, Another Enumeration of Caterpillar Trees, arXiv:1810.11744 [math.CO], 2018.
S. J. Cyvin, B. N. Cyvin, J. Brunvoll, E. Brendsdal, Zhang Fuji, Guo Xiaofeng, and R. Tosic, Theory of polypentagons, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.
Miroslav Marinov Dimitrov, Designing Boolean Functions and Digital Sequences for Cryptology and Communications, Ph. D. Dissertation, Bulgarian Acad. Sci. (Sofia, Bulgaria 2023).
A. A. Dobrynin, On the Wiener index of fibonacenes, MATCH: Commun. Math. Comput. Chem, 64 (2010), 707-726.
Vladimir Dotsenko and Irvin Roy Hentzel, On the conjecture of Kashuba and Mathieu about free Jordan algebras, arXiv:2507.00437 [math.RA], 2025. See p. 14.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
Sahir Gill, Bounds for Region Containing All Zeros of a Complex Polynomial, International Journal of Mathematical Analysis (2018), Vol. 12, No. 7, 325-333.
T. A. Gittings, Minimum braids: a complete invariant of knots and links, arXiv:math/0401051 [math.GT], 2004. - _N. J. A. Sloane_, Jan 18 2013
R. K. Guy, Letter to N. J. A. Sloane, Nov 1978.
Frank Harary and Allen J. Schwenk, The number of caterpillars, Discrete Mathematics, Volume 6, Issue 4, 1973, 359-365.
N. Hoffman, Binary grids and a related counting problem, Two-Year College Math. J. 9 (1978), 267-272.
S. V. Jablan, Geometry of Links, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29 (1999), no. 3, 121-139.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
Isaac B. Michael and M. R. Sepanski, Net regular signed trees, Australasian Journal of Combinatorics, Volume 66(2) (2016), 192-204.
U. N. Peled and F. Sun, Enumeration of difference graphs, Discrete Appl. Math., 60 (1995), 311-318.
Paulo Renato da Costa Pereira, Lilian Markenzon and Oswaldo Vernet, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.
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
Hans Rademacher, On the number of certain types of polyhedra, Illinois Journal of Mathematics 9.3 (1965): 361-380. Reprinted in Coll. Papers, Vol II, MIT Press, 1974, pp. 544-564. See Theorem 8, Eq. 14.3.
A. Regev, Remarks on two-eared triangulations, arXiv preprint arXiv:1309.0743 [math.CO], 2013-2014.
Suthee Ruangwises, The Landscape of Computing Symmetric n-Variable Functions with 2n Cards, arXiv:2306.13551 [cs.CR], 2023.
A. I. Shirshov, On special J-rings, Mat. Sb. (N.S.), 38(80), 1956, pp. 149-166.
N. J. A. Sloane, Classic Sequences
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), Article #00.1.1.
Eric Weisstein's World of Mathematics, Barker Code.
Eric Weisstein's World of Mathematics, Bishops Problem.
Eric Weisstein's World of Mathematics, Caterpillar Graph.
Eric Weisstein's World of Mathematics, Centipede Graph.
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Ladder Graph.
Eric Weisstein's World of Mathematics, Losanitsch's Triangle.
Eric Weisstein's World of Mathematics, Planar Embedding.
A. Yajima, How to calculate the number of stereoisomers of inositol-homologs, Bull. Chem. Soc. Jpn. 87 (2014), 1260-1264; see Tables 1 and 2 (and text). - _N. J. A. Sloane_, Mar 26 2015
Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Column 2 of A320750 (set partitions).
Cf. A131577 (oriented), A122746(n-3) (chiral), A016116 (achiral), for set partitions with up to two subsets.
Column 2 of A277504, offset by one (colors not permutable).
Cf. A000079 (oriented), A122746(n-2) (chiral), and A060546 (achiral), for a(n+1).
Cf. A001998, A001444, A051436, A051437, A007582, A001445, A032085.

a005418 n = sum $ a034851_row (n - 1) -- Reinhard Zumkeller, Jan 14 2012

A005418 := n->2^(n-2)+2^(floor(n/2)-1): seq(A005418(n), n=1..34);

LinearRecurrence[{2,2,-4}, {1,2,3}, 40] (* or *) Table[2^(n-2)+2^(Floor[n/2]-1), {n,40}] (* Harvey P. Dale, Jan 18 2012 *)

A005418(n)= 2^(n-2) + 2^(n\2-1); \\ Joerg Arndt, Sep 16 2013

def A005418(n): return 1 if n == 1 else 2**((m:= n//2)-1)*(2**(n-m-1)+1) # Chai Wah Wu, Feb 03 2022

a(n) = 2^(n-2) + 2^(floor(n/2) - 1).
G.f.: -x*(-1 + 3*x^2) / ( (2*x - 1)*(2*x^2 - 1) ). - Simon Plouffe in his 1992 dissertation
G.f.: x*(1+2*x)*(1-3*x^2)/((1-4*x^2)*(1-2*x^2)), not reduced. - Wolfdieter Lang, May 08 2001
a(n) = 6*a(n - 2) - 8*a(n - 4). a(2*n) = A063376(n - 1) = 2*a(2*n - 1); a(2*n + 1) = A007582(n). - Henry Bottomley, Jul 14 2001
a(n+2) = 2*a(n+1) - A077957(n) with a(1) = 1, a(2) = 2. - Yosu Yurramendi, Oct 24 2008
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3). - Jaume Oliver Lafont, Dec 05 2008
Union of A007582 and A161168. Union of A007582 and A063376. - Jaroslav Krizek, Aug 14 2009
G.f.: G(0); G(k) = 1 + 2*x/(1 - x*(1+2^(k+1))/(x*(1+2^(k+1)) + (1+2^k)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 12 2011
a(2*n) = 2*a(2*n-1) and a(2*n+1) = a(2*n) + 4^(n-1) with a(1) = 1. - Johannes W. Meijer, Aug 26 2013
From Robert A. Russell, Oct 28 2018: (Start)
a(n) = (A131577(n) + A016116(n)) / 2 = A131577(n) - A122746(n-3) = A122746(n-3) + A016116(n), for set partitions with up to two subsets.
a(n+1) = (A000079(n) + A060546(n)) / 2 = A000079(n) - A122746(n-2) = A122746(n-2) + A060546(n), for two colors that do not permute.
a(n) = Sum_{j=0..k} (S2(n,j) + Ach(n,j)) / 2, where k=2 is the maximum number of colors, S2(n,k) is the Stirling subset number A008277, and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
a(n+1) = (k^n + k^ceiling(n/2)) / 2, where k=2 is number of colors we can use. (End)
E.g.f.: (cosh(2*x) + 2*cosh(sqrt(2)*x) + sinh(2*x) + sqrt(2)*sinh(sqrt(2)*x) - 3)/4. - Stefano Spezia, Jun 01 2022

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287, 16383, 24575, 32767, 49151, 65535, 98303, 131071, 196607, 262143, 393215, 524287, 786431, 1048575, 1572863, 2097151, 3145727

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) is the least k such that A056792(k) = n.
One quarter of the number of positive integer (n+2) X (n+2) arrays with every 2 X 2 subblock summing to 1. - R. H. Hardin, Sep 29 2008
Number of length n+1 left factors of Dyck paths having no DUU's (here U=(1,1) and D=(1,-1)). Example: a(4)=7 because we have UDUDU, UUDDU, UUDUD, UUUDD, UUUDU, UUUUD, and UUUUU (the paths UDUUD, UDUUU, and UUDUU do not qualify).
Number of binary palindromes < 2^n (see A006995). - Hieronymus Fischer, Feb 03 2012
Partial sums of A016116 (omitting the initial term). - Hieronymus Fischer, Feb 18 2012
a(n - 1), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving or -reversing partial injective mappings on a set with n elements. - Wilf A. Wilson, Jul 21 2017
Number of monomials of the algebraic normal form of the Boolean function representing the n-th bit of the product 3x in terms of the bits of x. - Sebastiano Vigna, Oct 04 2020

			G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 7*x^4 + 11*x^5 + 15*x^6 + 23*x^7 + ... - _Michael Somos_, Jun 24 2018

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Zürich, Switzerland, 2019).
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, preprint, 2014.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, Journal of Combinatorics 5 (2014), 453-469.
David Blackman and Sebastiano Vigna, Scrambled Linear Pseudorandom Number Generators, ACM Transactions on Mathematical Software, Vol. 47, No. 4, p. 1-32, 2021; arXiv preprint, arXiv:1805.01407 [cs.DS], 2018.
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. [_Wilf A. Wilson_, Jul 21 2017]
Brian Hopkins and Aram Tangboonduangjit, Water Cells in Compositions of 1s and 2s, arXiv:2412.11528 [math.CO], 2024. See p. 9.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1026
Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, and Kamal Ali Alezabi, Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network, PLoS ONE (2020) Vol. 15, No. 8, e0237386.
Mark Shattuck, Further Results for the Capacity Statistic Distribution on Compositions of 1's and 2's, arXiv:2501.09931 [math.CO], 2025. See p. 3.
Index to sequences related to the complexity of n
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A000225 for even terms, A055010 for odd terms. See also A056792.
Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by Klaus Brockhaus, Aug 09 2009]
Union of A000225 & A055010.
For partial sums see A027383.
See A016116 for the first differences.
Cf. A083329, A107659, A132666.
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-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # G. C. Greubel, Oct 22 2019

a052955 n = a052955_list !! n
a052955_list = 1 : 2 : map ((+ 1) . (* 2)) a052955_list
-- Reinhard Zumkeller, Feb 22 2012

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // G. C. Greubel, Oct 22 2019

spec := [S,{S=Prod(Sequence(Prod(Union(Z,Z),Z)),Union(Sequence(Z),Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n]/2, n=2..43); # Zerinvary Lajos, Mar 16 2008

a[n_]:= If[EvenQ[n], 2^(n/2+1) -1, 3*2^((n-1)/2) -1]; Table[a[n], {n, 0, 41}] (* Robert G. Wilson v, Jun 05 2004 *)
a[0]=1; a[1]=2; a[n_]:= a[n]= 2 a[n-2] +1; Array[a, 42, 0]
a[n_]:= (2 + Mod[n, 2]) 2^Quotient[n, 2] - 1; (* Michael Somos, Jun 24 2018 *)

a(n)=(2+n%2)<<(n\2)-1 \\ Charles R Greathouse IV, Jun 19 2011

{a(n) = (n%2 + 2) * 2^(n\2) - 1}; /* Michael Somos, Jun 24 2018 */

# command line argument tells how high to take n
# Beyond a(38) = 786431 you may need a special code to handle large integers
  $lim = shift;
  sub show{};
$n = $incr = $P = 1;
show($n, $incr, $P);
$incr = 1;
for $n (2..$lim) {
    $P += $incr;
    show($n, $P, $incr, $P);
    $incr *=2 if ($n % 2); # double the increment after an odd n
}
sub show {
    my($n, $P) = @_;
    printf("%4d\t%16g\n", $n, $P);
}
# Mark A. Mandel (thnidu aT  g ma(il) doT c0m), Dec 29 2010

def A052955(n): return ((2|n&1)<<(n>>1))-1 # Chai Wah Wu, Jul 13 2023

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1 for n in (0..45)] # G. C. Greubel, Oct 22 2019

a(0)=1, a(1)=2; thereafter a(n) = 2*a(n-2) + 1, n >= 2.
G.f.: (1 + x - x^2)/((1 - x)*(1 - 2*x^2)).
a(n) = -1 + Sum_{alpha = RootOf(-1 + 2*Z^2)} (1/4) * (3 + 4*alpha) * alpha^(-1-n). (That is, the sum is indexed by the roots of the polynomial -1 + 2*Z^2.)
a(n) = 2^(n/2) * (3*sqrt(2)/4 + 1 - (3*sqrt(2)/4 - 1) * (-1)^n) - 1. - Paul Barry, May 23 2004
a(n) = 1 + Sum_{k=0..n-1} A016116(k). - Robert G. Wilson v, Jun 05 2004
A132340(a(n)) = A027383(n). - Reinhard Zumkeller, Aug 20 2007
From Hieronymus Fischer, Sep 15 2007: (Start)
a(n) = A027383(n-1) + 1 for n>0.
a(n) = A132666(a(n+1)-1).
a(n) = A132666(a(n-1)) + 1 for n>0.
A132666(a(n)) = a(n+1) - 1. (End)
a(n) = A027383(n+1)/2. - Zerinvary Lajos, Mar 16 2008
a(n) = (5 - (-1)^n)/2*2^floor(n/2) - 1. - Hieronymus Fischer, Feb 03 2012
a(2n+1) = (a(2*n) + a(2*n+2))/2. Combined with a(n) = 2*a(n-2) + 1, n >= 2 and a(0) = 1, this specifies the sequence. - Richard R. Forberg, Nov 30 2013
a(n) = ((5 - (-1)^n)/2)*2^((2*n - 1 + (-1)^n)/4) - 1. - Luce ETIENNE, Sep 20 2014
a(n) = -(2^(n+1)) * A107659(-3-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/4)*exp(-sqrt(2)*x)*(4 - 3*sqrt(2) + (4 + 3*sqrt(2))*exp(2*sqrt(2)*x) - 4*exp(x + sqrt(2)*x)). - Stefano Spezia, Oct 22 2019
A term k appears in this sequence <=> 4 does not divide binomial(k, j) for any j in 0..k. - Peter Luschny, Jun 28 2025

Formula and more terms from Henry Bottomley, May 03 2000
Additional comments from Robert G. Wilson v, Jan 29 2001
Minor edits from N. J. A. Sloane, Jul 09 2022

A163403 a(n) = 2*a(n-2) for n > 2; a(1) = 1, a(2) = 2.

Original entry on oeis.org

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

Offset: 1

Klaus Brockhaus, Jul 26 2009

a(n+1) is the number of palindromic words of length n using a two-letter alphabet. - Michael Somos, Mar 20 2011

			x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 8*x^6 + 8*x^7 + 16*x^8 + 16*x^9 + 32*x^10 + ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (0,2).

Equals A016116 without initial 1. Unsigned version of A152166.
Partial sums are in A136252.
Binomial transform is A078057, second binomial transform is A007070, third binomial transform is A102285, fourth binomial transform is A163350, fifth binomial transform is A163346.
Cf. A000079 (powers of 2), A009116, A009545, A051032.
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

[ n le 2 select n else 2*Self(n-2): n in [1..43] ];

LinearRecurrence[{0, 2}, {1, 2}, 50] (* Paolo Xausa, Feb 02 2024 *)

{a(n) = if( n<1, 0, 2^(n\2))} /* Michael Somos, Mar 20 2011 */

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

a(n) = 2^((1/4)*(2*n - 1 + (-1)^n)).
G.f.: x*(1 + 2*x)/(1 - 2*x^2).
a(n) = A051032(n) - 1.
G.f.: x / (1 - 2*x / (1 + x / (1 + x))) = x * (1 + 2*x / (1 - x / (1 - x / (1 + 2*x)))). - Michael Somos, Jan 03 2013
From R. J. Mathar, Aug 06 2009: (Start)
a(n) = A131572(n).
a(n) = A060546(n-1), n > 1. (End)
a(n+3) = a(n+2)*a(n+1)/a(n). - Reinhard Zumkeller, Mar 04 2011
a(n) = |A009116(n-1)| + |A009545(n-1)|. - Bruno Berselli, May 30 2011
E.g.f.: cosh(sqrt(2)*x) + sinh(sqrt(2)*x)/sqrt(2) - 1. - Stefano Spezia, Feb 05 2023

A052551 Expansion of 1/((1 - x)(1 - 2x^2)).

Original entry on oeis.org

1, 1, 3, 3, 7, 7, 15, 15, 31, 31, 63, 63, 127, 127, 255, 255, 511, 511, 1023, 1023, 2047, 2047, 4095, 4095, 8191, 8191, 16383, 16383, 32767, 32767, 65535, 65535, 131071, 131071, 262143, 262143, 524287, 524287, 1048575, 1048575, 2097151, 2097151

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Equals row sums of triangle A137865. - Gary W. Adamson, Feb 18 2008
Also, the decimal representation of the diagonal from the corner to the origin of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 566", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Jul 05 2017
Number of nonempty subsets of {1,2,...,n+1} that contain only odd numbers. a(0) = a(1) = 1: {1}; a(6) = a(7) = 15: {1}, {3}, {5}, {7}, {1,3}, {1,5}, {1,7}, {3,5}, {3,7}, {5,7}, {1,3,5}, {1,3,7}, {1,5,7}, {3,5,7}, {1,3,5,7}. - Enrique Navarrete, Mar 16 2018
Number of nonempty subsets of {1,2,...,n+2} that contain only even numbers. a(0) = a(1) = 1: {2}; a(4) = a(5) = 7: {2}, {4}, {6}, {2,4}, {2,6}, {4,6}, {2,4,6}. - Enrique Navarrete, Mar 26 2018
Doubling of A000225(n+1), n >= 0 entries. First differences give A077957. - Wolfdieter Lang, Apr 08 2018
a(n-2) is the number of achiral rows or cycles of length n partitioned into two sets or the number of color patterns using exactly 2 colors. An achiral row or cycle is equivalent to its reverse. Two color patterns are equivalent if the colors are permuted. For n = 4, the a(n-2) = 3 row patterns are AABB, ABAB, and ABBA; the cycle patterns are AAAB, AABB, and ABAB. For n = 5, the a(n-2) = 3 patterns for both rows and cycles are AABAA, ABABA, and ABBBA. For n = 6, the a(n-2) = 7 patterns for rows are AAABBB, AABABB, AABBAA, ABAABA, ABABAB, ABBAAB, and ABBBBA; the cycle patterns are AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABABB, and ABABAB. - Robert A. Russell, Oct 15 2018
For integers m > 1, the expansion of 1/((1 - x)*(1 - m*x^2)) generates a(n) = (sqrt(m)^(n + 1)*((-1)^n*(sqrt(m) - 1) + sqrt(m) + 1) - 2)/(2*(m - 1)). It appears, for integer values of n >= 0 and m > 1, that it could be simplified in the integral domain a(n) = (m^(1 + floor(n/2)) - 1)/(m - 1). - Federico Provvedi, Nov 23 2018
From Werner Schulte, Mar 04 2019: (Start)
More generally: For some fixed integers q and r > 0 the expansion of A(q,r; x) = 1/((1-x)*(1-q*x^r)) generates coefficients a(q,r; n) = (q^(1+floor(n/r))-1)/(q-1) for n >= 0; the special case q = 1 leads to a(1,r; n) = 1 + floor(n/r).
The a(q,r; n) satisfy for n > r a linear recurrence equation with constant coefficients. The signature vector is given by the sum of two vectors v and w where v has terms 1 followed by r zeros, i.e., (1,0,0,...,0), and w has r-1 leading zeros followed by q and -q, i.e., (0,0,...,0,q,-q).
Let a_i(q,r; n) be the convolution inverse of a(q,r; n). The terms are given by the sum a_i(q,r; n) = b(n) + c(n) for n >= 0 where b(n) has terms 1 and -1 followed by infinitely zeros, i.e., (1,-1,0,0,0,...), and c(n) has r leading zeros followed by -q, q and infinitely zeros, i.e., (0,0,...,0,-q,q,0,0,0,...).
Here is an example for q = 3 and r = 5: The expansion of A(3,5; x) = 1/((1-x)*(1-3*x^5)) = Sum_{n>=0} a(3,5; n)*x^n generates the sequence of coefficients (a(3,5; n)) = (1,1,1,1,1,4,4,4,4,4,13,13,13,13,13,40,...) where r = 5 controls the repetition and q = 3 the different values.
The a(3,5; n) satisfy for n > 5 the linear recurrence equation with constant coefficients and signature (1,0,0,0,0,0) + (0,0,0,0,3,-3) = (1,0,0,0,3,-3).
The convolution inverse a_i(3,5; n) has terms (1,-1,0,0,0,0,0,0,0,...) + (0,0,0,0,0,-3,3,0,0,...) = (1,-1,0,0,0,-3,3,0,0,...).
For further examples and informations see A014983 (q,r = -3,1), A077925 (q,r = -2,1), A000035 (q,r = -1,1), A000012 (q,r = 0,1), A000027 (q,r = 1,1), A000225 (q,r = 2,1), A003462 (q,r = 3,1), A077953 (q,r = -2,2), A133872 (q,r = -1,2), A004526 (q,r = 1,2), A052551 (this sequence with q,r = 2,2), A077886 (q,r = -2,3), A088911 (q,r = -1,3), A002264 (q,r = 1,3) and A077885 (q,r = 2,3). The offsets might be different.
(End)
a(n) is the number of palindromes of length n over the alphabet {1,2} containing the letter 1. More generally, the number of palindromes of length n over the alphabet {1,2,...,k} containing the letter 1 is given by k^ceiling(n/2)-(k-1)^ceiling(n/2). - Sela Fried, Dec 10 2024

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Vincenzo Librandi, Table of n, a(n) for n = 0..2000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 488
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A000225, A077957, A136865, A289404, A289405, A032085, A050686.
Column 2 (offset by two) of A304972.
Cf. A000225 (oriented), A056326 (unoriented), and A122746(n-2) (chiral) for rows.
Cf. A056295 (oriented), A056357 (unoriented), and A059053 (chiral) for cycles.

Flat(List([1..21],n->[2^n-1,2^n-1])); # Muniru A Asiru, Oct 16 2018

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

spec := [S,{S=Prod(Sequence(Prod(Z,Union(Z,Z))),Sequence(Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

Table[StirlingS2[Floor[n/2] + 2, 2], {n, 0, 50}] (* Robert A. Russell, Dec 20 2017 *)
Drop[LinearRecurrence[{1, 2, -2}, {0, 1, 1}, 50], 1] (* Robert A. Russell, Oct 14 2018 *)
CoefficientList[Series[1/((1-x)*(1-2*x^2)), {x, 0, 50}], x] (* Stefano Spezia, Oct 16 2018 *)
2^(1+Floor[(Range[0,50])/2])-1 (* Federico Provvedi, Nov 22 2018 *)
((-1)^#(Sqrt[2]-1)+Sqrt[2]+1)2^((#-1)/2)-1&@Range[0, 50] (* Federico Provvedi, Nov 23 2018 *)

x='x+O('x^50); Vec(1/((1-x)*(1-2*x^2))) \\ Altug Alkan, Mar 19 2018

[2^(floor(n/2)) -1 for n in (2..50)] # G. C. Greubel, Mar 04 2019

G.f.: 1/((1 - x)*(1 - 2*x^2)).
Recurrence: a(1) = 1, a(0) = 1, -2*a(n) - 1 + a(n+2) = 0.
a(n) = -1 + Sum((1/2)*(1 + 2*alpha)*alpha^(-1 - n)) where the sum is over alpha = the two roots of -1 + 2*x^2.
a(n) = A016116(n+2) - 1. - R. J. Mathar, Jun 15 2009
a(n) = A060546(n+1) - 1. - Filip Zaludek, Dec 10 2016
From Robert A. Russell, Oct 15 2018: (Start)
a(n-2) = S2(floor(n/2)+1,2), where S2 is the Stirling subset number A008277.
a(n-2) = 2*A056326(n) - A000225(n) = A000225(n) - 2*A122746(n-2) = A056326(n) - A122746(n-2).
a(n-2) = 2*A056357(n) - A056295(n) = A056295(n) - 2*A059053(n) = A056357(n) - A059053(n). (End)
From Federico Provvedi, Nov 22 2018: (Start)
a(n) = 2^( 1 + floor(n/2) ) - 1.
a(n) = ( (-1)^n*(sqrt(2)-1) + sqrt(2) + 1 ) * 2^( (n - 1)/2 ) - 1.  (End)
E.g.f.: 2*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x) - cosh(x) - sinh(x). - Franck Maminirina Ramaharo, Nov 23 2018

More terms from James Sellers, Jun 06 2000

A060482 New record highs reached in A060030.

Original entry on oeis.org

1, 2, 3, 5, 9, 13, 21, 29, 45, 61, 93, 125, 189, 253, 381, 509, 765, 1021, 1533, 2045, 3069, 4093, 6141, 8189, 12285, 16381, 24573, 32765, 49149, 65533, 98301, 131069, 196605, 262141, 393213, 524285, 786429, 1048573, 1572861, 2097149, 3145725, 4194301, 6291453

Offset: 1

Henry Bottomley, Mar 19 2001

Harry J. Smith, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A060013, A060030.

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

LinearRecurrence[{1,2,-2},{1,2,3,5,9},50] (* Harvey P. Dale, Sep 11 2016 *)

{ for (n=1, 1000, if (n%2==0, m=n/2; a=2^(m + 1) - 3, m=(n - 1)/2; a=3*2^m - 3); if (n<3, a=n); write("b060482.txt", n, " ", a); ) } \\ Harry J. Smith, Jul 05 2009

a(n) = a(n-1) + 2^((n-1)/2) = 2*a(n-2) + 3 = a(n-1) + A016116(n-1) = A027383(n-1) - 1 = 2*A027383(n-3) + 1 = 4*A052955(n-4) + 1. a(2n) = 2^(n+1) - 3; a(2n+1) = 3*2^n - 3.
From Colin Barker, Jan 12 2013: (Start)
a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) for n > 5.
G.f.: x*(2*x^4-x^2+x+1) / ((x-1)*(2*x^2-1)). (End)
E.g.f.: 1 + x + x^2/2 - 3*cosh(x) + 2*cosh(sqrt(2)*x) - 3*sinh(x) + 3*sinh(sqrt(2)*x)/sqrt(2). - Stefano Spezia, Jul 25 2024

A136252 a(n) = a(n-1) + 2a(n-2) - 2a(n-3).

Original entry on oeis.org

1, 3, 5, 9, 13, 21, 29, 45, 61, 93, 125, 189, 253, 381, 509, 765, 1021, 1533, 2045, 3069, 4093, 6141, 8189, 12285, 16381, 24573, 32765, 49149, 65533, 98301, 131069, 196605, 262141, 393213, 524285, 786429, 1048573, 1572861, 2097149, 3145725, 4194301, 6291453, 8388605

Offset: 0

Paul Curtz, Mar 17 2008

For n >= 2, number of n X n arrays with values that are squares of integers, having all 2 X 2 subblocks summing to 4. - R. H. Hardin, Apr 03 2009

Number of moves required in 4-peg Tower of Hanoi solution using a (suboptimal) recursive algorithm: Move (n-2) disks, move bottom 2 disks, move (n-2) disks. Cf. A007664. - Toby Gottfried, Nov 29 2010

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Same recurrence as in A135530.
Partial sums of A163403.
A060482 without the term 2.
Cf. A007664 (Optimal 4-peg Tower of Hanoi).
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

a:=proc(n) options operator,arrow: 2^((1/2)*n-1)*(4+4*(-1)^n+3*sqrt(2)*(1-(-1)^n))-3 end proc: seq(a(n),n=0..40); # Emeric Deutsch, Mar 31 2008

LinearRecurrence[{1, 2, -2}, {1, 3, 5}, 100] (* G. C. Greubel, Feb 18 2017 *)

x='x+O('x^50); Vec((1+2*x)/((1-x)*(1-2*x^2))) \\ G. C. Greubel, Feb 18 2017

a(n) = 2^((1/2)*n-1)*(4 + 4(-1)^n + 3*sqrt(2)*(1-(-1)^n)) - 3. - Emeric Deutsch, Mar 31 2008
G.f.: (1+2*x)/((1-x)*(1-2*x^2)). - Jaume Oliver Lafont, Aug 30 2009
a(n) = 2*a(n-2) + 3; first differences are powers of 2, occurring in pairs. - Toby Gottfried, Nov 29 2010
a(n) = A027383(n+1) - 1. - Jason Kimberley, Nov 01 2011
a(2n+1) = (a(2n) + a(2n+2))/2. - Richard R. Forberg, Nov 30 2013
E.g.f.: 4*cosh(sqrt(2)*x) + 3*sqrt(2)*sinh(sqrt(2)*x) - 3*cosh(x) - 3*sinh(x). - Stefano Spezia, May 13 2023

Edited by N. J. A. Sloane, Apr 18 2008

More terms from Emeric Deutsch, Mar 31 2008

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

A027383 a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A029744 Numbers of the form 2^n or 3*2^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scheme

Formula

Extensions

A005418 Number of (n-1)-bead black-white reversible strings; also binary grids; also row sums of Losanitsch's triangle A034851; also number of caterpillar graphs on n+2 vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A052955 a(2n) = 2*2^n - 1, a(2n+1) = 3*2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.

A052551 Expansion of 1/((1 - x)(1 - 2x^2)).

A136252 a(n) = a(n-1) + 2a(n-2) - 2a(n-3).

A152166 a(2n) = 2^n; a(2n+1) = -(2^(n+1)).