A033484 -id:A033484 - cp's OEIS frontend

A000918 a(n) = 2^n - 2.

-1, 0, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534, 131070, 262142, 524286, 1048574, 2097150, 4194302, 8388606, 16777214, 33554430, 67108862, 134217726, 268435454, 536870910, 1073741822, 2147483646, 4294967294, 8589934590, 17179869182, 34359738366, 68719476734, 137438953470

Offset: 0

N. J. A. Sloane

For n > 1, a(n) is the expected number of tosses of a fair coin to get n-1 consecutive heads. - Pratik Poddar, Feb 04 2011
For n > 2, Sum_{k=1..a(n)} (-1)^binomial(n, k) = A064405(a(n)) + 1 = 0. - Benoit Cloitre, Oct 18 2002
For n > 0, the number of nonempty proper subsets of an n-element set. - Ross La Haye, Feb 07 2004
Numbers j such that abs( Sum_{k=0..j} (-1)^binomial(j, k)*binomial(j + k, j - k) ) = 1. - Benoit Cloitre, Jul 03 2004
For n > 2 this formula also counts edge-rooted forests in a cycle of length n. - Woong Kook (andrewk(AT)math.uri.edu), Sep 08 2004
For n >= 1, conjectured to be the number of integers from 0 to (10^n)-1 that lack 0, 1, 2, 3, 4, 5, 6 and 7 as a digit. - Alexandre Wajnberg, Apr 25 2005
Beginning with a(2) = 2, these are the partial sums of the subsequence of A000079 = 2^n beginning with A000079(1) = 2. Hence for n >= 2 a(n) is the smallest possible sum of exactly one prime, one semiprime, one triprime, ... and one product of exactly n-1 primes. A060389 (partial sums of the primorials, A002110, beginning with A002110(1)=2) is the analog when all the almost primes must also be squarefree. - Rick L. Shepherd, May 20 2005
From the second term on (n >= 1), the binary representation of these numbers is a 0 preceded by (n - 1) 1's. This pattern (0)111...1110 is the "opposite" of the binary 2^n+1: 1000...0001 (cf. A000051). - Alexandre Wajnberg, May 31 2005
The numbers 2^n - 2 (n >= 2) give the positions of 0's in A110146. Also numbers k such that k^(k + 1) = 0 mod (k + 2). - Zak Seidov, Feb 20 2006
Partial sums of A155559. - Zerinvary Lajos, Oct 03 2007
Number of surjections from an n-element set onto a two-element set, with n >= 2. - Mohamed Bouhamida, Dec 15 2007
It appears that these are the numbers n such that 3*A135013(n) = n*(n + 1), thus answering Problem 2 on the Mathematical Olympiad Foundation of Japan, Final Round Problems, Feb 11 1993 (see link Japanese Mathematical Olympiad).
Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if x is a proper subset of y or y is a proper subset of x and x and y are disjoint. Then a(n+1) = |R|. - Ross La Haye, Mar 19 2009
The permutohedron Pi_n has 2^n - 2 facets [Pashkovich]. - Jonathan Vos Post, Dec 17 2009
First differences of A005803. - Reinhard Zumkeller, Oct 12 2011
For n >= 1, a(n + 1) is the smallest even number with bit sum n. Cf. A069532. - Jason Kimberley, Nov 01 2011
a(n) is the number of branches of a complete binary tree of n levels. - Denis Lorrain, Dec 16 2011
For n>=1, a(n) is the number of length-n words on alphabet {1,2,3} such that the gap(w)=1. For a word w the gap g(w) is the number of parts missing between the minimal and maximal elements of w. Generally for words on alphabet {1,2,...,m} with g(w)=g>0 the e.g.f. is Sum_{k=g+2..m} (m - k + 1)*binomial((k - 2),g)*(exp(x) - 1)^(k - g). a(3)=6 because we have: 113, 131, 133, 311, 313, 331. Cf. A240506. See the Heubach/Mansour reference. - Geoffrey Critzer, Apr 13 2014
For n > 0, a(n) is the minimal number of internal nodes of a red-black tree of height 2*n-2. See the Oct 02 2015 comment under A027383. - Herbert Eberle, Oct 02 2015
Conjecture: For n>0, a(n) is the least m such that A007814(A000108(m)) = n-1. - L. Edson Jeffery, Nov 27 2015
Actually this follows from the procedure for determining the multiplicity of prime p in C(n) given in A000108 by Franklin T. Adams-Watters: For p=2, the multiplicity is the number of 1 digits minus 1 in the binary representation of n+1. Obviously, the smallest k achieving "number of 1 digits" = k is 2^k-1. Therefore C(2^k-2) is divisible by 2^(k-1) for k > 0 and there is no smaller m for which 2^(k-1) divides C(m) proving the conjecture. - Peter Schorn, Feb 16 2020
For n >= 0, a(n) is the largest number you can write in bijective base-2 (a.k.a. the dyadic system, A007931) with n digits. - Harald Korneliussen, May 18 2019
The terms of this sequence are also the sum of the terms in each row of Pascal's triangle other than the ones. - Harvey P. Dale, Apr 19 2020
For n > 1, binomial(a(n),k) is odd if and only if k is even. - Charlie Marion, Dec 22 2020
For n >= 2, a(n+1) is the number of n X n arrays of 0's and 1's with every 2 X 2 square having density exactly 2. - David desJardins, Oct 27 2022
For n >= 1, a(n+1) is the number of roots of unity in the unique degree-n unramified extension of the 2-adic field Q_2. Note that for each p, the unique degree-n unramified extension of Q_p is the splitting field of x^(p^n) - x, hence containing p^n - 1 roots of unity for p > 2 and 2*(2^n - 1) for p = 2. - Jianing Song, Nov 08 2022

			a(4) = 14 because the 14 = 6 + 4 + 4 rationals (in lowest terms) for n = 3 are (see the Jun 14 2017 formula above): 1/2, 1, 3/2, 2, 5/2, 3; 1/4, 3/4, 5/4, 7/4; 1/8, 3/8, 5/8, 7/8. - _Wolfdieter Lang_, Jun 14 2017

