A059570 -id:A059570 - cp's OEIS frontend

A001787 a(n) = n*2^(n-1).

0, 1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264, 24576, 53248, 114688, 245760, 524288, 1114112, 2359296, 4980736, 10485760, 22020096, 46137344, 96468992, 201326592, 419430400, 872415232, 1811939328, 3758096384, 7784628224, 16106127360, 33285996544

Offset: 0

N. J. A. Sloane

Number of edges in an n-dimensional hypercube.
Number of 132-avoiding permutations of [n+2] containing exactly one 123 pattern. - Emeric Deutsch, Jul 13 2001
Number of ways to place n-1 nonattacking kings on a 2 X 2(n-1) chessboard for n >= 2. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 22 2001
Arithmetic derivative of 2^n: a(n) = A003415(A000079(n)). - Reinhard Zumkeller, Feb 26 2002
(-1) times the determinant of matrix A_{i,j} = -|i-j|, 0 <= i,j <= n.
a(n) is the number of ones in binary numbers 1 to 111...1 (n bits). a(n) = A000337(n) - A000337(n-1) for n = 2,3,... . - Emeric Deutsch, May 24 2003
The number of 2 X n 0-1 matrices containing n+1 1's and having no zero row or column. The number of spanning trees of the complete bipartite graph K(2,n). This is the case m = 2 of K(m,n). See A072590. - W. Edwin Clark, May 27 2003
Binomial transform of 0,1,2,3,4,5,... (A001477). Without the initial 0, binomial transform of odd numbers.
With an additional leading zero, [0,0,1,4,...] this is the binomial transform of the integers repeated A004526. Its formula is then (2^n*(n-1) + 0^n)/4. - Paul Barry, May 20 2003
Number of zeros in all different (n+1)-bit integers. - Ralf Stephan, Aug 02 2003
From Lekraj Beedassy, Jun 03 2004: (Start)
Final element of a summation table (as opposed to a difference table) whose first row consists of integers 0 through n (or first n+1 nonnegative integers A001477); illustrating the case n=5:
   0   1   2   3   4   5
     1   3   5   7   9
       4   8  12  16
        12  20  28
          32  48
            80
and the final element is a(5)=80. (End)
This sequence and A001871 arise in counting ordered trees of height at most k where only the rightmost branch at the root actually achieves this height and the count is by the number of edges, with k = 3 for this sequence and k = 4 for A001871.
Let R be a binary relation on the power set P(A) of a set A having n = |A| elements such that for all elements x,y of P(A), xRy if x is a proper subset of y and there are no z in P(A) such that x is a proper subset of z and z is a proper subset of y. Then a(n) = |R|. - Ross La Haye, Sep 21 2004
Number of 2 X n binary matrices avoiding simultaneously the right-angled numbered polyomino patterns (ranpp) (00;1) and (10;1). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2, j1 < j2 and these elements are in same relative order as those in the triple (x,y,z). - Sergey Kitaev, Nov 11 2004
Number of subsequences 00 in all binary words of length n+1. Example: a(2)=4 because in 000,001,010,011,100,101,110,111 the sequence 00 occurs 4 times. - Emeric Deutsch, Apr 04 2005
If you expand the n-factor expression (a+1)*(b+1)*(c+1)*...*(z+1), there are a(n) variables in the result. For example, the 3-factor expression (a+1)*(b+1)*(c+1) expands to abc+ab+ac+bc+a+b+c+1 with a(3) = 12 variables. - David W. Wilson, May 08 2005
An inverse Chebyshev transform of n^2, where g(x)->(1/sqrt(1-4*x^2))*g(x*c(x^2)), c(x) the g.f. of A000108. - Paul Barry, May 13 2005
Sequences A018215 and A058962 interleaved. - Graeme McRae, Jul 12 2006
The number of never-decreasing positive integer sequences of length n with a maximum value of 2*n. - Ben Paul Thurston, Nov 13 2006
Total size of all the subsets of an n-element set. For example, a 2-element set has 1 subset of size 0, 2 subsets of size 1 and 1 of size 2. - Ross La Haye, Dec 30 2006
Convolution of the natural numbers [A000027] and A045623 beginning [0,1,2,5,...]. - Ross La Haye, Feb 03 2007
If M is the matrix (given by rows) [2,1;0,2] then the sequence gives the (1,2) entry in M^n. - Antonio M. Oller-Marcén, May 21 2007
If X_1,X_2,...,X_n is a partition of a 2n-set X into 2-blocks then, for n > 0, a(n) is equal to the number of (n+1)-subsets of X intersecting each X_i (i=1,2,...,n). - Milan Janjic, Jul 21 2007
Number of n-permutations of 3 objects u,v,w, with repetition allowed, containing exactly one u. Example: a(2)=4 because we have uv, vu, uw and wu. - Zerinvary Lajos, Dec 27 2007
A member of the family of sequences defined by a(n) = n*[c(1)*...*c(r)]^(n-1); c(i) integer. This sequence has c(1)=2, A027471 has c(1)=3. - Ctibor O. Zizka, Feb 23 2008
a(n) is the number of ways to split {1,2,...,n-1} into two (possibly empty) complementary intervals {1,2,...,i} and {i+1,i+2,...,n-1} and then select a subset from each interval. - Geoffrey Critzer, Jan 31 2009
Equals the Jacobsthal sequence A001045 convolved with A003945: (1, 3, 6, 12, ...). - Gary W. Adamson, May 23 2009
Starting with offset 1 = A059570: (1, 2, 6, 14, 34, ...) convolved with (1, 2, 2, 2, ...). - Gary W. Adamson, May 23 2009
Equals the first left hand column of A167591. - Johannes W. Meijer, Nov 12 2009
The number of tatami tilings of an n X n square with n monomers is n*2^(n-1). - Frank Ruskey, Sep 25 2010
Under T. D. Noe's variant of the hypersigma function, this sequence gives hypersigma(2^n): a(n) = A191161(A000079(n)). - Alonso del Arte, Nov 04 2011
Number of Dyck (n+2)-paths with exactly one valley at height 1 and no higher valley. - David Scambler, Nov 07 2011
Equals triangle A059260 * A016777 as a vector, where A016777 = (3n + 1): [1, 4, 7, 10, 13, ...]. - Gary W. Adamson, Mar 06 2012
Main transitions in systems of n particles with spin 1/2 (see A212697 with b=2). - Stanislav Sykora, May 25 2012
Let T(n,k) be the triangle with (first column) T(n,1) = 2*n-1 for n >= 1, otherwise T(n,k) = T(n,k-1) + T(n-1,k-1), then a(n) = T(n,n). - J. M. Bergot, Jan 17 2013
Sum of all parts of all compositions (ordered partitions) of n. The equivalent sequence for partitions is A066186. - Omar E. Pol, Aug 28 2013
Starting with a(1)=1: powers of 2 (A000079) self-convolved. - Bob Selcoe, Aug 05 2015
Coefficients of the series expansion of the normalized Schwarzian derivative -S{p(x)}/6 of the polynomial p(x) = -(x-x1)*(x-x2) with x1 + x2 = 1 (cf. A263646). - Tom Copeland, Nov 02 2015
a(n) is the number of North-East lattice paths from (0,0) to (n+1,n+1) that have exactly one east step below y = x-1 and no east steps above y = x+1. Details can be found in Pan and Remmel's link. - Ran Pan, Feb 03 2016
Also the number of maximal and maximum cliques in the n-hypercube graph for n > 0. - Eric W. Weisstein, Dec 01 2017
Let [n]={1,2,...,n}; then a(n-1) is the total number of elements missing in proper subsets of [n] that contain n to form [n]. For example, for n = 3, a(2) = 4 since the proper subsets of [3] that contain 3 are {3}, {1,3}, {2,3} and the total number of elements missing in these subsets to form [3] is 4:  2 in the first subset, 1 in the second, and 1 in the third. - Enrique Navarrete, Aug 08 2020
Number of 3-permutations of n elements avoiding the patterns 132, 231. See Bonichon and Sun. - Michel Marcus, Aug 19 2022

			a(2)=4 since 2314, 2341,3124 and 4123 are the only 132-avoiding permutations of 1234 containing exactly one increasing subsequence of length 3.
x + 4*x^2 + 12*x^3 + 32*x^4 + 80*x^5 + 192*x^6 + 448*x^7 + ...
a(5) = 1*0 + 5*1 + 10*2 + 10*3 + 5*4 + 1*5 = 80, with 1,5,10,10,5,1 the 5th row of Pascal's triangle. - _J. M. Bergot_, Apr 29 2014

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 796.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 131.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 282.
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).

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..500
Rémi Abgrall and Wasilij Barsukow, Extensions of Active Flux to arbitrary order of accuracy, arXiv:2208.14476 [math.NA], 2022.
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
F. S. Al-Kharousi, A. Umar, and M. M. Zubairu, On injective partial Catalan monoids, arXiv:2501.00285 [math.GR], 2024. See p. 9.
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
Douglas W. Bass and I. Hal Sudborough, Hamilton decompositions and (n/2)-factorizations of hypercubes, J. Graph Algor. Appl., Vol. 7, No. 1 (2003), pp. 79-98.
Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
Harlan J. Brothers, Pascal's Prism: Supplementary Material.
David Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Frank Ellermann, Illustration of binomial transforms
Mohamed Elkadi and Bernard Mourrain, Symbolic-numeric methods for solving polynomial equations and applications, Chap 3. of A. Dickenstein and I. Z. Emiris, eds., Solving Polynomial Equations, Springer, 2005, pp. 126-168. See p. 152.
Alejandro Erickson, Frank Ruskey, Mark Schurch and Jennifer Woodcock, Auspicious Tatami Mat Arrangements, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 288-297.
Samuele Giraudo, Pluriassociative algebras I: The pluriassociative operad, Advances in Applied Mathematics, Vol. 77 (2016), pp. 1-42, arXiv preprint, arXiv:1603.01040 [math.CO], 2016.
Frank A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424.
Frank A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424. (Annotated scanned copy)
Frank A. Haight, Letter to N. J. A. Sloane, n.d.
V. E. Hoggatt, Jr., Letter to N. J. A. Sloane, Jul 06, 1976
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=4, q=-4.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 408. (Dead link)
Milan Janjić, Two Enumerative Functions.
Milan Janjić and Boris Petković, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013.
Milan Janjić and Boris Petković, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5.
C. W. Jones, J. C. P. Miller, J. F. C. Conn, and R. C. Pankhurst, Tables of Chebyshev polynomials, Proc. Roy. Soc. Edinburgh. Sect. A. 62, (1946). 187-203.
Kenji Kimura and Saburo Higuchi, Monte Carlo estimation of the number of tatami tilings, International Journal of Modern Physics C, Vol. 27, No. 11 (2016), 1650128, arXiv preprint, arXiv:1509.05983 [cond-mat.stat-mech], 2015-2016, eq. (1).
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, University of Kentucky Research Reports (2004). (Dead link)
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012.
T. Y. Lam, On the diagonalization of quadratic forms, Math. Mag., 72 (1999), 231-235 (see page 234).
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. See Eq.(3).
Duško Letić, Nenad Cakić, Branko Davidović, Ivana Berković and Eleonora Desnica, Some certain properties of the generalized hypercubical functions, Advances in Difference Equations, 2011, 2011:60.
Toufik Mansour and Armend Sh. Shabani, Bargraphs in bargraphs, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 2763-2773.
Ronald Orozco López, Deformed Differential Calculus on Generalized Fibonacci Polynomials, arXiv:2211.04450 [math.CO], 2022.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Michael Penn, on the alternating sum of subsets, YouTube video, 2021.
Michael Penn, Rare proof of well-known sum, YouTube video, 2023.
Aleksandar Petojević, A Note about the Pochhammer Symbol, Mathematica Moravica, Vol. 12-1 (2008), 37-42.
Maxwell Phillips, Ahmed Ammar, and Firas Hassan, A Generalized Multi-Level Structure for High-Precision Binary Decoders, IEEE 67th Int'l Midwest Symp. Circ. Sys. (MWSCAS 2024), 42-46.
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.
Lara Pudwell, Nathan Chenette and Manda Riehl, Statistics on Hypercube Orientations, AMS Special Session on Experimental and Computer Assisted Mathematics, Joint Mathematics Meetings (Denver 2020).
Lara Pudwell, Connor Scholten, Tyler Schrock and Alexa Serrato, Noncontiguous pattern containment in binary trees, ISRN Comb. 2014, Article ID 316535, 8 p. (2014), chapter 5.2.
Aaron Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Math. and Theoret. Computer Sci., 3 (1999), 151-154.
Aaron Robertson, Herbert S. Wilf and Doron Zeilberger, Permutation patterns and continued fractions, Electr. J. Combin. 6, 1999, #R38.
Thomas Selig and Haoyue Zhu, Complete non-ambiguous trees and associated permutations: connections through the Abelian sandpile model, arXiv:2303.15756 [math.CO], 2023, see p. 16.
Jeffrey Shallit, Letter to N. J. A. Sloane Mar 14, 1979, concerning A001787, A005209, A005210, A005211.
Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
Eric Weisstein's World of Mathematics, Hypercube.
Eric Weisstein's World of Mathematics, Hypercube Graph.
Eric Weisstein's World of Mathematics, Leibniz Harmonic Triangle.
Eric Weisstein's World of Mathematics, Maximal Clique.
Eric Weisstein's World of Mathematics, Maximum Clique.
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,-4).

Three other versions, essentially identical, are A085750, A097067, A118442.
Partial sums of A001792.
A058922(n+1) = 4*A001787(n).
Equals A090802(n, 1).
Column k=1 of A038207.
Row sums of A003506, A322427, A322428.
Cf. A053109, A001788, A001789, A000337, A130300, A134083, A002064, A027471, A003945, A059670, A167591, A059260, A016777, A212697, A000079, A263646.

a001787 n = n * 2 ^ (n - 1)
a001787_list = zipWith (*) [0..] $ 0 : a000079_list
-- Reinhard Zumkeller, Jul 11 2014

[n*2^(n-1): n in [0..40]]; // Vincenzo Librandi, Feb 04 2016

spec := [S, {B=Set(Z, 0 <= card), S=Prod(Z, B, B)}, labeled]: seq(combstruct[count](spec, size=n), n=0..29); # Zerinvary Lajos, Oct 09 2006
A001787:=1/(2*z-1)^2; # Simon Plouffe in his 1992 dissertation, dropping the initial zero

Table[Sum[Binomial[n, i] i, {i, 0, n}], {n, 0, 30}] (* Geoffrey Critzer, Mar 18 2009 *)
f[n_] := n 2^(n - 1); f[Range[0, 40]] (* Vladimir Joseph Stephan Orlovsky, Feb 09 2011 *)
Array[# 2^(# - 1) &, 40, 0] (* Harvey P. Dale, Jul 26 2011 *)
Join[{0}, Table[n 2^(n - 1), {n, 20}]] (* Eric W. Weisstein, Dec 01 2017 *)
Join[{0}, LinearRecurrence[{4, -4}, {1, 4}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)
CoefficientList[Series[x/(-1 + 2 x)^2, {x, 0, 20}], x] (* Eric W. Weisstein, Dec 01 2017 *)

PARI
```
{a(n) = if( n<0, 0, n * 2^(n-1))}
```

concat(0, Vec(x/(1-2*x)^2 + O(x^50))) \\ Altug Alkan, Nov 03 2015

def A001787(n): return n*(1<Chai Wah Wu, Nov 14 2022

a(n) = Sum_{k=1..n} k*binomial(n, k). - Benoit Cloitre, Dec 06 2002
E.g.f.: x*exp(2x). - Paul Barry, Apr 10 2003
G.f.: x/(1-2*x)^2.
G.f.: x / (1 - 4*x / (1 + x / (1 - x))). - Michael Somos, Apr 07 2012
A108666(n) = Sum_{k=0..n} binomial(n, k)^2 * a(n). - Michael Somos, Apr 07 2012
PSumSIGN transform of A053220. PSumSIGN transform is A045883. Binomial transform is A027471(n+1). - Michael Somos, Jul 10 2003
Starting at a(1)=1, INVERT transform is A002450, INVERT transform of A049072, MOBIUS transform of A083413, PSUM transform is A000337, BINOMIAL transform is A081038, BINOMIAL transform of A005408. - Michael Somos, Apr 07 2012
a(n) = 2*a(n-1)+2^(n-1).
a(2*n) = n*4^n, a(2*n+1) = (2*n+1)4^n.
G.f.: x/det(I-x*M) where M=[1,i;i,1], i=sqrt(-1). - Paul Barry, Apr 27 2005
Starting 1, 1, 4, 12, ... this is 0^n + n2^(n-1), the binomial transform of the 'pair-reversed' natural numbers A004442. - Paul Barry, Jul 24 2003
Convolution of [1, 2, 4, 8, ...] with itself. - Jon Perry, Aug 07 2003
The signed version of this sequence, n(-2)^(n-1), is the inverse binomial transform of n(-1)^(n-1) (alternating sign natural numbers). - Paul Barry, Aug 20 2003
a(n-1) = (Sum_{k=0..n} 2^(n-k-1)*C(n-k, k)*C(1,(k+1)/2)*(1-(-1)^k)/2) - 0^n/4. - Paul Barry, Oct 15 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)(n-2k)^2. - Paul Barry, May 13 2005
a(n+2) = A049611(n+2) - A001788(n).
a(n) = n! * Sum_{k=0..n} 1/((k - 1)!(n - k)!). - Paul Barry, Mar 26 2003
a(n+1) = Sum_{k=0..n} 4^k * A109466(n,k). - Philippe Deléham, Nov 13 2006
Row sums of A130300 starting (1, 4, 12, 32, ...). - Gary W. Adamson, May 20 2007
Equals row sums of triangle A134083. Equals A002064(n) + (2^n - 1). - Gary W. Adamson, Oct 07 2007
a(n) = 4*a(n-1) - 4*a(n-2), a(0)=0, a(1)=1. - Philippe Deléham, Nov 16 2008
Sum_{n>0} 1/a(n) = 2*log(2). - Jaume Oliver Lafont, Feb 10 2009
a(n) = A000788(A000225(n)) = A173921(A000225(n)). - Reinhard Zumkeller, Mar 04 2010
a(n) = n * A011782(n). - Omar E. Pol, Aug 28 2013
a(n-1) = Sum_{t_1+2*t_2+...+n*t_n=n} (t_1+t_2+...+t_n-1)*multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n). - Mircea Merca, Dec 06 2013
a(n+1) = Sum_{r=0..n} (2*r+1)*C(n,r). - J. M. Bergot, Apr 07 2014
a(n) = A007283(n)*n/6. - Enxhell Luzhnica, Apr 16 2016
a(n) = (A000225(n) + A000337(n))/2. - Anton Zakharov, Sep 17 2016
Sum_{n>0} (-1)^(n+1)/a(n) = 2*log(3/2) = 2*A016578. - Ilya Gutkovskiy, Sep 17 2016
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} (i+1) * C(k,i). - Wesley Ivan Hurt, Sep 21 2017
a(n) = Sum_{i=1..n} Sum_{j=1..n} phi(i)*binomial(n, i*j). - Ridouane Oudra, Feb 17 2024

A000975 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).

Original entry on oeis.org

0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381, 174762, 349525, 699050, 1398101, 2796202, 5592405, 11184810, 22369621, 44739242, 89478485, 178956970, 357913941, 715827882, 1431655765, 2863311530, 5726623061, 11453246122

Offset: 0