H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 212.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134. - Mohammad K. Azarian, Oct 27 2011
S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009 page 86, Exercise 3.16.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911, p. 31.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
O. Bagdasar, On some functions involving the lcm and gcd of integer tuples, Scientific Publications of the State University of Novi Pazar, Appl. Maths. Inform. and Mech., Vol. 6, 2 (2014), 91--100.
S. Bilotta, E. Grazzini, and E. Pergola, Enumeration of Two Particular Sets of Minimal Permutations, J. Int. Seq. 18 (2015) 15.10.2
R. B. Campbell, The effect of inbreeding constraints and offspring distribution on time to the most recent common ancestor, Journal of Theoretical Biology, Volume 382, 7 October 2015, Pages 74-80.
Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012
M. A. Hill, M. J. Hopkins and D. C. Ravenel, On the non-existence of elements of Kervaire invariant one. - _N. J. A. Sloane_, Sep 27 2010
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 77
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Milan Janjic and B. Petkovic, A Counting Function, arXiv 1301.4550 [math.CO], 2013.
Japanese Mathematical Olympiad 1993, Final Round - Problem 2, Feb 11 1993.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015.
Kanstantsin Pashkovich, Symmetry in Extended Formulations of the Permutahedron [sic], arXiv:0912.3446 [math.CO], 2009-2013. [_Jonathan Vos Post_, Dec 17 2009]
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
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
Pratik Poddar, Consecutive Heads Puzzle, Oct 2009.
H. P. Robinson, Letter to N. J. A. Sloane, Sep 1975
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911. [Annotated scans of pages 30-33 only]
Eric Weisstein's World of Mathematics, Sphere Line Picking
Index entries for linear recurrences with constant coefficients, signature (3,-2).
Index to sequences related to Olympiads.

Row sums of triangle A026998.
Cf. A000919, A001117, A001118, A095121, A110146.
Cf. A033484, A000225, A000325, A095151, A125128.
Cf. A058809 (3^n-3, n>0).

a000918 = (subtract 2) . (2 ^)
a000918_list = iterate ((subtract 2) . (* 2) . (+ 2)) (- 1)
-- Reinhard Zumkeller, Apr 23 2013

[2^n - 2: n in [0..40]]; // Vincenzo Librandi, Jun 23 2011

Maple
```
seq(2^n-2,n=0..20) ;
```

Table[2^n - 2, {n, 0, 29}] (* Alonso del Arte, Dec 01 2012 *)

a(n)=2^n-2 \\ Charles R Greathouse IV, Jun 16 2011