Mira Bernstein, N. J. A. Sloane, Robert G. Wilson v, Sep 13 1996

Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg, who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017
Number of steps to change from a binary string of n 0's to n 1's using a Gray code. - Jon Stadler (jstadler(AT)coastal.edu)
Popular puzzles such as Spin-Out and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.
Conjecture: {a(n)} also gives all j for which A048702(j) = A000217(j); i.e., if we take the a(n)-th triangular number (a(n)^2 + a(n))/2 and multiply it by 3, we get a(n)-th even-length binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g., a(4) = 10, which is 1010 in binary; the tenth triangular number is 55, and 55*3 = 165 = 10100101 in binary. - Antti Karttunen, circa 1999. (This has been now proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016
Number of ways to tie a tie of n or fewer half turns, excluding mirror images. Also number of walks of length n or less on a triangular lattice with the following restrictions; given l, r and c as the lattice axes. 1. All steps are taken in the positive axis direction. 2. No two consecutive steps are taken on the same axis. 3. All walks begin with l. 4. All walks end with rlc or lrc. - Bill Blewett, Dec 21 2000
a(n) is the minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - Sen-peng Eu, Jun 15 2002
A087117(a(n)) = A038374(a(n)) = 1 for n > 1; see also A090050. - Reinhard Zumkeller, Nov 20 2003
Intersection of A003754 and A003714; complement of A107907. - Reinhard Zumkeller, May 28 2005
Equivalently, numbers m whose binary representation is effectively, for some number k, both the lazy Fibonacci and the Zeckendorf representation of k (in which case k = A022290(m)). - Peter Munn, Oct 06 2022
a(n+1) gives row sums of Riordan array (1/(1-x), x(1+2x)). - Paul Barry, Jul 18 2005
Total number of initial 01's in all binary words of length n+1. Example: a(3) = 5 because the binary words of length 4 that start with 01 are (01)00, (01)(01), (01)10 and (01)11 and the total number of initial 01's is 5 (shown between parentheses). a(n) = Sum_{k >= 0} k*A119440(n+1, k). - Emeric Deutsch, May 19 2006
In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts. - Hans Isdahl, Jan 07 2008
Equals A002450 and A020988 interlaced. - Zak Seidov, Feb 10 2008
For n > 1, let B_n = the complete binary tree with vertex set V where |V| = 2^n - 1. If VC is a minimum-size vertex cover of B_n, Sen-Peng Eu points out that a(n) = |VC|. It also follows that if IS = V\VC, a(n+1) = |IS|. - K.V.Iyer, Apr 13 2009
Starting with 1 and convolved with [1, 2, 2, 2, ...] = A000295. - Gary W. Adamson, Jun 02 2009
a(n) written in base 2 is sequence A056830(n). - Jaroslav Krizek, Aug 05 2009
This is the sequence A(0, 1; 1, 2; 1) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
From Vladimir Shevelev, Jan 30 2012, Feb 13 2012: (Start)
1) Denote by {n, k} the number of permutations of 1, ..., n with the up-down index k (for definition, see comment in A203827). Then max_k{n, k} = {n, a(n)} = A000111(n).
2) a(n) is the minimal number > a(n-1) with the Hamming distance d_H(a(n-1), a(n)) = n. Thus this sequence is the Hamming analog of triangular numbers 0, 1, 3, 6, 10, ... (End)
From Hieronymus Fischer, Nov 22 2012: (Start)
Represented in binary form each term after the second one contains every previous term as a substring.
The terms a(2) = 2 and a(3) = 5 are the only primes. Proof: For even n we get a(n) = 2*(2^(2*n) - 1)/3, which shows that a(n) is even, too, and obviously a(n) > 2 for all even n > 2. For odd n we have a(n) = (2^(n+1) - 1)/3 = (2^((n+1)/2) - 1) * (2^((n+1)/2) + 1)/3. Evidently, at least one of these factors is divisible by 3, both are greater than 6, provided n > 3. Hence it follows that a(n) is composite for all odd n > 3.
Represented as a binary number, a(n+1) has exactly n prime substrings. Proof: Evidently, a(1) = 1_2 has zero and a(2) = 10_2 has 1 prime substring. Let n > 1. Written in binary, a(n+1) is 101010101...01 (if n + 1 is odd) and is 101010101...10 (if n + 1 is even) with n + 1 digits. Only the 2- and 3-digits substrings 10_2 (=2) and 101_2 (=5) are prime substrings. All the other substrings are nonprime since every substring is a previous term and all terms unequal to 2 and 5 are nonprime. For even n + 1, the number of prime substrings equal to 2 = 10_2 is (n+1)/2, and the number of prime substrings equal to 5 = 101_2 is (n-1)/2, makes a sum of n. For odd n + 1 we get n/2 for both, the number of 2's and 5's prime substrings, in any case, the sum is n. (End)
Number of different 3-colorings for the vertices of all triangulated planar polygons on a base with n+2 vertices if the colors of the two base vertices are fixed. - Patrick Labarque, Feb 09 2013
A090079(a(n)) = a(n) and A090079(m) <> a(n) for m < a(n). - Reinhard Zumkeller, Feb 16 2013
a(n) is the number of length n binary words containing at least one 1 and ending in an even number (possibly zero) of 0's. a(3) = 5 because we have: 001, 011, 100, 101, 111. - Geoffrey Critzer, Dec 15 2013
a(n) is the number of permutations of length n+1 having exactly one descent such that the first element of the permutation is an even number. - Ran Pan, Apr 18 2015
a(n) is the sequence of the last row of the Hadamard matrix H(2^n) obtained via Sylvester's construction: H(2) = [1,1;1,-1], H(2^n) = H(2^(n-1))*H(2), where * is the Kronecker product. - William P. Orrick, Jun 28 2015
Conjectured record values of A264784: a(n) = A264784(A155051(n-1)). - Reinhard Zumkeller, Dec 04 2015. (This is proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016
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 131", based on the 5-celled von Neumann neighborhood. See A279053 for references and links. - Robert Price, Dec 05 2016
For n > 4, a(n-2) is the second-largest number in row n of A127824. - Dmitry Kamenetsky, Feb 11 2017
Conjecture: a(n+1) is the number of compositions of n with two kinds of parts, n and n', where the order of the 1 and 1' does not matter. For n=2, a(3) = 5 compositions, enumerated as follows:  2; 2'; 1,1; 1',1 = 1',1; 1',1'. - Gregory L. Simay, Sep 02 2017
Conjecture proved by recognizing the appropriate g.f. is x/(1 - x)(1 - x)(1 - 2*x^2 - 2x^3 - ...) =  x/(1 - 2*x - x^2 + 2x^3). - Gregory L. Simay, Sep 10 2017
a(n) = 2^(n-1) + 2^(n-3) + 2^(n-5) + ... a(2*k -1) = A002450(k) is the sum of the powers of 4. a(2*k) = 2*A002450(k). - Gregory L. Simay, Sep 27 2017
a(2*n) = n times the string [10] in binary representation, a(2*n+1) = n times the string [10] followed with [1] in binary representation. Example: a(7) = 85 = (1010101) in binary, a(8) = 170 = (10101010) in binary. - Ctibor O. Zizka, Nov 06 2018
Except for 0, these are the positive integers whose binary expansion has cuts-resistance 1. For the operation of shortening all runs by 1, cuts-resistance is the number of applications required to reach an empty word. Cuts-resistance 2 is A329862. - Gus Wiseman, Nov 27 2019
From Markus Sigg, Sep 14 2020: (Start)
Let s(k) be the length of the Collatz orbit of k, e.g. s(1) = 1, s(2) = 2, s(3) = 5. Then s(a(n)) = n+3 for n >= 3. Proof by induction: s(a(3)) = s(5) = 6 = 3+3. For odd n >= 5 we have s(a(n)) = s(4*a(n-2)+1) = s(12*a(n-2)+4)+1 = s(3*a(n-2)+1)+3 = s(a(n-2))+2 = (n-2)+3+2 = n+3, and for even n >= 4 this gives s(a(n)) = s(2*a(n-1)) = s(a(n-1))+1 = (n-1)+3+1 = n+3.
Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)
From Gary W. Adamson, May 14 2021: (Start)
With offset 1 the sequence equals the numbers of 1's from n = 1 to 3, 3 to 7, 7 to 15, ...; of A035263; as shown below:
..1     3           7                      15...
..1  0  1  1  1  0  1  0  1  0  1  1  1  0  1...
..1.....2...........5......................10...; a(n) = Sum_(k=1..2n-1)A035263(k)
.....1...........2.......................5...; as to zeros.
..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:
..0,  1,  2,  0,  1,  2, ... whereas even numbered disks move in the pattern:
..0,  2,  1,  0,  2,  1, ... (End)
Except for 0, numbers that are repunits in Gray-code representation (A014550). - Amiram Eldar, May 21 2021
From Gus Wiseman, Apr 20 2023: (Start)
Also the number of nonempty subsets of {1..n} with integer median, where the median of a multiset is the middle part in the odd-length case, and the average of the two middle parts in the even-length case. For example, the a(1) = 1 through a(4) = 10 subsets are:
  {1}  {1}  {1}      {1}
       {2}  {2}      {2}
            {3}      {3}
            {1,3}    {4}
            {1,2,3}  {1,3}
                     {2,4}
                     {1,2,3}
                     {1,2,4}
                     {1,3,4}
                     {2,3,4}
The complement is counted by A005578.
For mean instead of median we have A051293, counting empty sets A327475.
For normal multisets we have A056450, strongly normal A361202.
For partitions we have A325347, strict A359907, complement A307683.
(End)
In binary form, because the sequence 10101_2... keeps repeating, one can represent a(n) = floor(0.(10)2 * 2^n). Because 0.(10)_2 = 0.(10)_2 * 4 - 2, then 0.(10)_2 = 2/3. Substituting this value in the first expression, we obtain a(n) = floor(2^(n+1)/3). This also agrees with the formula of Paul Barry, Oct 08 2005. - _Giovanni Ciriani, Mar 31 2025

			a(4)=10 since 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111 are the 10 binary strings switching 0000 to 1111.
a(3) = 1 because "lrc" is the only way to tie a tie with 3 half turns, namely, pass the business end of the tie behind the standing part to the left, bring across the front to the right, then behind to the center. The final motion of tucking the loose end down the front behind the "lr" piece is not considered a "step".
a(4) = 2 because "lrlc" is the only way to tie a tie with 4 half turns. Note that since the number of moves is even, the first step is to go to the left in front of the tie, not behind it. This knot is the standard "four in hand", the most commonly known men's tie knot. By contrast, the second most well known tie knot, the Windsor, is represented by "lcrlcrlc".
a(n) = (2^0 - 1) XOR (2^1 - 1) XOR (2^2 - 1) XOR (2^3 - 1) XOR ... XOR (2^n - 1). - _Paul D. Hanna_, Nov 05 2011
G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...
a(9) = 341 = 2^8 + 2^6 + 2^4 + 2^2 + 2^0 = 4^4 + 4^3 + 4^2 + 4^1 + 4^0 = A002450(5). a(10) = 682 = 2*a(9) = 2*A002450(5). - _Gregory L. Simay_, Sep 27 2017

Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.

G. C. Greubel, Table of n, a(n) for n = 0..3300 (terms 0..300 from T. D. Noe)
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Thomas Baruchel, Properties of the cumulated deficient binary digit sum, arXiv:1908.02250 [math.NT], 2019.
Sergei L. Bezrukov et al., The congestion of n-cube layout on a rectangular grid, Discrete Mathematics 213.1-3 (2000): 13-19. See Theorem 1.
F. Chapoton and S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv:1310.4521 [math.CO], 2013. Is the sequence in Table 2 this sequence? - _N. J. A. Sloane_, Jan 04 2014. (Yes, it is. See Stockmeyer's arXiv:1608.08245 2016 paper for the proof.)
Ji Young Choi, Ternary Modified Collatz Sequences And Jacobsthal Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.7.5.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See pp. 1, 17, 42.
David Hayes, Kaveh Khodjasteh, Lorenza Viola and Michael J. Biercuk, Reducing sequencing complexity in dynamical quantum error suppression by Walsh modulation, arXiv:1109.6002 [quant-ph], 2011.
Clemens Heuberger and Daniel Krenn, Esthetic Numbers and Lifting Restrictions on the Analysis of Summatory Functions of Regular Sequences, arXiv:1808.00842 [math.CO], 2018. See p. 10.
Clemens Heuberger and Daniel Krenn, Asymptotic Analysis of Regular Sequences, arXiv:1810.13178 [math.CO], 2018. See p. 29.
Andreas M. Hinz, The Lichtenberg sequence, Fib. Quart., 55 (2017), 2-12.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 56. Book's website
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Jia Huang, Nonassociativity of the Norton Algebras of some distance regular graphs, arXiv:2001.05547 [math.CO], 2020.
Jia Huang, Norton algebras of the Hamming Graphs via linear characters, arXiv:2101.05711 [math.CO], 2021.
Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 17.
Jia Huang, Madison Mickey, and Jianbai Xu, The Nonassociativity of the Double Minus Operation, Journal of Integer Sequences, Vol. 20 (2017), #17.10.3.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 10.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 394
Hans Isdahl, "Knitwear" puzzle
D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3) (2007) p 265, E_3.
S. Lafortune, A. Ramani, B. Grammaticos, Y. Ohta and K.M. Tamizhmani, Blending two discrete integrability criteria: singularity confinement and algebraic entropy, arXiv:nlin/0104020 [nlin.SI], 2001.
Robert L. Lamphere, A Recurrence Relation in the Spinout Puzzle, The College Mathematics Journal, Vol. 27, Nbr. 4, Page 289, Sep. 96.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Georg Christoph Lichtenberg, Vermischte Schriften, Band 6 (1805). See chapter 6, p. 257.
Saad Mneimneh, Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction, Department of Computer Science, Hunter College, CUNY, 2019.
Richard Moot, Partial Orders, Residuation, and First-Order Linear Logic, arXiv:2008.06351 [cs.LO], 2020.
Gregg Musiker and Son Nguyen, Labeled Chip-firing on Binary Trees, arXiv:2206.02007 [math.CO], 2022.
Kival Ngaokrajang, Illustration of initial terms
Ahmet Öteleş, On the sum of Pell and Jacobsthal numbers by the determinants of Hessenberg matrices, AIP Conference Proceedings 1863, 310003 (2017).
Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure, arXiv:0801.0072 [math.CO], 2007-2010. See Example 3.
Chloe E. Shiff and Noah A. Rosenberg, Enumeration of rooted binary perfect phylogenies, arXiv:2410.14915 [q-bio.PE], 2024. See pp. 15, 17.
A. V. Sills and H. Wang, On the maximal Wiener index and related questions, Discrete Applied Mathematics, Volume 160, Issues 10-11, July 2012, Pages 1615-1623 - _N. J. A. Sloane_, Sep 21 2012
N. J. A. Sloane, Transforms
Elen Viviani Pereira Spreafico, Francisco Regis Vieira Alves, Paula Maria Machado Cruz Catarino, and Eudes Antonio Costa, A brief study of the one parameter Lichtenberg numbers, VI Int'l Conf. Math. Appl. Sci. Eng. (ICMASE 2025).
Paul K. Stockmeyer, An Exploration of Sequence A000975, arXiv:1608.08245 [math.CO], 2016; Fib. Quart. 55 (2017) 174.
Eric Weisstein's World of Mathematics, Baguenaudier
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
Index entries for sequences related to binary expansion of n
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Partial sums of A001045.
Row sums of triangle A013580.
Equals A026644/2.
Union of the bijections A002450 and A020988. - Robert G. Wilson v, Jun 09 2014
Column k=3 of A261139.
Cf. A000295, A005578, A015441, A043291, A053404, A059260, A077854, A119440, A127824, A130125, A135228, A155051, A179970, A264784.
Complement of A107907.
Row 3 of A300653.
Other sequences that relate to the binary representation of the terms: A003714, A003754, A007088, A022290, A056830, A104161, A107909.
Cf. A000120, A001511, A003242, A027383, A070939, A164707, A295235, A319416.
Cf. A005186, A033491, A153772.
Cf. A014550, A035263
Cf. A051293, A067659, A079309, A231147, A325347, A359893, A359907, A361801.

List([0..35],n->(2^(n+1)-2+(n mod 2))/3); # Muniru A Asiru, Nov 01 2018

a000975 n = a000975_list !! n
a000975_list = 0 : 1 : map (+ 1)
   (zipWith (+) (tail a000975_list) (map (* 2) a000975_list))
-- Reinhard Zumkeller, Mar 07 2012

[(2^(n+1) - 2 + (n mod 2))/3: n in [0..40]]; // Vincenzo Librandi, Mar 18 2015

A000975 := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2*A000975(n-1) else 2*A000975(n-1)+1 fi; fi; end;
seq(iquo(2^n,3),n=1..33); # Zerinvary Lajos, Apr 20 2008
f:=n-> if n mod 2 = 0 then (2^n-1)/3 else (2^n-2)/3; fi; [seq(f(n),n=0..40)]; # N. J. A. Sloane, Mar 21 2017