def A000918(n): return (1<Chai Wah Wu, Jun 10 2025

a(n) = 2*A000225(n-1).
G.f.: 1/(1 - 2*x) - 2/(1 - x), e.g.f.: (e^x - 1)^2 - 1. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001
For n >= 1, a(n) = A008970(n + 1, 2). - Philippe Deléham, Feb 21 2004
G.f.: (3*x - 1)/((2*x - 1)*(x - 1)). - Simon Plouffe in his 1992 dissertation for the sequence without the leading -1
a(n) = 2*a(n - 1) + 2. - Alexandre Wajnberg, Apr 25 2005
a(n) = A000079(n) - 2. - Omar E. Pol, Dec 16 2008
a(n) = A058896(n)/A052548(n). - Reinhard Zumkeller, Feb 14 2009
a(n) = A164874(n - 1, n - 1) for n > 1. - Reinhard Zumkeller, Aug 29 2009
a(n) = A173787(n,1); a(n) = A028399(2*n)/A052548(n), n > 0. - Reinhard Zumkeller, Feb 28 2010
a(n + 1) = A027383(2*n - 1). - Jason Kimberley, Nov 02 2011
G.f.: U(0) - 1, where U(k) = 1 + x/(2^k + 2^k/(x - 1 - x^2*2^(k + 1)/(x*2^(k + 1) - (k + 1)/U(k + 1) ))); (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Dec 01 2012
a(n+1) is the sum of row n in triangle A051601. - Reinhard Zumkeller, Aug 05 2013
a(n+1) = A127330(n,0). - Reinhard Zumkeller, Nov 16 2013
a(n) = Sum_{k=1..n-1} binomial(n, k) for n > 0. - Dan McCandless, Nov 14 2015
From Miquel Cerda, Aug 16 2016: (Start)
a(n) = A000225(n) - 1.
a(n) = A125128(n-1) - A000325(n).
a(n) = A095151(n) - A125128(n) - 1. (End)
a(n+1) = 2*(n + Sum_{j=1..n-1} (n-j)*2^(j-1)), n >= 1. This is the number of the rationals k/2, k = 1..2*n for n >= 1 and (2*k+1)/2^j for j = 2..n, n >= 2, and 2*k+1 < n-(j-1). See the example for n = 3 below. Motivated by the proposal A287012 by Mark Rickert. - Wolfdieter Lang, Jun 14 2017

Maple programs fixed by Vaclav Kotesovec, Dec 13 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

A055010 a(0) = 0; for n > 0, a(n) = 3*2^(n-1) - 1.

Original entry on oeis.org

0, 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 12287, 24575, 49151, 98303, 196607, 393215, 786431, 1572863, 3145727, 6291455, 12582911, 25165823, 50331647, 100663295, 201326591, 402653183, 805306367, 1610612735, 3221225471, 6442450943, 12884901887

Offset: 0

Henry Bottomley, May 31 2000

Apart from leading term (which should really be 3/2), same as A083329.
Written in binary, a(n) is 1011111...1.
The sequence 2, 5, 11, 23, 47, 95, ... apparently gives values of n such that Nim-factorial(n) = 2. Cf. A059970. However, compare A060152. More work is needed! - John W. Layman, Mar 09 2001
With offset 1, number of (132,3412)-avoiding two-stack sortable permutations.
Number of descents after n+1 iterations of morphism A007413.
a(n) = A164874(n,1), n>0; subsequence of A030130. - Reinhard Zumkeller, Aug 29 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=[i,i]:=1, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^n*charpoly(A,-1). - Milan Janjic, Jan 24 2010
a(n) is the total number of records over all length n binary words. A record in a word a_1,a_2,...,a_n is a letter a_j that is larger than all the preceding letters. That is, a_j>a_i for all iGeoffrey Critzer, Jul 18 2020
Called Thabit numbers after the Syrian mathematician Thābit ibn Qurra (826 or 836 - 901). - Amiram Eldar, Jun 08 2021
a(n) is the number of objects in a pile that represents a losing position in a Nim game, where a player must select at least one object but not more than half of the remaining objects, on their turn. - Kiran Ananthpur Bacche, Feb 03 2025

			a(3) = 3*2^2 - 1 = 3*4 - 1 = 11.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Eric S. Egge and Toufik Mansour, 132-avoiding Two-stack Sortable Permutations, Fibonacci Numbers, and Pell Numbers, arXiv:math/0205206 [math.CO], 2002.
Sergey Kitaev and Toufik Mansour, Counting the occurrences of generalized patterns in words generated by a morphism, arXiv:math/0210170 [math.CO], 2002.
Hunar Sherzad Taher and Saroj Kumar Dash, On sums of k-generalized Fibonacci and k-generalized Lucas numbers as first and second kinds of Thabit numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 3, 448-459. See p. 2.
Eric Weisstein's World of Mathematics, Thabit ibn Kurrah Number.
Wikipedia, Thabit number.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A007505 for primes in this sequence. Apart from initial term, same as A052940 and A083329.
Cf. A266550 (independence number of the n-Mycielski graph).
Cf. A000079, A000225, A007283, A007413, A010036, A030130, A033484, A059970, A060152, A099258, A118654, A164874, A196168.

Concatenation([0], List([1..35], n-> 3*2^(n-1)-1)); # G. C. Greubel, May 06 2019

[Floor(3*2^(n-1) - 1): n in [0..35]]; // Vincenzo Librandi, May 18 2011

Join[{0},3*2^Range[0,34]-1] (* Harvey P. Dale, May 05 2013 *)

a(n)=3*2^n\2 - 1 \\ Charles R Greathouse IV, Apr 08 2016

[0]+[3*2^(n-1)-1 for n in (1..35)] # G. C. Greubel, May 06 2019

a(n) = A118654(n-1, 4), for n > 0.
a(n) = 2*a(n-1) + 1 = a(n-1) + A007283(n-1) = A007283(n)-1 = A000079(n) + A000225(n + 1) = A000079(n + 1) + A000225(n) = 3*A000079(n) - 1 = 3*A000225(n) + 2.
a(n) = A010036(n)/2^(n-1). - Philippe Deléham, Feb 20 2004
a(n) = A099258(A033484(n)-1) = floor(A033484(n)/2). - Reinhard Zumkeller, Oct 09 2004
G.f.: x*(2-x)/((1-x)*(1-2*x)). - Philippe Deléham, Oct 04 2011
a(n+1) = A196168(A000079(n)). - Reinhard Zumkeller, Oct 28 2011
E.g.f.: (3*exp(2*x) - 2*exp(x) - 1)/2. - Stefano Spezia, Sep 14 2024

A068156 G.f.: (x+2)(x+1)/((x-1)(x-2)) = Sum_{n>=0} a(n)*(x/2)^n.

Original entry on oeis.org

1, 3, 9, 21, 45, 93, 189, 381, 765, 1533, 3069, 6141, 12285, 24573, 49149, 98301, 196605, 393213, 786429, 1572861, 3145725, 6291453, 12582909, 25165821, 50331645, 100663293, 201326589, 402653181, 805306365, 1610612733

Offset: 0

Benoit Cloitre, Mar 12 2002

Number of moves to solve Hard Pagoda puzzle.
Partial sums of A111286. Binomial transform of (1,2,4,2,4,2,4 ....). - Paul Barry, Feb 28 2003
Warren W. Kokko writes that this sequence also appears to give the number of scoring sequences for the Racer Dice Game with n dice. - N. J. A. Sloane, Feb 24 2015
From Michel Lagneau, Apr 27 2015: (Start)
For n > 0, a(n) is the number of identical bowls having the same weight except for one which has a higher weight than the others which are identifiable by a weighing machine using n weighings.
Example: a(2)=9 because two weighings are sufficient:
Start with 9 bowls;
Step 1: remove 3 bowls => there are still 6 bowls;
Step 2: first weighing of 6 bowls (3 bowls on each side of the weighing machine);
Step 3: if the machine is in equilibrium, we find immediately the unknown bowl with a second weighing from the first 3 removing bowls. Else, we find immediately the unknown bowl with a second weighing from the 3 heaviest bowls.
Note: If the unknown bowl has a lower weight, the reasoning is the same, but it is necessary to know whether the unknown bowl is heavier or lighter.
In the general case, we always remove 3 bowls in step 1.
(End)
The number of ternary words of length n that avoid {11-2,22-1}. G.f. [1+(k-1)*x^2]/[1-k*x+(k-1)*x^2] at k=3. [Theorem 7.93 by Heubach and Mansour]. - R. J. Mathar, May 22 2016
Apart from the first term, column 2 of A222057. - Anton Zakharov, Oct 27 2016

Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.
Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.
S. Heubach, T. Mansour, in Combinatorics of Compositions and words, Discr. Math. Applicat. (ed by K H Rosen), CRC Press 2010, p 300.
Warren W. Kokko, The Racer Dice Game, Manuscript, 2015.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Artur Schaefer, Endomorphisms of The Hamming Graph and Related Graphs, arXiv preprint arXiv:1602.02186 [math.CO], 2016. See Table Remark 4.5.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

A diagonal of A233308 (for n > 1).

Cf. A000079.

[3*2^n+0^n-3 : n in [0..30]]; // Vincenzo Librandi, Nov 11 2011

Join[{1}, LinearRecurrence[{3, -2}, {3, 9}, 30]] (* Jean-François Alcover, Jan 08 2019 *)
CoefficientList[Series[(1+2x^2)/((1-2x)(1-x)),{x,0,40}],x] (* Harvey P. Dale, Jan 02 2022 *)

def a(n): return 3*2**n+0**n-3 # Torlach Rush, Jan 09 2025

a(0) = 1, a(n) = A060482(2n+1). For n > 0, a(n+1) = 2*a(n)+3.
G.f.: (1+2*x^2)/((1-2*x)*(1-x)). - Paul Barry, Feb 28 2003
a(n) = 3*2^n+0^n-3. - Paul Barry, Sep 04 2003
a(n) = A099257(A033484(n)+1) = 2*A033484(n) + 1. - Reinhard Zumkeller, Oct 09 2004
a(n) = 3*a(n-1) - 2*a(n-2), n > 1. - Vincenzo Librandi, Nov 11 2011
a(n) = a(n-1)+ 3*2^(n-1); a(1)=3. - Ctibor O. Zizka, Apr 17 2008
E.g.f.: 1 + 3*(exp(x) - 1)*exp(x). - Ilya Gutkovskiy, May 22 2016

A112468 Riordan array (1/(1-x), x/(1+x)).

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, -1, 1, 1, 0, 2, -2, 1, 1, 1, -2, 4, -3, 1, 1, 0, 3, -6, 7, -4, 1, 1, 1, -3, 9, -13, 11, -5, 1, 1, 0, 4, -12, 22, -24, 16, -6, 1, 1, 1, -4, 16, -34, 46, -40, 22, -7, 1, 1, 0, 5, -20, 50, -80, 86, -62, 29, -8, 1, 1, 1, -5, 25, -70, 130, -166, 148, -91, 37, -9, 1, 1, 0, 6, -30, 95, -200, 296, -314, 239, -128, 46, -10, 1

Offset: 0

Paul Barry, Sep 06 2005

Row sums are A040000. Diagonal sums are A112469. Inverse is A112467. Row sums of k-th power are 1, k+1, k+1, k+1, .... Note that C(n,k) = Sum_{j=0..n-k} C(n-j-1, n-k-j).
Equals row reversal of triangle A112555 up to sign, where log(A112555) = A112555 - I. Unsigned row sums equals A052953 (Jacobsthal numbers + 1). Central terms of even-indexed rows are a signed version of A072547. Sums of squared terms in rows yields A112556, which equals the first differences of the unsigned central terms. - Paul D. Hanna, Jan 20 2006
Sum_{k=0..n} T(n,k)*x^k = A000012(n), A040000(n), A005408(n), A033484(n), A048473(n), A020989(n), A057651(n), A061801(n), A238275(n), A238276(n), A138894(n), A090843(n), A199023(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 respectively (see the square array in A112739). - Philippe Deléham, Feb 22 2014

			Triangle starts
  1;
  1,  1;
  1,  0,  1;
  1,  1, -1,  1;
  1,  0,  2, -2,  1;
  1,  1, -2,  4, -3,  1;
  1,  0,  3, -6,  7, -4,  1;
Matrix log begins:
  0;
  1,  0;
  1,  0,  0;
  1,  1, -1,  0;
  1,  1,  1, -2,  0;
  1,  1,  1,  1, -3,  0; ...
Production matrix begins
  1,  1,
  0, -1,  1,
  0,  0, -1,  1,
  0,  0,  0, -1,  1,
  0,  0,  0,  0, -1,  1,
  0,  0,  0,  0,  0, -1,  1,
  0,  0,  0,  0,  0,  0, -1,  1.
- _Paul Barry_, Apr 08 2011

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
H. Belbachir and F. Bencherif, On some properties of bivariate Fibonacci and Lucas Polynomials, JIS 11 (2008) 08.2.6.
Hacene Belbachir and Athmane Benmezai, Expansion of Fibonacci and Lucas Polynomials: An Answer to Prodinger's Question, Journal of Integer Sequences, Vol. 15 (2012), #12.7.6.
Emeric Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Applied Mathematics, 34 (2005) pp. 101-122.
Kyu-Hwan Lee and Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
H. Prodinger, On the expansion of Fibonacci and Lucas Polynomials, JIS 12 (2009) 09.1.6.

Cf. A174294, A174295, A174296, A174297. - Mats Granvik, Mar 15 2010
Cf. A072547 (central terms), A112555 (reversed rows), A112465, A052953, A112556, A112739, A119258.
See A279006 for another version.

T:= function(n,k)
    if k=0 or k=n then return 1;
    else return T(n-1,k-1) - T(n-1,k);
    fi;
  end;
Flat(List([0..12], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Nov 13 2019

a112468 n k = a112468_tabl !! n !! k
a112468_row n = a112468_tabl !! n
a112468_tabl = iterate (\xs -> zipWith (-) ([2] ++ xs) (xs ++ [0])) [1]
-- Reinhard Zumkeller, Jan 03 2014

function T(n,k)
  if k eq 0 or k eq n then return 1;
  else return T(n-1,k-1) - T(n-1,k);
  end if;
  return T;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 13 2019

T := (n,k,m) -> (1-m)^(-n+k)-m^(k+1)*pochhammer(n-k,k+1)*hypergeom( [1,n+1],[k+2],m)/(k+1)!; A112468 := (n,k) -> T(n,n-k,-1);
seq(print(seq(simplify(A112468(n,k)),k=0..n)),n=0..10); # Peter Luschny, Jul 25 2014

T[n_, 0] = 1; T[n_, n_] = 1; T[n_, k_ ]:= T[n, k] = T[n-1, k-1] - T[n-1, k]; Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* Jean-François Alcover, Mar 06 2013 *)

{T(n,k)=local(m=1,x=X+X*O(X^n),y=Y+Y*O(Y^k)); polcoeff(polcoeff((1+(m-1)*x)*(1+m*x)/(1+m*x-x*y)/(1-x),n,X),k,Y)} \\ Paul D. Hanna, Jan 20 2006

T(n,k) = if(k==0 || k==n, 1, T(n-1, k-1) - T(n-1, k)); \\ G. C. Greubel, Nov 13 2019

@CachedFunction
def T(n, k):
    if (k<0 or n<0): return 0
    elif (k==0 or k==n): return 1
    else: return T(n-1, k-1) - T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Nov 13 2019

Triangle T(n,k) read by rows: T(n,0)=1, T(n,k) = T(n-1,k-1) - T(n-1,k). - Mats Granvik, Mar 15 2010
Number triangle T(n, k)= Sum_{j=0..n-k} C(n-j-1, n-k-j)*(-1)^(n-k-j).
G.f. of matrix power T^m: (1+(m-1)*x)*(1+m*x)/(1+m*x-x*y)/(1-x). G.f. of matrix log: x*(1-2*x*y+x^2*y)/(1-x*y)^2/(1-x). - Paul D. Hanna, Jan 20 2006
T(n, k) = R(n,n-k,-1) where R(n,k,m) = (1-m)^(-n+k)-m^(k+1)*Pochhammer(n-k,k+1)*hyper2F1([1,n+1],[k+2],m)/(k+1)!. - Peter Luschny, Jul 25 2014

A153893 a(n) = 3*2^n - 1.

Original entry on oeis.org

2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 12287, 24575, 49151, 98303, 196607, 393215, 786431, 1572863, 3145727, 6291455, 12582911, 25165823, 50331647, 100663295, 201326591, 402653183, 805306367, 1610612735, 3221225471

Offset: 0

Vladimir Joseph Stephan Orlovsky, Jan 03 2009

A020944(a(n)) = 0. - Reinhard Zumkeller, Mar 13 2011
a(n) + a(n-1)^2 is a perfect square. - Vincenzo Librandi, Oct 28 2011
Number of distinct continued fractions of n terms chosen from {1,2}. - Clark Kimberling, Jul 20 2015
Also, the decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 643", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. See A283508. - Robert Price, Mar 09 2017
This sequence has been used by the ninth-century mathematician Thabit ibn Qurra to devise the first method to construct amicable pairs (see Tattersall). - Stefano Spezia, Jul 18 2025

James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 138.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Gennady Eremin, Partitioning the set of natural numbers into Mersenne trees and into arithmetic progressions; Natural Matrix and Linnik's constant, arXiv:2405.16143 [math.CO], 2024. See pp. 2-5, 14.
Gennady Eremin, Infinite matrix of odd natural numbers. A bit about Sophie Germain prime numbers, arXiv:2501.17090 [math.GM], 2025. See pp. 3, 11.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A283508.

[3*2^n-1: n in [0..30]]; // Vincenzo Librandi, Oct 28 2011

Table[3*2^n - 1 , {n,0,25}] (* G. C. Greubel, Sep 01 2016 *)
LinearRecurrence[{3,-2},{2,5},40] (* Harvey P. Dale, Mar 01 2024 *)

a(n)=3*2^n-1 \\ Charles R Greathouse IV, Sep 24 2015

a(n) = a(n-1)*2 + 1, a(0)=2.
a(n) = A083329(n+1).
a(n) = A055010(n+1).
G.f.: (2 - x)/((1-x)(1-2x)). - R. J. Mathar, Feb 13 2009
a(n) = A083416(2n) = A033484(n) + 1. - Philippe Deléham, Apr 14 2013
From G. C. Greubel, Sep 01 2016: (Start)
a(n) = 3*a(n-1) - 2*a(n-2).
E.g.f.: 3*exp(2*x) - exp(x). (End)

Edited by N. J. A. Sloane, Feb 14 2009

A050488 a(n) = 3(2^n-1) - 2n.

Original entry on oeis.org

0, 1, 5, 15, 37, 83, 177, 367, 749, 1515, 3049, 6119, 12261, 24547, 49121, 98271, 196573, 393179, 786393, 1572823, 3145685, 6291411, 12582865, 25165775, 50331597, 100663243, 201326537, 402653127, 805306309, 1610612675, 3221225409, 6442450879, 12884901821, 25769803707

Offset: 0

James Sellers, Dec 26 1999

Number of words of length n+1 where first element is from {0,1,2}, other elements are from {0,1} and sequence does not decrease (for n=2 there are 3*2^2 sequences, but 000, 100, 110, 111, 200, 210, 211 decrease, so a(2) = 12-7 = 5).
Number of subgroups of C_(2^n) X C_(2^n) (see A060724).
Starting with 1 = row sums of triangle A054582. - Gary W. Adamson, Jun 23 2008
Starting with "1" equals the eigensequence of a triangle with integer squares (1, 4, 9, 16, ...) as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010
(1 + 2x + 2x^2 + 2x^3 + ...)*(1 + 3x + 7x^2 + 15x^3 + ...) = (1 + 5x + 15x^2 + 37x^3 + ...). - Gary W. Adamson, Mar 14 2012
The partial sums of A033484. - J. M. Bergot, Oct 03 2012
Binomial transform is 0, 1, 7, 33, ... (shifted A066810); inverse binomial transform is 0, 1, 3, 3, ... (3 repeated). - R. J. Mathar, Oct 05 2012
Define a triangle by T(n,0) = n*(n+1) + 1, T(n,n) = n + 1, and T(r,c) = T(r-1,c-1) + T(r-1,c) otherwise; then a(n+1) is the sum of the terms of row n. - J. M. Bergot, Mar 30 2013
Starting with "1" are also the antidiagonal sums of the array formed by partial sums of integer squares (1, 4, 9, 16, ...). - Luciano Ancora, Apr 24 2015
Sums of 2 adjacent terms in diagonal k=2 of Eulerian triangle A008292. I.e., T(n,2)+T(n-1,2) for n > 0. Also, 4th NW-SE diagonal of A126277. In other words, a(n) = A000295(n) + A000295(n+1). - Gregory Gerard Wojnar, Sep 30 2018

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Adam Buck, Jennifer Elder, Azia A. Figueroa, Pamela E. Harris, Kimberly Harry, and Anthony Simpson, Flattened Stirling Permutations, arXiv:2306.13034 [math.CO], 2023. See p. 14.
Tamas Lengyel, On p-adic properties of the Stirling numbers of the first kind, Journal of Number Theory, 148 (2015) 73-94.
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

A050487(2^m-1).
Equals (1/2) A051667.
Cf. A000079, A000225, A000295, A005408, A008292, A033484, A054852, A060724, A066810, A125165, A126277, A142963, A156919, A156920, A156925.

List([0..30],n->3*(2^n-1)-2*n); # Muniru A Asiru, Oct 26 2018

a050488 n = sum $ zipWith (*) a000079_list (reverse $ take n a005408_list)
-- Reinhard Zumkeller, Jul 24 2015

[3*(2^n-1) - 2*n: n in [0..30]]; // G. C. Greubel, Oct 23 2018

seq(coeff(series(x*(x+1)/((1-x)^2*(1-2*x)),x,n+1), x, n), n = 0 .. 30); # Muniru A Asiru, Oct 26 2018

Table[3(2^n-1)-2n,{n,0,30}] (* or *) LinearRecurrence[{4,-5,2}, {0,1,5}, 40] (* Harvey P. Dale, Apr 09 2018 *)

a(n)=3*(2^n-1)-2*n \\ Charles R Greathouse IV, Sep 24 2015

for n in range(0, 30): print(3*(2**n-1) - 2*n, end=', ') # Stefano Spezia, Oct 27 2018

Row sums of A125165: (1, 5, 15, 37, ...). Binomial transform of [1, 4, 6, 6, 6, ...] = [1, 5, 15, 37, ...]. 4th diagonal from the right of A126777 = (1, 5, 15, ...). - Gary W. Adamson, Dec 23 2006
a(n) = 2*a(n-1) + (2n-1). - Gary W. Adamson, Sep 30 2007
From Johannes W. Meijer, Feb 20 2009: (Start)
a(n+1) = A156920(n+1,1).
a(n+1) = A156919(n+1,1)/2^n.
a(n+1) = A142963(n+2,1)/2.
a(n) = 4a(n-1) - 5a(n-2) + 2a(n-3) for n>2 with a(0) = 0, a(1) = 1, a(2) = 5.
G.f.: z*(1+z)/((1-z)^2*(1-2*z)).
(End)
a(n) = 2*n + 2*a(n-1) - 1 (with a(0)=0). - Vincenzo Librandi, Aug 06 2010
a(n+1) = Sum_{k=0..n} A000079(k) * A005408(n-k), convolution of the powers of 2 with the odd numbers. - Reinhard Zumkeller, Mar 08 2012
E.g.f.: exp(x)*(3*exp(x) - 2*x - 3). - Stefano Spezia, May 15 2023

A175655 Eight bishops and one elephant on a 3 X 3 chessboard. G.f.: (1+x-5x^2)/(1-3x-x^2+6*x^3).

Original entry on oeis.org

1, 4, 8, 22, 50, 124, 290, 694, 1628, 3838, 8978, 21004, 48962, 114022, 265004, 615262, 1426658, 3305212, 7650722, 17697430, 40911740, 94528318, 218312114, 503994220, 1163124866, 2683496134, 6189647948, 14273690782

Offset: 0

Johannes W. Meijer, Aug 06 2010, Aug 10 2010

a(n) represents the number of n-move routes of a fairy chess piece starting in the central square (m = 5) on a 3 X 3 chessboard. This fairy chess piece behaves like a bishop on the eight side and corner squares but on the central square the bishop turns into a raging elephant, see A175654.
For the central square the 512 elephants lead to 46 different elephant sequences, see the cross-references for examples.
The sequence above corresponds to 16 A[5] vectors with decimal values 71, 77, 101, 197, 263, 269, 293, 323, 326, 329, 332, 353, 356, 389, 449 and 452. These vectors lead for the side squares to A000079 and for the corner squares to A175654.

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

Cf. Elephant sequences central square [decimal value A[5]]: A000007 [0], A000012 [16], A000045 [1], A011782 [2], A000079 [3], A003945 [42], A099036 [11], A175656 [7], A105476 [69], A168604 [26], A045891 [19], A078057 [21], A151821 [170], A175657 [43], 4*A172481 [15; n>=-1], A175655 [71, this sequence], 4*A026597 [325; n>=-1], A033484 [58], A087447 [27], A175658 [23], A026150 [85], A175661 [171], A036563 [186], A098156 [59], A046717 [341], 2*A001792 [187; n>=1 with a(0)=1], A175659 [343].

Cf. A000244, A006130, A075118, A175654.

I:=[1, 4, 8]; [n le 3 select I[n] else 3*Self(n-1)+Self(n-2)-6*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jul 21 2013

with(LinearAlgebra): nmax:=27; m:=5; A[5]:= [0,0,1,0,0,0,1,1,1]: A:=Matrix([[0,0,0,0,1,0,0,0,1], [0,0,0,1,0,1,0,0,0], [0,0,0,0,1,0,1,0,0], [0,1,0,0,0,0,0,1,0], A[5], [0,1,0,0,0,0,0,1,0], [0,0,1,0,1,0,0,0,0], [0,0,0,1,0,1,0,0,0], [1,0,0,0,1,0,0,0,0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax);

CoefficientList[Series[(1 + x - 5 x^2) / (1 - 3 x - x^2 + 6 x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Jul 21 2013 *)
LinearRecurrence[{3,1,-6},{1,4,8},40] (* Harvey P. Dale, Dec 25 2024 *)

a(n)=([0,1,0; 0,0,1; -6,1,3]^n*[1;4;8])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

G.f.: (1+x-5*x^2)/(1-3*x-x^2+6*x^3).
a(n) = 3*a(n-1) + a(n-2) - 6*a(n-3) with a(0)=1, a(1)=4 and a(2)=8.
a(n) = ((10+8*A)*A^(-n-1) + (10+8*B)*B^(-n-1))/13 - 2^n with A = (-1+sqrt(13))/6 and B = (-1-sqrt(13))/6.
Limit_{k->oo} a(n+k)/a(k) = (-1)^(n)*2*A000244(n)/(A075118(n)-A006130(n-1)*sqrt(13)).
E.g.f.: 2*exp(x/2)*(13*cosh(sqrt(13)*x/2) + 5*sqrt(13)*sinh(sqrt(13)*x/2))/13 - cosh(2*x) - sinh(2*x). - Stefano Spezia, Jan 31 2023

A104743 a(n) = 3^n + n.

Original entry on oeis.org

1, 4, 11, 30, 85, 248, 735, 2194, 6569, 19692, 59059, 177158, 531453, 1594336, 4782983, 14348922, 43046737, 129140180, 387420507, 1162261486, 3486784421, 10460353224, 31381059631, 94143178850, 282429536505, 847288609468

Offset: 0

Zak Seidov, Mar 23 2005

This sequence also describes the total number of moves solving (non-optimally) the [RED ; NEUTRAL ; NEUTRAL] or [NEUTRAL ; NEUTRAL ; BLUE] pre-colored Magnetic Tower of Hanoi puzzle (see the "CROSSREFS" in A183121). For other Magnetic Tower of Hanoi related sequences, cf. A183111 - A183125.

Form an infinite array with m(0,k) = 2*k+1 and m(n,k) = Sum_{r=0..n-1} m(r,k) + Sum_{c=0..k-1} m(n,c), being the sum of the terms above m(n,k) plus those terms to the left of m(n,k). The first row is A005408. The second row is A033484. The first column is A011782. The sum of the terms in the n-th antidiagonal is a(n). - J. M. Bergot, Jun 07 2013

G. C. Greubel, Table of n, a(n) for n = 0..1000
Uri Levy, The Magnetic Tower of Hanoi, arXiv:1003.0225 [math.CO], 2010.
Index entries for linear recurrences with constant coefficients, signature (5,-7,3).

Cf. A103537.

List([0..40], n-> 3^n +n ); # G. C. Greubel, May 21 2019

[3^n +n: n in [0..40]]; // G. C. Greubel, May 21 2019

Table[3^n +n, {n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Jan 18 2009, modified by G. C. Greubel, May 21 2019 *)
LinearRecurrence[{5,-7,3},{1,4,11},30] (* Harvey P. Dale, Aug 01 2020 *)

{a(n) = 3^n + n}; \\ G. C. Greubel, May 21 2019

[3^n +n for n in (0..40)] # G. C. Greubel, May 21 2019

a(n) = n + 3^n.
From Colin Barker, Jan 25 2012: (Start)
a(n) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3).
G.f.: (1+x)*(1-2*x) / ((1-3*x)*(1-x)^2). (End)
E.g.f.: x*exp(x) + exp(3*x). - G. C. Greubel, May 21 2019

More terms from Vladimir Joseph Stephan Orlovsky, Jan 18 2009

cp's OEIS Frontend

A099018 Duplicate of A033484.

Views

Author

Keywords

A000918 a(n) = 2^n - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

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

A055010 a(0) = 0; for n > 0, a(n) = 3*2^(n-1) - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A068156 G.f.: (x+2)*(x+1)/((x-1)*(x-2)) = Sum_{n>=0} a(n)*(x/2)^n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A112468 Riordan array (1/(1-x), x/(1+x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

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

A068156 G.f.: (x+2)(x+1)/((x-1)(x-2)) = Sum_{n>=0} a(n)*(x/2)^n.

A050488 a(n) = 3(2^n-1) - 2n.

A175655 Eight bishops and one elephant on a 3 X 3 chessboard. G.f.: (1+x-5x^2)/(1-3x-x^2+6*x^3).