Array[Ceiling[2(2^# - 1)/3] &, 41, 0]
RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == a[n - 1] + 2a[n - 2] + 1}, a, {n, 40}] (* or *)
LinearRecurrence[{2, 1, -2}, {0, 1, 2}, 40] (* Harvey P. Dale, Aug 10 2013 *)
f[n_] := Block[{exp = n - 2}, Sum[2^i, {i, exp, 0, -2}]]; Array[f, 33] (* Robert G. Wilson v, Oct 30 2015 *)
f[s_List] := Block[{a = s[[-1]]}, Append[s, If[OddQ@ Length@ s, 2a + 1, 2a]]]; Nest[f, {0}, 32] (* Robert G. Wilson v, Jul 20 2017 *)
NestList[2# + Boole[EvenQ[#]] &, 0, 39] (* Alonso del Arte, Sep 21 2018 *)

{a(n) = if( n<0, 0, 2 * 2^n \ 3)}; /* Michael Somos, Sep 04 2006 */

a(n)=if(n<=0,0,bitxor(a(n-1),2^n-1)) \\ Paul D. Hanna, Nov 05 2011

concat(0, Vec(x/(1-2*x-x^2+2*x^3) + O(x^100))) \\ Altug Alkan, Oct 30 2015

{a(n) = (4*2^n - 3 - (-1)^n) / 6}; /* Michael Somos, Jul 23 2017 */

def a(n): return (2**(n+1) - 2 + (n%2))//3
print([a(n) for n in range(35)]) # Michael S. Branicky, Dec 19 2021

a(n) = ceiling(2*(2^n-1)/3).
Alternating sum transform (PSumSIGN) of {2^n - 1} (A000225).
a(n) = a(n-1) + 2*a(n-2) + 1.
a(n) = 2*2^n/3 - 1/2 - (-1)^n/6.
a(n) = Sum_{i = 0..n} A001045(i), partial sums of A001045. - Bill Blewett
a(n) = n + 2*Sum_{k = 1..n-2} a(k).
G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3). - Paul Barry, Feb 11 2003
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). - Paul Barry, Feb 11 2003
a(n) = Sum_{k = 0..floor((n-1)/2)} 2^(n-2*k-1). - Paul Barry, Nov 11 2003
a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2*k); a(n+1) = Sum_{k = 0..n} Sum_{j = 0..k} (-1)^(j+k)*2^j. - Paul Barry, Nov 12 2003
(-1)^(n+1)*a(n) = Sum_{i = 0..n} Sum_{k = 1..i} k!*k* Stirling2(i, k)*(-1)^(k-1) = (1/3)*(-2)^(n+1)-(1/6)(3*(-1)^(n+1)-1). - Mario Catalani (mario.catalani(AT)unito.it), Dec 22 2003
a(n+1) = (n!/3)*Sum_{i - (-1)^i + j = n, i = 0..n, j = 0..n} 1/(i - (-1)^i)!/j!. - Benoit Cloitre, May 24 2004
a(n) = A001045(n+1) - A059841(n). - Paul Barry, Jul 22 2004
a(n) = Sum_{k = 0..n} 2^(n-k-1)*(1-(-1)^k), row sums of A130125. - Paul Barry, Jul 28 2004
a(n) = Sum_{k = 0..n} binomial(k, n-k+1)2^(n-k); a(n) = Sum_{k = 0..floor(n/2)} binomial(n-k, k+1)2^k. - Paul Barry, Oct 07 2004
a(n) = A107909(A104161(n)); A007088(a(n)) = A056830(n). - Reinhard Zumkeller, May 28 2005
a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3) - 1 = A005578(n+1) - 1. - Paul Barry, Oct 08 2005
Convolution of "Number of fixed points in all 231-avoiding involutions in S_n." (A059570) with "1-n" (A024000), treating the result as if offset was 0. - Graeme McRae, Jul 12 2006
a(n) = A081254(n) - 2^n. - Philippe Deléham, Oct 15 2006
Starting (1, 2, 5, 10, 21, 42, ...), these are the row sums of triangle A135228. - Gary W. Adamson, Nov 23 2007
Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [A005578(n), A001045(n), a(n-1)]. - Gary W. Adamson, Dec 25 2007
2^n = 2*A005578(n-1) + 2*A001045(n) + 2*a(n-2). - Gary W. Adamson, Dec 25 2007
If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*stirling2(k,j)*x^(m-k) then a(n-3) = (-1)^(n-1)*f(n,3,-2), (n >= 3). - Milan Janjic, Apr 26 2009
a(n) + A001045(n) = A166920(n). a(n) + A001045(n+2) = A051049(n+1). - Paul Curtz, Oct 29 2009
a(n) = floor(A051049(n+1)/3). - Gary Detlefs, Dec 19 2010
a(n) = round((2^(n+2)-3)/6) = floor((2^(n+1)-1)/3) = round((2^(n+1)-2)/3); a(n) = a(n-2) + 2^(n-1), n > 1. - Mircea Merca, Dec 27 2010
a(n) = binary XOR of 2^k-1 for k=0..n. - Paul D. Hanna, Nov 05 2011
E.g.f.: 2/3*exp(2*x) - 1/2*exp(x) - 1/6*exp(-x) = 2/3*U(0); U(k) = 1 - 3/(4*(2^k) - 4*(2^k)/(1+3*(-1)^k - 24*x*(2^k)/(8*x*(2^k)*(-1)^k - (k+1)/U(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
Starting with "1" = triangle A059260 * [1, 2, 2, 2, ...] as a vector. - Gary W. Adamson, Mar 06 2012
a(n) = 2*(2^n - 1)/3, for even n; a(n) = (2^(n+1) - 1)/3 = (1/3)*(2^((n+1)/2) - 1)*(2^((n+1)/2) + 1), for odd n. - Hieronymus Fischer, Nov 22 2012
a(n) + a(n+1) = 2^(n+1) - 1. - Arie Bos, Apr 03 2013
G.f.: Q(0)/(3*(1-x)), where Q(k) = 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 + 1/(2*4^k - 8*x*16^k/(4*x*4^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 21 2013
floor(a(n+2)*3/5) = A077854(n), for n >= 0. - Armands Strazds, Sep 21 2014
a(n) = (2^(n+1) - 2 + (n mod 2))/3. - Paul Toms, Mar 18 2015
a(0) = 0, a(n) = 2*(a(n-1)) + (n mod 2). - Paul Toms, Mar 18 2015
Binary: a(n) = (a(n-1) shift left 1) + (a(n-1)) NOR (...11110). - Paul Toms, Mar 18 2015
Binary: for n > 1, a(n) = 2*a(n-1) OR a(n-2). - Stanislav Sykora, Nov 12 2015
a(n) = A266613(n) - 20*2^(n-5), for n > 2. - Andres Cicuttin, Mar 31 2016
From Michael Somos, Jul 23 2017: (Start)
a(n) = -(2^n)*a(-n) for even n; a(n) = -(2^(n+1))*a(-n) + 1 for odd n.
0 = +a(n)*(+2 +4*a(n) -4*a(n+1)) + a(n+1)*(-1 +a(n+1)) for all n in Z. (End)
G.f.: (x^1+x^3+x^5+x^7+...)/(1-2*x). - Gregory L. Simay, Sep 27 2017
a(n+1) = A051049(n) + A001045(n). - Yuchun Ji, Jul 12 2018
a(n) = A153772(n+3)/4. - Markus Sigg, Sep 14 2020
a(4*k+d) = 2^(d+1)*a(4*k-1) + a(d), a(n+4) = a(n) + 2^n*10, a(0..3) = [0,1,2,5]. So the last digit is always 0,1,2,5 repeated. - Yuchun Ji, May 22 2023

Additional comments from Barry E. Williams, Jan 10 2000

A124762 Number of levels for compositions in standard order.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 1, 3, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, 1, 1, 1, 2, 4, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 2, 2, 0, 0, 1, 3, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 2, 2, 2, 3, 5, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 1, 3, 0, 0, 0, 1, 1, 2, 1, 3, 0, 0, 1, 1, 1, 1, 2, 4, 0, 0, 0, 1, 1, 0, 0, 2, 0

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence gives the number of adjacent equal terms in the n-th composition in standard order. Alternatively, a(n) is one fewer than the number of maximal anti-runs in the same composition, where anti-runs are sequences without any adjacent equal terms. For example, the 1234567th composition in standard order is (3,2,1,2,2,1,2,5,1,1,1) with anti-runs ((3,2,1,2),(2,1,2,5,1),(1),(1)), so a(1234567) = 4 - 1 = 3. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; 2>1=1, so a(11) = 1.
The table starts:
  0
  0
  0 1
  0 0 0 2
  0 0 1 1 0 0 1 3
  0 0 0 1 0 1 0 2 0 0 1 1 1 1 2 4
  0 0 0 1 1 0 0 2 0 0 2 2 0 0 1 3 0 0 0 1 0 1 0 2 1 1 2 2 2 2 3 5

Cf. A066099, A124760, A124761, A124763, A124764, A011782 (row lengths), A059570 (row sums).
Anti-runs summing to n are counted by A003242(n).
A triangle counting maximal anti-runs of compositions is A106356.
A triangle counting maximal runs of compositions is A238279.
Partitions whose first differences are an anti-run are A238424.
All of the following pertain to compositions in standard order (A066099):
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Adjacent unequal pairs are counted by A333382.
- Anti-runs are A333489.
Cf. A000120, A029931, A048793, A059893, A070939, A114994, A225620, A228351.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Select[Partition[stc[n],2,1],SameQ@@#&]],{n,0,100}] (* Gus Wiseman, Apr 08 2020 *)

For a composition b(1),...,b(k), a(n) = Sum_{1<=i=1

For n > 0, a(n) = A333381(n) - 1. - Gus Wiseman, Apr 08 2020

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

Original entry on oeis.org

0, 1, 5, 17, 49, 129, 321, 769, 1793, 4097, 9217, 20481, 45057, 98305, 212993, 458753, 983041, 2097153, 4456449, 9437185, 19922945, 41943041, 88080385, 184549377, 385875969, 805306369, 1677721601, 3489660929, 7247757313, 15032385537, 31138512897, 64424509441

Offset: 0

N. J. A. Sloane

a(n) also gives number of 0's in binary numbers 1 to 111..1 (n+1 bits). - Stephen G Penrice, Oct 01 2000
Numerator of m(n) = (m(n-1)+n)/2, m(0)=0. Denominator is A000079. - Reinhard Zumkeller, Feb 23 2002
a(n) is the number of directed column-convex polyominoes of area n+2 having along the lower contour exactly one vertical step that is followed by a horizontal step (a reentrant corner). - Emeric Deutsch, May 21 2003
a(n) is the number of bits in binary numbers from 1 to 111...1 (n bits). Partial sums of A001787. - Emeric Deutsch, May 24 2003
Genus of graph of n-cube = a(n-3) = 1+(n-4)*2^(n-3), n>1.
Sum of ordered partitions of n where each element is summed via T(e-1). See A066185 for more information. - Jon Perry, Dec 12 2003
a(n-2) is the number of Dyck n-paths with exactly one peak at height >= 3. For example, there are 5 such paths with n=4: UUUUDDDD, UUDUUDDD, UUUDDUDD, UDUUUDDD, UUUDDDUD. - David Callan, Mar 23 2004
Permutations in S_{n+2} avoiding 12-3 that contain the pattern 13-2 exactly once.
a(n) is prime for n = 2, 3, 7, 27, 51, 55, 81. a(n) is semiprime for n = 4, 5, 6, 8, 9, 10, 11, 13, 15, 19, 28, 32, 39, 57, 63, 66, 75, 97. - Jonathan Vos Post, Jul 18 2005
A member of the family of sequences defined by a(n) = Sum_{i=1..n} i*[c(1)*...*c(r)]^(i-1). This sequence has c(1)=2, A014915 has c(1)=3. - Ctibor O. Zizka, Feb 23 2008
Starting with 1 = row sums of A023758 as a triangle by rows: [1; 2,3; 4,6,7; 8,12,14,15; ...]. - Gary W. Adamson, Jul 18 2008
Equivalent formula given in Brehm: for each q >= 3 there exists a polyhedral map M_q of type {4, q} with [number of vertices] f_0 = 2^q and [genus] g = (2^(q-3))*(q-4) + 1 such that M_q and its dual have polyhedral embeddings in R^3 [McMullen et al.]. - Jonathan Vos Post, Jul 25 2009
Sums of rows of the triangle in A173787. - Reinhard Zumkeller, Feb 28 2010
This sequence is related to A000079 by a(n) = n*A000079(n)-Sum_{i=0..n-1} A000079(i). - Bruno Berselli, Mar 06 2012
(1 + 5*x + 17*x^2 + 49*x^3 + ...) = (1 + 2*x + 4*x^2 + 8*x^3 + ...) * (1 + 3*x + 7*x^2 + 15*x^3 + ...). - Gary W. Adamson, Mar 14 2012
The first barycentric coordinate of the centroid of Pascal triangles, assuming that numbers are weights, is A000295(n+1)/A000337(n), no matter what the triangle sides are. See attached figure. - César Eliud Lozada, Nov 14 2014
a(n) is the n-th number that is a sum of n positive n-th powers for n >= 1. a(4) = 49 = A003338(4). - Alois P. Heinz, Aug 01 2020
a(n) is the sum of the largest elements of all subsets of {1,2,..,n}. For example, a(3)=17; the subsets of {1,2,3} are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, and the sum of the largest elements is 17. - Enrique Navarrete, Aug 20 2020
a(n-1) is the sum of the second largest elements of the subsets of {1,2,..,n} that contain n. For example, for n = 4, a(3)=17; the subsets of {1,2,3,4} that contain 4 are {4}, {1,4}, {2,4}, {3,4}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}, and the sum of the second largest elements is 17. - Enrique Navarrete, Aug 24 2020
a(n-1) is also the sum of diameters of all subsets of {1,2,...,n} that contain n.  For example, for n = 4, a(3)=17; the subsets of {1,2,3,4} that contain 4 are {4}, {1,4}, {2,4}, {3,4}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}; the diameters of these sets are 0,3,2,1,3,3,2,3 and the sum is 17. - Enrique Navarrete, Sep 07 2020
a(n-1) is also the number of additions required to compute the permanent of general n X n matrices using trellis methods (see Theorems 5 and 6, pp. 10-11 in Kiah et al.). - Stefano Spezia, Nov 02 2021

F. Harary, Topological concepts in graph theory, pp. 13-17 of F. Harary and L. Beineke, editors, A seminar on Graph Theory, Holt, Rinehart and Winston, New York, 1967.
V. G. Gutierrez and S. L. de Medrano, Surfaces as complete intersections, in Riemann and Klein Surfaces, Automorphisms, Symmetries and Moduli Spaces, edited by Milagros Izquierdo, S. Allen Broughton, Antonio F. Costa, Contemp. Math. vol. 629, 2014, pp. 171-.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 119.
G. H. Hardy, A Theorem Concerning the Infinite Cardinal Numbers, Quart. J. Math., 35 (1904), p. 90 = Collected Papers of G. H. Hardy, Vol. VII, p. 430.
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).

Indranil Ghosh, Table of n, a(n) for n = 0..1000 (first 301 terms from T. D. Noe)
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 14.
H. H. Bauschke and R. M. Corless, Analyzing a Projection Method with Maple, MapleTech Journal, 4:1 (1997), 2-7.
L. W. Beineke and F. Harary, The genus of the n-cube, Canad. J. Math., 17 (1965), 494-496.
Ulrich Brehm and Egon Schulte, Polyhedral Maps. [_Jonathan Vos Post_, Jul 25 2009]
Harry Crane, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
Pedro Fernando Fernández Espinosa and Agustín Moreno Cañadas, Homological Ideals as Integer Specializations of Some Brauer Configuration Algebras, arXiv:2104.00050 [math.RT], 2021.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
Christian Kassel and Christophe Reutenauer, The zeta function of the Hilbert scheme of n points on a two-dimensional torus, arXiv:1505.07229v3 [math.AG], 2015. [A later version of this paper has a different title and different contents, and the number-theoretical part of the paper was moved to the publication below.]
Christian Kassel and Christophe Reutenauer, Complete determination of the zeta function of the Hilbert scheme of n points on a two-dimensional torus, arXiv:1610.07793 [math.NT], 2016.
Han Mao Kiah, Alexander Vardy, and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021.
S. Kitaev, J. Remmel, and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 2015, #A16. (arXiv, arXiv:1302.2274 [math.CO], 2013)
Santiago López de Medrano, On the genera of moment-angle manifolds associated to dual-neighborly polytopes, combinatorial formulas and sequences, arXiv:2003.07508 [math.GT], 2020.
César Eliud Lozada, Centroids of Pascal triangles
P. McMullen, Ch. Schulz and J.M. Wills, Polyhedral manifolds in E^3 with unusually large genus, Israel J. Math. 46:127-144, 1983. [From _Jonathan Vos Post_, Jul 25 2009]
Toufik Mansour, Restricted permutations by patterns of type (2,1), arXiv:math/0202219 [math.CO], 2002.
Michael Penn, An awesome number theory contest problem, YouTube video, 2022.
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
Len Smiley, Hardy's algorithm.
Nsibiet E. Udo, Praise Adeyemo, Balazs Szendroi, and Stavros Argyrios Papadakis, Ideals, representations and a symmetrised Bernoulli triangle, arXiv:2409.10278 [math.AC], 2024. See pp. 2,4,8.
Eric Weisstein's World of Mathematics, Graph Genus.
Eric Weisstein's World of Mathematics, Hypercube Graph.
A. F. Y. Zhao, Pattern Popularity in Multiply Restricted Permutations, Journal of Integer Sequences, 17 (2014), #14.10.3.
Index entries for linear recurrences with constant coefficients, signature (5,-8,4).

a(n) = T(3, n), array T given by A048472. A036799/2.
Cf. A001787, A066185, A077436, A023758, A014915.
Cf. A000079, A209359.
Cf. A000295, A008292.
Cf. A003338.
Main diagonal of A336725.

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

[(n-1)*2^n + 1: n in [0..40]]; // Vincenzo Librandi, Nov 21 2014

A000337 := proc(n) 1+(n-1)*2^n ; end proc: # R. J. Mathar, Oct 10 2011

Table[Sum[(-1)^(n - k) k (-1)^(n - k) Binomial[n + 1, k + 1], {k, 0, n}], {n, 0, 28}] (* Zerinvary Lajos, Jul 08 2009 *)
Table[(n - 1) 2^n + 1, {n, 0, 40}] (* Harvey P. Dale, Jun 21 2011 *)
LinearRecurrence[{5, -8, 4}, {0, 1, 5}, 40] (* Harvey P. Dale, Jun 21 2011 *)
CoefficientList[Series[x / ((1 - x) (1 - 2 x)^2), {x, 0, 50}], x] (* Vincenzo Librandi, Nov 21 2014 *)

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

a=lambda n:((n-1)<<(n))+1 # Indranil Ghosh, Jan 05 2017

Binomial transform of A004273. Binomial transform of A008574 if the leading zero is dropped.
G.f.: x/((1-x)*(1-2*x)^2). - Simon Plouffe in his 1992 dissertation
E.g.f.: exp(x) - exp(2*x)*(1-2*x). a(n) = 4*a(n-1) - 4*a(n-2)+1, n>0. Series reversion of g.f. A(x) is x*A034015(-x). - Michael Somos
Binomial transform of n/(n+1) is a(n)/(n+1). - Paul Barry, Aug 19 2005
a(n) = A119258(n+1,n-1) for n>0. - Reinhard Zumkeller, May 11 2006
Convolution of "Number of fixed points in all 231-avoiding involutions in S_n" (A059570) with "The odd numbers" (A005408), treating the result as if offset=0. - Graeme McRae, Jul 12 2006
a(n) = Sum_{k=1..n} k*2^(k-1), partial sums of A001787. - Zerinvary Lajos, Oct 19 2006
a(n) = 5*a(n-1) - 8*a(n-2) + 4*a(n-3), n > 2. - Harvey P. Dale, Jun 21 2011
a(n) = Sum_{k=1..n} Sum_{i=1..n} i * C(k,i). - Wesley Ivan Hurt, Sep 19 2017
a(n) = A000295(n+1)^2 - A000295(n)*A000295(n+2). - Gregory Gerard Wojnar, Oct 23 2018

A045883 a(n) = ((3n+1)2^n - (-1)^n)/9.

Original entry on oeis.org

0, 1, 3, 9, 23, 57, 135, 313, 711, 1593, 3527, 7737, 16839, 36409, 78279, 167481, 356807, 757305, 1601991, 3378745, 7107015, 14913081, 31224263, 65244729, 136081863, 283348537, 589066695, 1222872633, 2535223751, 5249404473, 10856722887, 22429273657, 46290203079

Offset: 0

Edward Early

Without the initial zero, PSumSIGN transform of A001787. - Michael Somos, Jul 10 2003
Number of rises (drops) in the compositions of n+2 with parts in N.
From Michel Lagneau, Jan 13 2012: (Start)
This sequence is connected with the Collatz problem. We consider the array T(i,j) where the i-th row gives the parity trajectory of i, for example for i = 6, the infinite trajectory is 6 -> 3 -> 10 ->5 -> 16 ->8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4->2-> 1 ... and T(6,j) = [0,1,0,1,0,0,0,0,1,0,0,1,...,1,0,0,1,...]. Now, we consider the sum of the digits 1 of each array T(i,j), where
a(1) = sum of the digits "1" of T(i,j), i = 1..2^1 and j = 1;
a(2) = sum of the digits "1" of T(i,j), i = 1..2^2 and j = 1..2;
a(3) = sum of the digits "1" of T(i,j), i = 1..2^3 and j = 1..3;
a(n) = Sum_{i=1..2^n}(Sum_{j=1..n} T(i,j)) = Sum_{i=1..n} A001045(n)*2^(n-i) = convolution of A001045 and A000079 (see the formula below).
The number of digits "0" equals A113861(n) = n*2^n - a(n) because n and 2^n are the dimensions of each array.
An important result is that the ratio r = A113861(n) / A045883(n) tends towards 2 when n tends towards infinity. In other words, when the array tends towards infinity, the ratio r = (number of divisions by 2) / (number of multiplications by 3) tends towards 2, even if there exists divergent trajectories. That is the problem! For each possible divergent infinite trajectory, r < 2 even though the global ratio r is 2.
Conclusion:
1. For each number n with a convergent trajectory T(n,k), k = 1..infinity, or for each row of the array T(i,j), the ratio r tends towards 2 (the proof is easy because the trajectory becomes periodic from a certain index 1001001001...).
2. For each array of dimension n X 2^n, the radio r tends towards 2.
3. If there exists a number n such that the trajectory is divergent, this trajectory is random and r tends towards a real x such that 1 < = r < = x < 2.
4. In order to establish a proof of the Collatz problem from this considerations (if that is possible), it is necessary to prove that a ratio < 2 for an infinite row (or several rows) of an infinite array T(i,j) is incompatible with r = 2, the exact ratio for this array. (End)
a(n) is the distance spectral radius of the dimension-regular generalized recursive circulant graph (commonly known as multiplicative circulant graph) of order 2^n. - John Rafael M. Antalan, Sep 25 2020
Total sum over all compositions of n of the absolute differences between consecutive parts, assuming an initial part 0. - Alois P. Heinz, Apr 30 2025

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
John Rafael M. Antalan and Francis Joseph H. Campeña, Distance eigenvalues and forwarding indices of dimension-regular generalized recursive circulant graph of order power of two and three, arXiv:2009.11608[math.CO], 2020.
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.
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
Silvia Heubach and Toufik Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
F. K. Hwang, Three versions of a group testing game, SIAM J. Algebraic Discrete Methods 5 (1984), no. 2, 145--153. MR0745434(85d:90120). See p. 151, f(n) (but divide by 2). - _N. J. A. Sloane_, Apr 13 2014
Peter J. Larcombe and Eric J. Fennessey, On a Scaled Balanced-Power Product Recurrence, Fibonacci Quart. 54 (2016), no. 3, 242-246. See Remark 2.2 p. 244.
Peter J. Larcombe, Julius Fergy T. Rabago, and Eric J. Fennessey, On two derivative sequences from scaled geometric mean sequence terms, Palestine Journal of Mathematics (2018) Vol. 7(2), 397-405.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Partial sums of A059570, bisection: A014916.
Row sums of triangle A094953.
Cf. A059260, A127984.
Cf. A000079, A001045, A001787, A045883, A049260, A113861, A140960, A188545.
Cf. A238343, A238344.

[((3*n+1)*2^n-(-1)^n)/9: n in [0..35]]; // Vincenzo Librandi, Jun 15 2017

A045883:=n->((3*n+1)*2^n-(-1)^n)/9; seq(A045883(n), n=0..30); # Wesley Ivan Hurt, Mar 21 2014

nn=31;a=x^2(1-x)/(1-x-2x^2)/(1-2x);b=x^2/(1-2x)^2;Drop[CoefficientList[Series[(b-a)/2,{x,0,nn}],x],2] (* Geoffrey Critzer, Mar 21 2014 *)
CoefficientList[Series[x / ((1 + x) (1 - 2 x)^2), {x, 0, 33}], x] (* Vincenzo Librandi, Jun 15 2017 *)
LinearRecurrence[{3, 0, -4}, {0, 1, 3}, 33] (* Jean-François Alcover, Sep 27 2017 *)

{a(n) = if( n<-1, 0, ((3*n + 1)*2^n - (-1)^n) / 9)};

G.f.: x/((1+x)*(1-2*x)^2).
a(n) = 3*a(n-1) - 4*a(n-3).
Convolution of A001045 and A000079. G.f.: x/((1-2*x)(1-x-2*x^2)). - Paul Barry, May 21 2004
Starting with "1" = triangle A049260 * the odd integers as a vector. - Gary W. Adamson, Mar 06 2012
a(n) = A140960(n)/2. - J. M. Bergot, May 21 2013
From Wolfdieter Lang, Jun 14 2017: (Start)
a(n) = f(n)*2^n, where f(n) is a rational Fibonacci type sequence based on fuse(a,b) = (a+b+1)/2 with f(0) = 0, f(1) = 1/2 and f(n) = fuse(f(n-1), f(n-2)), for n >= 2. For fuse(a,b) see the Jeff Erickson link under A188545. Proof with f(n) = (3*n+1 - (-1)^n/2^n)/9, n >= 0, by induction.
a(n) = a(n-1) + 2*a(n-2) + 2^(n-1), n >= 0, with input a(-2) = 1/4 and a(-1) = 0. See also A127984. (End)
E.g.f.: (exp(2*x)*(1 + 6*x) - cosh(x) + sinh(x))/9. - Stefano Spezia, Apr 09 2025
a(n) = Sum_{k=0..n+2} k * A238343(n+2,k). - Alois P. Heinz, Apr 30 2025

Simpler description from Vladeta Jovovic, Jul 18 2002

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

Original entry on oeis.org

1, 2, 6, 14, 36, 86, 210, 500, 1194, 2822, 6660, 15638, 36642, 85604, 199626, 464630, 1079892, 2506550, 5811762, 13462484, 31159914, 72071654, 166599972, 384912086, 888906306, 2052031172, 4735527306, 10925175254, 25198866036, 58108609526, 133973643090

Offset: 0

Johannes W. Meijer, Aug 06 2010; edited Jun 21 2013

a(n) represents the number of n-move routes of a fairy chess piece starting in a given corner square (m = 1, 3, 7 or 9) on a 3 X 3 chessboard. This fairy chess piece behaves like a bishop on the eight side and corner squares but on the center square the bishop flies into a rage and turns into a raging elephant.
In chaturanga, the old Indian version of chess, one of the pieces was called gaja, elephant in Sanskrit. The Arabs called the game shatranj and the elephant became el fil in Arabic. In Spain chess became chess as we know it today but surprisingly in Spanish a bishop isn't a Christian bishop but a Moorish elephant and it still goes by its original name of el alfil.
On a 3 X 3 chessboard there are 2^9 = 512 ways for an elephant to fly into a rage on the central square (off the center the piece behaves like a normal bishop). The elephant is represented by the A[5] vector in the fifth row of the adjacency matrix A, see the Maple program and A180140. For the corner squares the 512 elephants lead to 46 different elephant sequences, see the overview of elephant sequences and the crossreferences.
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 central square to A175655.

Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984.
David Hooper and Kenneth Whyld, The Oxford Companion to Chess, pp. 74, 366, 1992.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Viswanathan Anand, The Indian Defense, Time, Jun 19 2008.
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
Johannes W. Meijer, The elephant sequences.
Wikipedia, War Elephant.
Index entries for linear recurrences with constant coefficients, signature (3,1,-6).

Cf. Elephant sequences corner squares [decimal value A[5]]: A040000 [0], A000027 [16], A000045 [1], A094373 [2], A000079 [3], A083329 [42], A027934 [11], A172481 [7], A006138 [69], A000325 [26], A045623 [19], A000129 [21], A095121 [170], A074878 [43], A059570 [15], A175654 [71, this sequence], A026597 [325], A097813 [58], A057711 [27], 2*A094723 [23; n>=-1], A002605 [85], A175660 [171], A123203 [186], A066373 [59], A015518 [341], A134401 [187], A093833 [343].

Cf. A000244, A006130, A006138, A075188, A175655, A180140.

[n le 3 select Factorial(n) else 3*Self(n-1) +Self(n-2) -6*Self(n-3): n in [1..41]]; // G. C. Greubel, Dec 08 2021

nmax:=28; m:=1; A[1]:=[0,0,0,0,1,0,0,0,1]: A[2]:=[0,0,0,1,0,1,0,0,0]: A[3]:=[0,0,0,0,1,0,1,0,0]: A[4]:=[0,1,0,0,0,0,0,1,0]: A[5]:=[0,0,1,0,0,0,1,1,1]: A[6]:=[0,1,0,0,0,0,0,1,0]: A[7]:=[0,0,1,0,1,0,0,0,0]: A[8]:=[0,0,0,1,0,1,0,0,0]: A[9]:=[1,0,0,0,1,0,0,0,0]: A:=Matrix([A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9]]): 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);

LinearRecurrence[{3,1,-6}, {1,2,6}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 21 2012 *)

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

[( (1-x-x^2)/((1-2*x)*(1-x-3*x^2)) ).series(x,n+1).list()[n] for n in (0..40)] # G. C. Greubel, Dec 08 2021

G.f.: (1 - x - 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)=2 and a(2)=6.
a(n) = ((6+10*A)*A^(-n-1) + (6+10*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)).
a(n) = b(n) - b(n-1) - b(n-2), where b(n) = Sum_{k=1..n} Sum_{j=0..k} binomial(j,n-3*k+2*j)*(-6)^(k-j)*binomial(k,j)*3^(3*k-n-j), n>0, b(0)=1, with a(0) = b(0), a(1) = b(1) - b(0). - Vladimir Kruchinin, Aug 20 2010
a(n) = 2*A006138(n) - 2^n = 2*(A006130(n) + A006130(n-1)) - 2^n. - G. C. Greubel, Dec 08 2021
E.g.f.: 2*exp(x/2)*(13*cosh(sqrt(13)*x/2) + 3*sqrt(13)*sinh(sqrt(13)*x/2))/13 - cosh(2*x) - sinh(2*x). - Stefano Spezia, Feb 12 2023

A027934 a(0)=0, a(1)=1, a(2)=2; for n > 2, a(n) = 3a(n-1) - a(n-2) - 2a(n-3).

Original entry on oeis.org

0, 1, 2, 5, 11, 24, 51, 107, 222, 457, 935, 1904, 3863, 7815, 15774, 31781, 63939, 128488, 257963, 517523, 1037630, 2079441, 4165647, 8342240, 16702191, 33433039, 66912446, 133899917, 267921227, 536038872, 1072395555, 2145305339

Offset: 0

Clark Kimberling

Number of compositions of n with at least one even part (offset 2). - Vladeta Jovovic, Dec 29 2004
First differences of A008466. a(n) = A008466(n+2) - A008466(n+1). - Alexander Adamchuk, Apr 06 2006
Starting with "1" = eigensequence of a triangle with the Fibonacci series as the left border and the rest 1's. - Gary W. Adamson, Jul 24 2010
An elephant sequence, see A175654. For the corner squares 24 A[5] vectors, with decimal values between 11 and 416, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A099036 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010
a(n) = Sum_{k=1..n} A108617(n,k) / 2. - Reinhard Zumkeller, Oct 07 2012
a(n) is the number of binary strings that contain the substring 11 or end in 1. a(3) = 5 because we have: 001, 011, 101, 110, 111. - Geoffrey Critzer, Jan 04 2014
a(n-1), n >= 1, is the number of nonexisting (due to the maturation delay) "[male-female] pairs of Fibonacci rabbits" at the beginning of the n-th month. - Daniel Forgues, May 06 2015
a(n-1) is the number of subsets of {1,2,..,n} that contain n that have at least one pair of consecutive integers. For example, for n=5, a(4) = 11 and the 11 subsets are {4,5}, {1,2,5}, {1,4,5}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}.  Note that A008466(n) is the number of all subsets of {1,2,..,n} that have at least one pair of consecutive integers. - Enrique Navarrete, Aug 15 2020

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Patrick Letendre, Polynomials with integer roots, arXiv:1911.00480 [math.NT], 2019. See p. 4.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
OEIS Wiki, Fibonacci rabbits
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2).

Row sums of triangle A131767. - Gary W. Adamson, Jul 13 2007
a(n) = A101220(1, 2, n+1).
T(n, n) + T(n, n+1) + ... + T(n, 2n), T given by A027926.
Diagonal sums of A055248.
Cf. A000045, A000079, A008466, A059570, A099036, A047967, A000032.

List([0..35], n-> 2^n - Fibonacci(n+1) ); # G. C. Greubel, Sep 27 2019

a027934 n = a027934_list !! n
a027934_list = 0 : 1 : 2 : zipWith3 (\x y z -> 3 * x - y - 2 * z)
               (drop 2 a027934_list) (tail a027934_list) a027934_list
-- Reinhard Zumkeller, Oct 07 2012

[2^n - Fibonacci(n+1): n in [0..35]]; // G. C. Greubel, Sep 27 2019

A027934:= proc(n) local K; K:= Matrix ([[2,0,0], [0,1,1], [0,1,0]])^n; K[1,1]-K[2,2] end: seq (A027934(n), n=0..31); # Alois P. Heinz, Jul 28 2008
a := n -> 2^n - combinat:-fibonacci(n+1): seq(a(n),n=0..31); # Peter Luschny, May 09 2015

nn=31; a:=1/(1-x-x^2); b:=1/(1-2x); CoefficientList[Series[a*x*(1+x*b), {x,0,nn}], x] (* Geoffrey Critzer, Jan 04 2014 *)
LinearRecurrence[{3,-1,-2}, {0,1,2}, 32] (* Jean-François Alcover, Jan 09 2016 *)
nxt[{a_,b_,c_}]:={b,c,3c-b-2a}; NestList[nxt,{0,1,2},40][[;;,1]] (* Harvey P. Dale, Feb 02 2025 *)

a(n)=2^n-fibonacci(n+1) \\ Charles R Greathouse IV, Jun 11 2015

[2^n - fibonacci(n+1) for n in (0..35)] # G. C. Greubel, Sep 27 2019

a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..n-2*j} binomial(n-j, n-2*j-k). - Paul Barry, Feb 07 2003
From Paul Barry, Jan 23 2004: (Start)
Row sums of A105809.
G.f.: x*(1-x)/((1-2*x)*(1-x-x^2)).
a(n) = 2^n - Fibonacci(n+1). (End) - corrected Apr 06 2006 and Oct 05 2012
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j). - Paul Barry, Aug 29 2004
a(n) = (Sum of (n+1)-th row of the triangle in A108617) / 2. - Reinhard Zumkeller, Jun 12 2005
a(n) = term (1,1) - term (2,2) in the 3 X 3 matrix [2,0,0; 0,1,1; 0,1,0]^n. - Alois P. Heinz, Jul 28 2008
a(n) = 2^n - A000045(n+1). - Geoffrey Critzer, Jan 04 2014
a(n) ~ 2^n. - Daniel Forgues, May 06 2015
From Bob Selcoe, Mar 29 2016: (Start)
a(n) = 2*a(n-1) + A000045(n-2).
a(n) = 4*a(n-2) + A000032(n-2). (End)
a(n) = 2^(n-1) - ( ((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5). - Haider Ali Abdel-Abbas, Aug 17 2019

Simpler definition from Miklos Kristof, Nov 24 2003
Initial zero added by N. J. A. Sloane, Feb 13 2008
Definition fixed by Reinhard Zumkeller, Oct 07 2012

A172481 a(n) = (3n2^n+2^(n+4)+2*(-1)^n)/18.

Original entry on oeis.org

1, 2, 5, 11, 25, 55, 121, 263, 569, 1223, 2617, 5575, 11833, 25031, 52793, 111047, 233017, 487879, 1019449, 2126279, 4427321, 9204167, 19107385, 39612871, 82021945, 169636295, 350457401, 723284423, 1491308089, 3072094663, 6323146297, 13004206535, 26724240953

Offset: 0

Paul Curtz, Feb 04 2010

The binomial transform is in A126184.
An elephant sequence, see A175654 and A175655. There are 24 A[5] vectors, with decimal values between 7 and 448, that lead for the corner squares to this sequence. Its companion sequence for the central square is A175656. Furthermore there are 36 A[5] vectors, with decimal values between 15 and 480, that lead for the central square to four times this sequence for n >= -1. Its companion sequence for the corner squares is A059570. - Johannes W. Meijer, Aug 15 2010
a(n) is also the number of runs of weakly increasing parts in all compositions of n+1. a(2) = 5: (111), (12), (2)(1), (3). - Alois P. Heinz, Apr 30 2017

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

Cf. A059570, A151529, A127984.

[(3*n*2^n+2^(n+4)+2*(-1)^n)/18: n in [0..40]]; // Vincenzo Librandi, Aug 04 2011

Table[(3n 2^n+2^(n+4)+2(-1)^n)/18,{n,0,40}]  (* or *)
CoefficientList[Series[(1-x-x^2)/((1+x)(1-2x)^2), {x,0,40}], x]  (* Harvey P. Dale, Mar 28 2011 *)

a(n)=(3*n*2^n+2^(n+4)+2*(-1)^n)/18 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: (1-x-x^2)/((1+x)*(1-2*x)^2).
a(n) = A001045(n-1)+2*a(n-1), n>0.
a(n)+A139790(n) = 2^(n+1) = A000079(n+1).
a(n) = A139790(n)+A140960(n).
a(n) = A001045(n)+(-1)^n*A084219(n).
a(n) = A127984(n) + 2^(n-1).  Application:  Problem 11623, AMM 119 (2012) 161. - Stephen J. Herschkorn, Feb 11 2012

Definition replaced by explicit formula by R. J. Mathar, Feb 11 2010

A127984 a(n) = (n/3 + 7/9)*2^(n - 1) + (-1)^n/9.

Original entry on oeis.org

1, 3, 7, 17, 39, 89, 199, 441, 967, 2105, 4551, 9785, 20935, 44601, 94663, 200249, 422343, 888377, 1864135, 3903033, 8155591, 17010233, 35418567, 73633337, 152859079, 316902969, 656175559, 1357090361, 2803659207, 5786275385, 11930464711, 24576757305

Offset: 1

Artur Jasinski, Feb 09 2007

a(n) is the number of runs of strictly increasing parts in all compositions of n. a(3) = 7: (1)(1)(1), (12), (2)(1), (3). - Alois P. Heinz, Apr 30 2017
From Hugo Pfoertner, Feb 19 2020: (Start)
a(n)/2^(n-2) apparently is the expected number of flips of a fair coin to completion of a game where the player advances by 1 for heads and by 2 for tails, starting at position 0 and repeating to flip until the target n+1 is exactly reached. If the position n (1 below the target) is reached, the player stays at this position and continues to flip the coin and count the flips until he can advance by 1.
The expected number of flips for targets 1, 2, 3,... , found by inversion of the corresponding Markov matrices, is 2, 2, 3, 7/2, 17/4, 39/8, 89/16, 199/32, 441/64, ...
Target 1 needs an expected number of 2 flips and would require a(0) = 1/2.
  n=1, target n+1 = 2: 1 / 2^(1-2) = 2;
  n=2, target n+1 = 3: 3 / 2^(2-2) = 3;
  n=3, target n+1 = 4: 7 / 2^(3-2) = 7/2.
(End)

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
W. Bosma, Signed bits and fast exponentiation, J. Th. des Nombres de Bordeaux Vol.13, Fasc. 1, 2001.
Aruna Gabhe, Problem 11623, Am. Math. Monthly 119 (2012) 161.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Cf. A059570, A073371, A127976, A127978, A127979, A127980, A127981, A127982, A127983, A073371, A000337, A172481.

[(n/3+7/9)*2^(n-1)+(-1)^n/9: n in [1..35]]; // Vincenzo Librandi, Jun 15 2017

A127984:=n->(n/3 + 7/9)*2^(n - 1) + (-1)^n/9; seq(A127984(n), n=1..50); # Wesley Ivan Hurt, Mar 14 2014

Table[(n/3 + 7/9)2^(n - 1) + (-1)^n/9, {n, 50}] (* Artur Jasinski *)
CoefficientList[Series[(1 - 2 x^2) / ((-1 + 2 x)^2 (1 + x)), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 15 2017 *)

a(n) = (n/3 + 7/9)*2^(n - 1) + (-1)^n/9.
From R. J. Mathar, Apr 04 2008: (Start)
O.g.f.: -x*(-1+2x^2)/((-1+2x)^2*(1+x)).
a(n) = 3*a(n-1) - 4*a(n-3). (End)
a(n) + a(n+1) = A087447(n+1). - R. J. Mathar, Feb 21 2009
A172481(n) = a(n) + 2^(n-1). Application: Problem 11623, AMM 119 (2012) 161. - Stephen J. Herschkorn, Feb 11 2012
From Wolfdieter Lang, Jun 14 2017: (Start)
a(n) = f(n+1)*2^(n-1), where f(n) is a rational Fibonacci type sequence based on fuse(a,b) = (a+b+1)/2 with f(0) = 0, f(1) = 1 and f(n) = fuse(f(n-1),f(n-2)), for n >= 2. For fuse(a,b) see the Jeff Erickson link under A188545. Proof: f(n) = (3*n+4 - (-1)^n/2^(n-2))/9, n >= 0, by induction.
a(n) = a(n-1) + a(n-2) + 2^(n-2), n >= 1, with inputs a(-1) = 0, a(0) = 1/2.
(End)
E.g.f.: (2*exp(-x) + exp(2*x)*(7 + 6*x) - 9)/18. - Stefano Spezia, Feb 19 2020

A221878 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with exactly k fixed points.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 2, 8, 2, 1, 6, 22, 5, 2, 1, 14, 57, 12, 5, 2, 1, 34, 136, 28, 12, 5, 2, 1, 78, 315, 64, 28, 12, 5, 2, 1, 178, 710, 144, 64, 28, 12, 5, 2, 1, 398, 1577, 320, 144, 64, 28, 12, 5, 2, 1, 882, 3460, 704, 320, 144, 64, 28, 12, 5, 2, 1

Offset: 1

Abdullahi Umar, Feb 28 2013

Its row sum is A221882.

			T (4,0) = 6 because there are exactly 6 order-preserving or order-reversing full contraction mappings (of a 4-chain) with no fixed point, namely: (2111), (3321), (3322), (4321), (4322), (4443).
Triangle:
1,
0, 1,
1, 2, 1,
2, 8, 2, 1,
6, 22, 5, 2, 1,
14, 57, 12, 5, 2, 1,
34, 136, 28, 12, 5, 2, 1,
78, 315, 64, 28, 12, 5, 2, 1,
178, 710, 144, 64, 28, 12, 5, 2, 1,
398, 1577, 320, 144, 64, 28, 12, 5, 2, 1,
882, 3460, 704, 320, 144, 64, 28, 12, 5, 2, 1

A. D. Adeshola, V. Maltcev and A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain, arXiv:1303.7428 [math.CO], 2013.
A. D. Adeshola, A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain, JMCC 106 (2017) 37-49

Cf. A221876, A221877, A221879, A221880, A221881, A221882.

T(n,0) = T(n-1,1), T(n,1) = A059570(n) + A221876(n,1) - n and T(n,k) = A221876 if k > 1.

Showing 1-10 of 28 results. Next

cp's OEIS Frontend

A001787 a(n) = n*2^(n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A000975 a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A124762 Number of levels for compositions in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Formula

A045883 a(n) = ((3*n+1)*2^n - (-1)^n)/9.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A000975 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).

A045883 a(n) = ((3n+1)2^n - (-1)^n)/9.

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

A027934 a(0)=0, a(1)=1, a(2)=2; for n > 2, a(n) = 3a(n-1) - a(n-2) - 2a(n-3).

A172481 a(n) = (3n2^n+2^(n+4)+2*(-1)^n)/18.