A006054 -id:A006054 - cp's OEIS frontend

A005021 Random walks (binomial transform of A006054).

1, 5, 19, 66, 221, 728, 2380, 7753, 25213, 81927, 266110, 864201, 2806272, 9112264, 29587889, 96072133, 311945595, 1012883066, 3288813893, 10678716664, 34673583028, 112584429049, 365559363741, 1186963827439, 3854047383798, 12514013318097, 40632746115136

Offset: 0

N. J. A. Sloane

Number of walks of length 2n+5 in the path graph P_6 from one end to the other one. Example: a(1)=5 because in the path ABCDEF we have ABABCDEF, ABCBCDEF, ABCDCDEF, ABCDEDEF and ABCDEFEF. - Emeric Deutsch, Apr 02 2004
Since a(n) is the binomial transform of A006054 from formula (3.63) in the Witula-Slota-Warzynski paper, it follows that a(n)=A(n;1)*(B(n;-1)-C(n;-1))-B(n;1)*B(n;-1)+C(n;1)*(A(n;-1)-B(n;-1)+C(n;-1)), where A(n;1)=A077998(n), B(n;1)=A006054(n+1), C(n;1)=A006054(n), A(n;-1)=A121449(n), B(n+1;-1)=-A085810(n+1), C(n;-1)=A215404(n) and A(n;d), B(n;d), C(n;d), n in N, d in C, denote the quasi-Fibonacci numbers defined and discussed in comments in A121449 and in the cited paper. - Roman Witula, Aug 09 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
With offset -4 this sequence 6, 1, 0, 0, 1, 5, ... appears in the formula for the n-th power of the 3 X 3 tridiagonal Matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: (M_3)^n = a(n-2)*(M_3)^2 - (6*a(n-3) - a(n-4))*M_3 + a(n-3)*1_3, with the 3 X 3 unit matrix 1_3, for n >= 0. Proof from Cayley-Hamilton: (M_3)^n = 5*(M_3)^3 - 6*M_3 + 1_3 (see A332602 for the characteristic polynomial Phi(3, x)), and the recurrence (M_3)^n = M_3*(M_3)^(n-1). For (M_3)^n[1,1] = 2*a(n-2) - 5*a(n-3) + a(n-4), for n >= 0, see A080937(n).
The formula for a(n) in terms of r = rho(7) = A160389 given below shows that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796... for n -> infinity. This is because r - 2/r = 0.692..., and r - 1 - 1/r = 0.137... .
(End)

W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025. See p. 26.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
C. J. Everett and P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45.
C. J. Everett and P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45. [Annotated scanned copy]
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
S. Morier-Genoud, V. Ovsienko and S. Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987; arXiv:1008.3359 [math.AG], 2010-2011. - From _N. J. A. Sloane_, Dec 26 2012
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
N. J. A. Sloane, Transforms
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Roman Witula, Damian Slota and Adam Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.
Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

Double partial sums of A060557. Bisection of A052547.

Cf. A094789, A094790, A080937, A160389, A116425, A322602.

I:=[1,5,19]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 18 2015

a:=k->sum(binomial(5+2*k,7*j+k-2),j=ceil((2-k)/7)..floor((7+k)/7))-sum(binomial(5+2*k,7*j+k-1),j=ceil((1-k)/7)..floor((6+k)/7)): seq(a(k),k=0..25);
A005021:=-(z-1)*(z-5)/(-1+5*z-6*z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence apart from the initial 1

LinearRecurrence[{5,-6,1}, {1,5,19}, 50] (* Roman Witula, Aug 09 2012 *)
CoefficientList[Series[1/(1 - 5 x + 6 x^2 - x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)

x='x+O('x^30); Vec(1/(1-5*x+6*x^2-x^3)) \\ G. C. Greubel, Apr 19 2018

G.f.: 1/(1-5x+6x^2-x^3). - Emeric Deutsch, Apr 02 2004
a(n) = 5*a(n-1) -6*a(n-2) +a(n-3). - Emeric Deutsch, Apr 02 2004
a(n) = Sum_{j=-infinity..infinity} (binomial(5+2*k, 7*j+k-2) - binomial(5+2*k, 7*j+k-1)) (a finite sum).
a(n-2) = 2^n*C(n;1/2)=(1/7)*((c(2)-c(4))*(c(4))^(2n) + (c(4)-c(1))*(c(1))^(2n) + (c(1)-c(2))*(c(2))^(2n)), where a(-2)=a(-1):=0, c(j):=2*cos(2Pi*j/7). This formula follows from the Binet formula for C(n;d)--one of the quasi-Fibonacci numbers (see comments in A121449 and the formula (3.17) in the Witula-Slota-Warzynski paper). - Roman Witula, Aug 09 2012
In terms of the algebraic number r = rho(7) = 2*cos(Pi/7) = A160389 of degree 3 the preceding formula gives a(n) = r^(2*(n+2))*(A1(r) + A2(r)*(r - 2/r)^(2*(n+1)) = A3(r)*(r - 1 - 1/r)^(2*(n+1)))/7, for n >= -4 (see a comment above for this offset), with A1(r) = -r^2 + 2*r + 1, A2(r) = -r^2 - r + 2, and A3(r) = 2*r^2 - r - 3. - Wolfdieter Lang, Mar 30 2020

a(25)-a(26) from Vincenzo Librandi, Sep 18 2015

A180264 Triangle, row sums = A006054; derived from an infinite lower triangular matrix with (1,1,1,...) as the leftmost column and (1,2,1,1,1,...) as other columns.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 1, 1, 4, 5, 1, 1, 2, 10, 11, 1, 1, 2, 5, 22, 25, 1, 1, 2, 5, 11, 50, 56, 1, 1, 2, 5, 11, 50, 56, 1, 1, 2, 5, 11, 25, 112, 126, 1, 1, 2, 5, 11, 25, 56, 252, 283, 1, 1, 2, 5, 11, 25, 56, 126, 566, 636, 1, 1, 2, 5, 11, 25, 56, 126, 283, 1272, 1429

Offset: 1

Gary W. Adamson, Aug 21 2010

Row sums = A006054 starting (1, 2, 5, 11, 25, 56, 126,...).

Sum of n-th row terms = rightmost term of next row.

			First few rows of the triangle =
.
1;
1, 1;
1, 2, 2;
1, 1, 4, 5;
1, 1, 2, 10, 11;
1, 1, 2, 5, 22, 25;
1, 1, 2, 5, 11, 50, 56;
1, 1, 2, 5, 11, 25, 112, 126;
1, 1, 2, 5, 11, 25, 56, 252, 283;
1, 1, 2, 5, 11, 25, 56, 126, 566, 636;
1, 1, 2, 5, 11, 25, 56, 126, 283, 1272, 1429;
1, 1, 2, 5, 11, 25, 56, 126, 283, 636, 2858, 3211;
...
Example: Row 4 = (1, 1, 4, 5) = termwise products of (1, 1, 2, 1) and (1, 1, 2, 5).

Cf. A006054

Let M = an infinite lower triangular matrix with 1's in the leftmost column,
and (1,2,1,1,1,...) as other columns. Let Q = a diagonalized variant of
A006054 (1, 1, 2, 5, 11, 25, 56,...) as the right border and the rest zeros.
Triangle A180264 = M*Q.

A144159 Eigentriangle, sum of row n terms = A006054(n+2).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 2, 2, 5, 3, 2, 4, 5, 11, 3, 3, 4, 10, 11, 25, 4, 3, 6, 10, 22, 25, 56, 4, 4, 6, 15, 22, 50, 56, 126, 5, 4, 8, 15, 33, 50, 112, 126, 283, 5, 5, 8, 20, 33, 75, 112, 252, 283, 636

Offset: 1

Gary W. Adamson, Sep 12 2008

Left border = (1, 1, 2, 2, 3, 3,...) Row sums = (1, 2, 5, 11, 25, 56, 126,...) = A006054 such that row n = A006054(n+2).

Sum of n-th row terms = rightmost term of next row.

			First few rows of the triangle =
1;
1, 1;
2, 1, 2;
2, 2, 2, 5;
3, 2, 4, 5, 11;
3, 3, 4, 10, 11, 25;
4, 3, 6, 10, 22, 25, 56;
4, 4, 6, 15, 22, 50, 56, 126;
5, 4, 8, 15, 33, 50, 112, 126, 283;
...

Cf. A006054, A008619.

Triangle read by rows, A * B, where A = an infinite lower triangular matrix with A008619: (1, 1, 2, 2, 3, 3,...) in every column. B = an infinite lower triangular matrix with A008619 as the main diagonal: (1, 2, 5, 11, 25, 56, 126,...) and the rest zeros.

A122500 Semiprimes in A006054.

Original entry on oeis.org

25, 183922, 413269, 2086561, 268550439, 77664004259, 1286498670037058, 835992504648428541, 69918194872608910320341, 157104757807495406675035, 353011186440414668176111, 13139449230370726052061293111

Offset: 1

Roger L. Bagula and Gary W. Adamson, Sep 15 2006

nonn

Cf. A006054, A006053.

semiPrimeQ[n_Integer] := Plus @@ Last /@ FactorInteger[n] == 2; s = CoefficientList[ Series[x/(x^3 - x^2 - 2*x + 1), {x, 0, 100}], x]; Select[s, SemiprimeQ@# &]
Select[LinearRecurrence[{2,1,-1},{0,0,1},100],PrimeOmega[#]==2&] (* Harvey P. Dale, Aug 21 2013 *)

Edited by N. J. A. Sloane, Sep 17 2006

More terms from Robert G. Wilson v, Sep 18 2006

A284786 Pisano period of sequence A006054 modulo n.

Original entry on oeis.org

1, 7, 26, 14, 62, 182, 42, 28, 78, 434, 266, 182, 12, 42, 806, 56, 614, 546, 254, 434, 546, 266, 1106, 364, 310, 84, 234, 42, 28, 5642, 1986, 112, 3458, 4298, 1302, 546, 2814, 1778, 156, 868, 40, 546, 42, 266, 2418, 1106, 4514, 728, 294, 2170, 7982, 84, 5726, 1638, 8246, 84, 3302, 28, 7082, 5642, 582

Offset: 1

Patrick D McLean, Apr 02 2017

nonn

Robert Israel, Mathematics StackExchange, When does x^3-x^2-2x+1 split mod p.
Wikipedia, Pisano period.

Cf. A001175 Pisano periods of Fibonacci numbers mod n.

Cf. A045472.

f:= proc(n) option remember; local F, t, k, a;
F:= ifactors(n)[2];
if nops(F) > 1 then
  return(ilcm(seq(procname(t[1]^t[2]),t=F)))
fi;
a:= [0,0,1];
for k from 1 do
  a:= [a[2],a[3],2*a[3]+a[2]-a[1] mod n];
  if  a = [0,0,1] then return k fi;
od:
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Jun 14 2017

Table[FindTransientRepeat[
    Mod[LinearRecurrence[{2, 1, -1}, {0, 0, 1}, 100000], n], 2] //
   Last // Length, {n, 1, 20}]

From Robert Israel, Jun 14 2017: (Start)
If m and n are coprime, a(m*n) = lcm(a(m),a(n)).
If p is a prime such that the polynomial x^3-x^2-2*x+1 splits into distinct factors mod p, then a(p) divides p-1. These primes are A045472. (End)

More terms from Robert Israel, Jun 14 2017

A008619 Positive integers repeated.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37, 38

Offset: 0

N. J. A. Sloane

The floor of the arithmetic mean of the first n+1 positive integers. - Cino Hilliard, Sep 06 2003
Number of partitions of n into powers of 2 where no power is used more than three times, or 4th binary partition function (see A072170).
Number of partitions of n in which the greatest part is at most 2. - Robert G. Wilson v, Jan 11 2002
Number of partitions of n into at most 2 parts. - Jon Perry, Jun 16 2003
a(n) = #{k=0..n: k+n is even}. - Paul Barry, Sep 13 2003
Number of symmetric Dyck paths of semilength n+2 and having two peaks. E.g., a(6)=4 because we have UUUUUUU*DU*DDDDDDD, UUUUUU*DDUU*DDDDDD, UUUUU*DDDUUU*DDDDD and UUUU*DDDDUUUU*DDDD, where U=(1,1), D=(1,-1) and * indicates a peak. - Emeric Deutsch, Jan 12 2004
Smallest positive integer whose harmonic mean with another positive integer is n (for n > 0). For example, a(6)=4 is already given (as 4 is the smallest positive integer such that the harmonic mean of 4 (with 12) is 6) - but the harmonic mean of 2 (with -6) is also 6 and 2 < 4, so the two positive integer restrictions need to be imposed to rule out both 2 and -6.
Second outermost diagonal of Losanitsch's triangle (A034851). - Alonso del Arte, Mar 12 2006
Arithmetic mean of n-th row of A080511. - Amarnath Murthy, Mar 20 2003
a(n) is the number of ways to pay n euros (or dollars) with coins of one and two euros (respectively dollars). - Richard Choulet and Robert G. Wilson v, Dec 31 2007
Inverse binomial transform of A045623. - Philippe Deléham, Dec 30 2008
Coefficient of q^n in the expansion of (m choose 2)_q as m goes to infinity. - Y. Kelly Itakura (yitkr(AT)mta.ca), Aug 21 2002
This Itakura comment follows from a partial fraction decomposition (m choose 2)q = [(1-q^(2m-2))/(1+q) + (1-q^(2m-2))/(1-q) +2 (1-q^(m-1))^2/(1-q)^2]/4. Interpreted as generating functions in q, they have convolution structures; the first term in the numerator creates +1,-1,+1,-1 etc, the 2nd term creates +1,+1,+1,+1 etc., the 3rd term 2,4,6,8, etc. as m->infinity. - _R. J. Mathar, Sep 25 2008
Binomial transform of (-1)^n*A034008(n) = [1,0,1,-2,4,-8,16,-32,...]. - Philippe Deléham, Nov 15 2009
From Jon Perry_, Nov 16 2010: (Start)
Column sums of:
  1 1 1 1 1 1...
      1 1 1 1...
          1 1...
  ..............
  --------------
  1 1 2 2 3 3...  (End)
This sequence is also the half-convolution of the powers of 1 sequence A000012 with itself. For the definition of half-convolution see a comment on A201204, where also the rule for the o.g.f. is given. - Wolfdieter Lang, Jan 09 2012
a(n) is also the number of roots of the n-th Bernoulli polynomial in the right half-plane for n>0. - Michel Lagneau, Nov 08 2012
a(n) is the number of symmetry-allowed, linearly-independent terms at n-th order in the series expansion of the Exe vibronic perturbation matrix, H(Q) (cf. Viel & Eisfeld). - Bradley Klee, Jul 21 2015
a(n) is the number of distinct integers in the n-th row of Pascal's triangle. - Melvin Peralta, Feb 03 2016
a(n+1) for n >= 3 is the diameter of the Generalized Petersen Graph G(n, 1). - Nick Mayers, Jun 06 2016
The arithmetic function v_1(n,2) as defined in A289198. - Robert Price, Aug 22 2017
Also, this sequence is the second column in the triangle of the coefficients of the sum of two consecutive Fibonacci polynomials F(n+1, x) and F(n, x) (n>=0) in ascending powers of x. - Mohammad K. Azarian, Jul 18 2018
a(n+2) is the least k such that given any k integers, there exist two of them whose sum or difference is divisible by n. - Pablo Hueso Merino, May 09 2020
Column k = 2 of A051159. - John Keith, Jun 28 2021

D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 100.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 109, Eq. [6c]; p. 116, P(n,2).
D. Parisse, 'The tower of Hanoi and the Stern-Brocot Array', Thesis, Munich 1997

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Andrei Asinowski, Cyril Banderier and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
L. Colmenarejo, Combinatorics on several families of Kronecker coefficients related to plane partitions, arXiv:1604.00803 [math.CO], 2016. See Table 1 p. 5.
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.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 120
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 209
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 351
Gerzson Keri and Patric R. J. Östergård, The Number of Inequivalent (2R+3,7)R Optimal Covering Codes, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.7.
L. F. Klosinski, G. L. Alexanderson and A. P. Hillman, The William Lowell Putnam Mathematical Competition, Amer. Math. Monthly 91 (1984), 487-495. See Problem B2.
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
Narad Rampersad and Max Wiebe, Sums of products of binomial coefficients mod 2 and 2-regular sequences, arXiv:2309.04012 [math.NT], 2023.
Bruce Reznick, Some binary partition functions, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), 451-477, Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990.
Alexandra Viel and Wolfgang Eisfeld, Effects of higher order Jahn-Teller coupling on the nuclear dynamics, J. Chem. Phys., 120, 4603 (2004).
Eric Weisstein's World of Mathematics, Legendre-Gauss Quadrature
Index entries for sequences related to Stern's sequences
Index entries for related partition-counting sequences
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).
Index entries for Molien series

Essentially same as A004526.
Harmonic mean of a(n) and A056136 is n.
Cf. A001057, A065033, A001399, A001400, A001401.
a(n)=A010766(n+2, 2).
Cf. A010551 (partial products).
Cf. A263997 (a block spiral).
Cf. A289187.
Column 2 of A235791.

a008619 = (+ 1) . (`div` 2)
a008619_list = concatMap (\x -> [x,x]) [1..]
-- Reinhard Zumkeller, Apr 02 2012

I:=[1,1,2]; [n le 3 select I[n] else Self(n-1)+Self(n-2)-Self(n-3): n in [1..100]]; // Vincenzo Librandi, Feb 04 2015

a:= n-> iquo(n+2, 2): seq(a(n), n=0..75);

Flatten[Table[{n,n},{n,35}]] (* Harvey P. Dale, Sep 20 2011 *)
With[{c=Range[40]},Riffle[c,c]] (* Harvey P. Dale, Feb 23 2013 *)
CoefficientList[Series[1/(1 - x - x^2 + x^3), {x, 0, 75}], x] (* Robert G. Wilson v, Feb 05 2015 *)
LinearRecurrence[{1, 1, -1}, {1, 1, 2}, 75] (* Robert G. Wilson v, Feb 05 2015 *)
Table[QBinomial[n, 2, -1], {n, 2, 75}] (* John Keith, Jun 28 2021 *)

PARI
```
a(n)=n\2+1
```

def A008619(n): return (n>>1)+1 # Chai Wah Wu, Jul 07 2022

a = lambda n: 1 if n==0 else a(n-1)+1 if 2.divides(n) else a(n-1) # Peter Luschny, Feb 05 2015

(2 to 99).map( / 2) // _Alonso del Arte, May 09 2020

Euler transform of [1, 1].
a(n) = 1 + floor(n/2).
G.f.: 1/((1-x)(1-x^2)).
E.g.f.: ((3+2*x)*exp(x) + exp(-x))/4.
a(n) = a(n-1) + a(n-2) - a(n-3) = -a(-3-n).
a(0) = a(1) = 1 and a(n) = floor( (a(n-1) + a(n-2))/2 + 1 ).
a(n) = (2*n + 3 + (-1)^n)/4. - Paul Barry, May 27 2003
a(n) = Sum_{k=0..n} Sum_{j=0..k} Sum_{i=0..j} binomial(j, i)*(-2)^i. - Paul Barry, Aug 26 2003
E.g.f.: ((1+x)*exp(x) + cosh(x))/2. - Paul Barry, Sep 13 2003
a(n) = A108299(n-1,n)*(-1)^floor(n/2) for n > 0. - Reinhard Zumkeller, Jun 01 2005
a(n) = A108561(n+2,n) for n > 0. - Reinhard Zumkeller, Jun 10 2005
a(n) = A125291(A125293(n)) for n>0. - Reinhard Zumkeller, Nov 26 2006
a(n) = ceiling(n/2), n >= 1. - Mohammad K. Azarian, May 22 2007
INVERT transformation yields A006054 without leading zeros. INVERTi transformation yields negative of A124745 with the first 5 terms there dropped. - R. J. Mathar, Sep 11 2008
a(n) = A026820(n,2) for n > 1. - Reinhard Zumkeller, Jan 21 2010
a(n) = n - a(n-1) + 1 (with a(0)=1). - Vincenzo Librandi, Nov 19 2010
a(n) = A000217(n) / A110654(n). - Reinhard Zumkeller, Aug 24 2011
a(n+1) = A181971(n,n). - Reinhard Zumkeller, Jul 09 2012
1/(1+2/(2+3/(3+4/(4+5/(5+...(continued fraction))))) = 1/(e-1), see A073333. - Philippe Deléham, Mar 09 2013
a(n) = floor(A000217(n)/n), n > 0. - L. Edson Jeffery, Jul 26 2013
a(n) = n*a(n-1) mod (n+1) = -a(n-1) mod (n+1), the least positive residue modulo n+1 for each expression for n > 0, with a(0) = 1 (basically restatements of Vincenzo Librandi's formula). - Rick L. Shepherd, Apr 02 2014
a(n) = (a(0) + a(1) + ... + a(n-1))/a(n-1), where a(0) = 1. - Melvin Peralta, Jun 16 2015
a(n) = Sum_{k=0..n} (-1)^(n-k) * (k+1). - Rick L. Shepherd, Sep 18 2020
a(n) = a(n-2) + 1 for n >= 2. - Vladimír Modrák, Sep 29 2020
a(n) = A004526(n)+1. - Chai Wah Wu, Jul 07 2022

Additional remarks from Daniele Parisse
Edited by N. J. A. Sloane, Sep 06 2009
Partially edited by Joerg Arndt, Mar 11 2010

A007583 a(n) = (2^(2*n + 1) + 1)/3.

Original entry on oeis.org

1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763, 699051, 2796203, 11184811, 44739243, 178956971, 715827883, 2863311531, 11453246123, 45812984491, 183251937963, 733007751851, 2932031007403, 11728124029611, 46912496118443, 187649984473771, 750599937895083

Offset: 0

Simon Plouffe

Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1)=u(k)+v(k)-w(k), v(k+1)=u(k)-v(k)+w(k), w(k+1)=-u(k)+v(k)+w(k); let M(k)=Max(u(k),v(k),w(k)); then a(n)=M(2n)=M(2n-1). - Benoit Cloitre, Mar 25 2002
Also the number of words of length 2n generated by the two letters s and t that reduce to the identity 1 by using the relations ssssss=1, tt=1 and stst=1. The generators s and t along with the three relations generate the dihedral group D6=C2xD3. - Jamaine Paddyfoot (jay_paddyfoot(AT)hotmail.com) and John W. Layman, Jul 08 2002
Binomial transform of A025192. - Paul Barry, Apr 11 2003
Number of walks of length 2n+1 between two adjacent vertices in the cycle graph C_6. Example: a(1)=3 because in the cycle ABCDEF we have three walks of length 3 between A and B: ABAB, ABCB and AFAB. - Emeric Deutsch, Apr 01 2004
Numbers of the form 1 + Sum_{i=1..m} 2^(2*i-1). - Artur Jasinski, Feb 09 2007
Prime numbers of the form 1+Sum[2^(2n-1)] are in A000979. Numbers x such that 1+Sum[2^(2n-1)] is prime for n=1,2,...,x is A127936. - Artur Jasinski, Feb 09 2007
Related to A024493(6n+1), A131708(6n+3), A024495(6n+5). - Paul Curtz, Mar 27 2008
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-6, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^(n-1)*charpoly(A,2). - Milan Janjic, Feb 21 2010
Number of toothpicks in the toothpick structure of A139250 after 2^n stages. - Omar E. Pol, Feb 28 2011
Numbers whose binary representation is "10" repeated (n-1) times with "11" appended on the end, n >= 1. For example 171 = 10101011 (2). - Omar E. Pol, Nov 22 2012
a(n) is the smallest number for which A072219(a(n)) = 2*n+1. - Ramasamy Chandramouli, Dec 22 2012
An Engel expansion of 2 to the base b := 4/3 as defined in A181565, with the associated series expansion 2 = b + b^2/3 + b^3/(3*11) + b^4/(3*11*43) + .... Cf. A007051. - Peter Bala, Oct 29 2013
The positive integer solution (x,y) of 3*x - 2^n*y = 1, n>=0, with smallest x is (a(n/2), 2) if n is even and (a((n-1)/2), 1) if n is odd. - Wolfdieter Lang, Feb 15 2014
The smallest positive number that requires at least n additions and subtractions of powers of 2 to be formed. See Puzzling StackExchange link. - Alexander Cooke Jul 16 2023

H. W. Gould, Combinatorial Identities, Morgantown, 1972, (1.77), page 10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..170
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Cecilia Bebeacua, Toufik Mansour, Alexander Postnikov, and Simone Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Greg Bell, Austin Lawson, Neil Pritchard, and Dan Yasaki, On locally infinite Cayley graphs of the integers, arXiv preprint arXiv:1711.00809 [math.GT], 2017. See lambda_2.
Phillip G. Bradford, Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability, arXiv:1802.05239 [cs.DS], 2018.
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in types A, B and D, arXiv:1507.04803 [math.CO], 2015.
Ernesto Estrada and José A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013.
Ernesto Estrada and José A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 35.
Sungpyo Hong and Jin Ho Kwak, Regular fourfold coverings with respect to the identity automorphism, J. Graph Theory, 17 (1993), 621-627.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 893
Dmitry Kamenetsky, A magic grasshopper, Puzzling StackExchange, 2023.
Wolfdieter Lang, On Collatz' Words, Sequences and Trees, arXiv preprint arXiv:1404.2710 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.11.7.
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 5.
Quynh Nguyen, Jean Pedersen, and Hien T. Vu, New Integer Sequences Arising From 3-Period Folding Numbers, Vol. 19 (2016), Article 16.3.1.
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. also A006054, A006356, A005578, A075680.
Partial sums of A081294.
Cf. A002450, A004171, A007051, A083065, A083066, A083884.
Cf. A000978, A000979, A124400, A124401, A127936, A127955, A127956, A127957, A127958.
Cf. location of records in A007302.

List([0..25], n-> (2^(2*n+1) + 1)/3); # G. C. Greubel, Dec 25 2019

a007583 = (`div` 3) . (+ 1) . a004171
-- Reinhard Zumkeller, Jan 09 2013

[(2^(2*n+1) + 1)/3: n in [0..30] ]; // Vincenzo Librandi, Apr 28 2011

a[0]:=1:for n from 1 to 50 do a[n]:=4*a[n-1]-1 od: seq(a[n], n=0..23); # Zerinvary Lajos, Feb 22 2008, with correction by K. Spage, Aug 20 2014
A007583 := proc(n)
    (2^(2*n+1)+1)/3 ;
end proc: # R. J. Mathar, Feb 19 2015

(* From Michael De Vlieger, Aug 22 2016 *)
Table[(2^(2n+1) + 1)/3, {n, 0, 23}]
Table[1 + 2Sum[4^k, {k, 0, n-1}], {n, 0, 23}]
NestList[4# -1 &, 1, 23]
Table[Sum[Binomial[n+k, 2k]/2^(k-n), {k, 0, n}], {n, 0, 23}]
CoefficientList[Series[(1-2x)/(1-5x+4x^2), {x, 0, 23}], x] (* End *)

a(n)=sum(k=-n\3,n\3,binomial(2*n+1,n+1+3*k))

a=1; for(n=1,23, print1(a,", "); a=bitor(a,3*a)) \\ K. Spage, Aug 20 2014

Vec((1-2*x)/(1-5*x+4*x^2) + O(x^30)) \\ Altug Alkan, Dec 08 2015

apply( {A007583(n)=2<<(2*n)\/3}, [0..25]) \\ M. F. Hasler, Nov 30 2021

[(2^(2*n+1) + 1)/3 for n in (0..25)] # G. C. Greubel, Dec 25 2019

a(n) = 2*A002450(n) + 1.
From Wolfdieter Lang, Apr 24 2001: (Start)
a(n) = Sum_{m = 0..n} A060920(n, m) = A002450(n+1) - 2*A002450(n).
G.f.: (1-2*x)/(1-5*x+4*x^2). (End)
a(n) = Sum_{k = 0..n} binomial(n+k, 2*k)/2^(k - n).
a(n) = 4*a(n-1) - 1, n > 0.
From Paul Barry, Mar 17 2003: (Start)
a(n) = 1 + 2*Sum_{k = 0..n-1} 4^k;
a(n) = A001045(2n+1). (End)
a(n) = A020988(n-1) + 1 = A039301(n+1) - 1 = A083584(n-1) + 2. - Ralf Stephan, Jun 14 2003
a(0) = 1; a(n+1) = a(n) * 4 - 1. - Regis Decamps (decamps(AT)users.sf.net), Feb 04 2004 (correction to lead index by K. Spage, Aug 20 2014)
a(n) = Sum_{i + j + k = n; 0 <= i, j, k <= n} (n+k)!/i!/j!/(2*k)!. - Benoit Cloitre, Mar 25 2004
a(n) = 5*a(n-1) - 4*a(n-2). - Emeric Deutsch, Apr 01 2004
a(n) = 4^n - A001045(2*n). - Paul Barry, Apr 17 2004
a(n) = 2*(A001045(n))^2 + (A001045(n+1))^2. - Paul Barry, Jul 15 2004
a(n) = left and right terms in M^n * [1 1 1] where M = the 3X3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 1 1] = [a(n) A002450(n+1) a(n)] E.g. a(3) = 43 since M^n * [1 1 1] = [43 85 43] = [a(3) A002450(4) a(3)]. - Gary W. Adamson, Dec 18 2004
a(n) = A072197(n) - A020988(n). - Creighton Dement, Dec 31 2004
a(n) = A139250(2^n). - Omar E. Pol, Feb 28 2011
a(n) = A193652(2*n+1). - Reinhard Zumkeller, Aug 08 2011
a(n) = Sum_{k = -floor(n/3)..floor(n/3)} binomial(2*n, n+3*k)/2. - Mircea Merca, Jan 28 2012
a(n) = 2^(2*(n+1)) - A072197(n). - Vladimir Pletser, Apr 12 2014
a(n) == 2*n + 1 (mod 3). Indeed, from Regis Decamps' formula (Feb 04 2004) we have a(i+1) - a(i) == -1 (mod 3), i= 0, 1, ..., n - 1. Summing, we have a(n) - 1 == -n (mod 3), and the formula follows. - Vladimir Shevelev, May 20 2015
For n > 0 a(n) = A133494(0) + 2 * (A133494(n) + Sum_{x = 1..n - 1}Sum_{k = 0..x - 1}(binomial(x - 1, k)*(A133494(k+1) + A133494(n-x+k)))). - J. Conrad, Dec 06 2015
a(n) = Sum_{k = 0..2n} (-2)^k == 1 + Sum_{k = 1..n} 2^(2k-1). - Bob Selcoe, Aug 21 2016
E.g.f.: (1 + 2*exp(3*x))*exp(x)/3. - Ilya Gutkovskiy, Aug 21 2016
A075680(a(n)) = 1, for n > 0. - Ralf Stephan, Jun 17 2025

A006356 a(n) = 2*a(n-1) + a(n-2) - a(n-3) for n >= 3, starting with a(0) = 1, a(1) = 3, and a(2) = 6.

Original entry on oeis.org

1, 3, 6, 14, 31, 70, 157, 353, 793, 1782, 4004, 8997, 20216, 45425, 102069, 229347, 515338, 1157954, 2601899, 5846414, 13136773, 29518061, 66326481, 149034250, 334876920, 752461609, 1690765888, 3799116465, 8536537209, 19181424995

Offset: 0

N. J. A. Sloane

Number of distributive lattices; also number of paths with n turns when light is reflected from 3 glass plates.
Let u(k), v(k), w(k) be defined by u(1) = 1, v(1) = 0, w(1) = 0 and u(k+1) = u(k) + v(k) + w(k), v(k+1) = u(k) + v(k), w(k+1) = u(k); then {u(n)} = 1, 1, 3, 6, 14, 31, ... (this sequence with an extra initial 1), {v(n)} = 0, 1, 2, 5, 11, 25, ... (A006054 with its initial 0 deleted) and {w(n)} = {u(n)} prefixed by an extra 0 = A077998 with an extra initial 0. - Benoit Cloitre, Apr 05 2002
Also u(k)^2 + v(k)^2 + w(k)^2 = u(2*k). - Gary W. Adamson, Dec 23 2003
The n-th term of the series is the number of paths for a ray of light that enters two layers of glass and then is reflected exactly n times before leaving the layers of glass.
One such path (with 2 plates of glass and 3 reflections) might be:
...\........./..................
--------------------------------
....\/\..../....................
--------------------------------
........\/......................
--------------------------------
For a k-glass sequence, say a(n,k), a(n,k) is always asymptotic to z(k)*w(k)^n where w(k) = (1/2)/cos(k*Pi/(2*k+1)) and it is conjectured that z(k) is the root 1 < x < 2 of a polynomial of degree Phi(2k+1)/2.
Number of ternary sequences of length n-1 such that every pair of consecutive digits has a sum less than 3. That is to say, the pairs (1,2), (2,1) and (2,2) do not appear. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 07 2004
Number of weakly up-down sequences of length n using the digits {1,2,3}. When n=2 the sequences are 11, 12, 13, 22, 23, 33.
Form the graph with matrix A = [1, 1, 1; 1, 0, 0; 1, 0, 1]. Then A006356 counts walks of length n that start at the degree 4 vertex. - Paul Barry, Oct 02 2004
In general, the g.f. for p glass plates is: A(x) = F_{p-1}(-x)/F_p(x) where F_p(x) = Sum_{k=0..p} (-1)^[(k+1)/2]*C([(p+k)/2],k)*x^k. - Paul D. Hanna, Feb 06 2006
Equals the INVERT transform of (1, 2, 1, 1, 1, ...) equivalent to a(n) = a(n-1) + 2*a(n-2) + a(n-3) + a(n-4) + ... + 1. a(6) = 70 = (31 + 2*14 + 6 + 3 + 1 + 1). - Gary W. Adamson, Apr 27 2009
a(n) = the number of terms in the n-th iterate of sequence A179542 generated from the rules a(0) = 1, then (1->1,2,3), (2->1,2), (3->1).
Example: 3rd iterate = (1,2,3,1,2,1,1,2,3,1,2,1,2,3) = 14 terms composed of a frequency of (6, 5, 3): (1's, 2's, and 3's), where a(3) = 14, and the [6, 5, 3] = top row and left column of the 3rd power of M, the matrix generator [1,1,1; 1,1,0; 1,0,0] or a(2) = 6, A006054(4) = 5, and a(1) = 3.
Given the heptagon diagonal lengths with edge = 1: (a = 1, b = 1.80193773..., c = 2.24697...) = (1, 2*cos(Pi/7), (1 + 2*cos(2*Pi/7))), and using the diagonal product formulas in [Steinbach], we obtain: c^n = c*a(n-2) + b*A006054(n) + a(n-3) corresponding to the top row of M^(n-1), in the case M^3 = [6, 5, 3]. Example: c^4 = 25.491566... = 6*c + 5*b + 3 = 13.481... + 9.00968... + 3. - Gary W. Adamson, Jul 18 2010
Equals row sums of triangle A180262. - Gary W. Adamson, Aug 21 2010
The number of the one-sided n-step prudent walks, avoiding 2 or more consecutive east steps. - Shanzhen Gao, Apr 27 2011
a(n) = [A_{7,2}^(n+2)](1,1), where A{7,2} is the 3 X 3 unit-primitive matrix (see [Jeffery]) A_{7,2} = [0,0,1; 0,1,1; 1,1,1]. The denominator of the generating function for this sequence is also the characteristic polynomial of A_{7,2}. - L. Edson Jeffery, Dec 06 2011 [See the comments for sequence A306334. - Petros Hadjicostas, Nov 17 2019]
a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1] or of the 3 X 3 matrix [1, 1, 1; 1, 1, 0; 1, 0, 0]. - R. J. Mathar, Feb 03 2014
Successive sequences in this set (A006356, A006357, A006358, etc.) can be generated as follows: Begin with (1, 1, 1, 1, 1, 1, ...); and perform an operation with three steps to get the next sequence in the series. First, put alternate signs in the current series: With (1, 1, 1, ...) this equals (1, -1, 1, -1, ...); then take the inverse, getting (1, 1, 0, 0, 0, ...). Take the INVERT transform of the last step, getting (1, 2, 3, 5, 8, ...). Repeat the three steps using (1, 2, 3, 5, ...) --> (1, -2, 3, -5) --> (1, 2, 1, 1, 1, ...) --> (1, 3, 6, 14, 31, ...). Repeat the three steps using (1, 3, 6, 14, 31, ...), getting (1, 4, 10, 30, 85, ...) = A006357; and so on. - Gary W. Adamson, Aug 08 2019
Let W_n be the fence poset (a.k.a. zig-zag poset) of size n.  Let [2] be a chain of size 2.  Then a(n) is the number of antichains in the product poset W_n X [2]. See Berman- Koehler link. - Geoffrey Critzer, Jun 13 2023
a(n) is the number of double-dimer covers of the 2 X (n+1) square grid graph. See Musiker et al. link. - Nicholas Ovenhouse, Jan 07 2024
In general, the number of weakly up-down words of length n over an alphabet of size k is given by 4/(2*k+1)*|Sum_{j = 1..k} sin^2(2*j*Pi/(2*k+1))/(2*cos^2(2*j*Pi/(2*k+1)))^(n+1)| and the corresponding g. f. is given by V_(k-1)(-x/2)/W_k(x/2) if k is even and -W_(k-1)(-x/2) / V_k(x/2) if k is odd, where V_m(x) and W_m(x) are the Chebyshev polynomials of the third and fourth kind, respectively (see Paul D. Hanna's comment above and the Fried link). - Sela Fried, Apr 01 2025

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 120).
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd edition, p. 291 (very briefly without generalizations).
J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.
Jay Kappraff, Beyond Measure, A Guided Tour Through Nature, Myth and Number, World Scientific, 2002.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
J. Berman and P. Köhler, On Dedekind Numbers and Two Sequences of Knuth, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.
Sela Fried, A formula for the number of up-down words, arXiv:2503.02005 [math.CO], 2025.
Emma L. L. Gao, Sergey Kitaev, and Philip B. Zhang, Pattern-avoiding alternating words, arXiv:1505.04078 [math.CO], 2015.
Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Manfred Goebel, Rewriting Techniques and Degree Bounds for Higher Order Symmetric Polynomials, Applicable Algebra in Engineering, Communication and Computing (AAECC), Volume 9, Issue 6 (1999), 559-573.
V. E. Hoggatt Jr. and M. Bicknell-Johnson, Reflections across two and three glass plates, Fibonacci Quarterly, volume 17 (1979), 118-142.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 451
L. E. Jeffery, Unit-primitive matrices
B. Junge and V. E. Hoggatt, Jr., Polynomials arising from reflections across multiple plates, Fib. Quart., 11 (1973), 285-291.
Peter Köhler, The Central Decomposition of FD_01(n), Order (2021).
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
Julien Leroy, Michel Rigo, and Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
Leo Moser, Problem B-6: some reflections, Fib. Quart. Vol. 1, No. 4 (1963), 75-76.
Leo Moser and Max Wyman, Multiple reflections, Fib. Quart., 11 (1973).
Gregg Musiker, Ralf Schiffler, Nicholas Ovenhouse, and Sylvester Zhang, Higher Dimer Covers on Snake Graphs, arXiv:2306.14389 [math.CO], 2023.
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.
Lingjuan Shi and Kai Deng, The Numbers of Perfect and Maximal Matchings in Double Hexagonal Chains, Match Comm. Math. Comp. Chem. (2025) 659-685. See p. 8.
P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
R. Witula, D. Slota and A. Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.
Index entries for linear recurrences with constant coefficients, signature (2,1,-1).

Cf. A000217, A000330, A050446, A050447, A006054, A077998, A052534, A052994, A052949.
See also A006357-A006359, A025030, A030112-A030116.
Cf. A038196 (3-wave sequence).
Cf. A179542. - Gary W. Adamson, Jul 18 2010
Cf. A180262. - Gary W. Adamson, Aug 21 2010
Cf. A033303, A190360, A306334.

a006056 n = a006056_list !! n
a006056_list = 1 : 3 : 6 : zipWith (+) (map (2 *) $ drop 2 a006056_list)
   (zipWith (-) (tail a006056_list) a006056_list)
-- Reinhard Zumkeller, Oct 14 2011

[ n eq 1 select 1 else n eq 2 select 3 else n eq 3 select 6 else 2*Self(n-1)+Self(n-2)- Self(n-3): n in [1..40] ] ; // Vincenzo Librandi, Aug 20 2011

A006356:=-(-1-z+z**2)/(1-2*z-z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation

LinearRecurrence[{2,1,-1},{1,3,6},30] (* or *) CoefficientList[ Series[ (1+x-x^2)/(1-2x-x^2+x^3),{x,0,30}],x] (* Harvey P. Dale, Jul 06 2011 *)
Table[If[n==0, a2=0; a1=1; a0=1, a3=a2; a2=a1; a1=a0; a0=2*a1+a2-a3], {n, 0, 29}] (* Jean-François Alcover, Apr 30 2013 *)

a(n):=sum(sum((sum(binomial(j,-3*k+2*j+i)*(-1)^(j-k)*binomial(k,j),j,0,k))*binomial(n+k-i-1,k-1),i,k,n),k,1,n); /* Vladimir Kruchinin, May 05 2011 */

{a(n)=local(p=3);polcoeff(sum(k=0,p-1,(-1)^((k+1)\2)*binomial((p+k-1)\2,k)* (-x)^k)/sum(k=0,p,(-1)^((k+1)\2)*binomial((p+k)\2,k)*x^k+x*O(x^n)),n)} \\ Paul D. Hanna, Feb 06 2006

Vec((1+x-x^2)/(1-2*x-x^2+x^3)+O(x^66)) \\ Joerg Arndt, Apr 30 2013

from math import comb
def A006356(n): return sum(comb(j,a)*comb(k,j)*comb(n+k-i,k-1)*(-1 if j-k&1 else 1) for k in range(1,n+2) for i in range(k,n+2) for j in range(k+1) if (a:=-3*k+2*j+i)>=0) # Chai Wah Wu, Feb 19 2024

a(n) is asymptotic to z(3)*w(3)^n where w(3) = (1/2)/cos(3*Pi/7) and z(3) is the root 1 < X < 2 of P(3, X) = 1 - 14*X - 49*X^2 + 49*X^3. w(3) = 2.2469796.... z(3) = 1.220410935...
G.f.: (1 + x - x^2)/(1 - 2*x - x^2 + x^3). - Paul D. Hanna, Feb 06 2006
a(n) = a(n-1) + a(n-2) + A006054(n+1). - Gary W. Adamson, Jun 05 2008
a(n) = A006054(n+2) + A006054(n+1) - A006054(n). - R. J. Mathar, Apr 07 2011
a(n-1) = Sum_{k = 1..n} Sum_{i = k..n} Sum_{j = 0..k} binomial(j, -3*k+2*j+i) * (-1)^(j-k) * binomial(k, j) * binomial(n+k-i-1, k-1). - Vladimir Kruchinin, May 05 2011
Sum_{k=0..n} a(k) = a(n+1) - a(n-1) - 1. - Greg Dresden and Mina BH Arsanious, Aug 23 2023

Recurrence, alternative description from Jacques Haubrich (jhaubrich(AT)freeler.nl)

Alternative definition added by Andrew Niedermaier, Nov 11 2008

A006053 a(n) = a(n-1) + 2*a(n-2) - a(n-3), with a(0) = a(1) = 0, a(2) = 1.

Original entry on oeis.org

0, 0, 1, 1, 3, 4, 9, 14, 28, 47, 89, 155, 286, 507, 924, 1652, 2993, 5373, 9707, 17460, 31501, 56714, 102256, 184183, 331981, 598091, 1077870, 1942071, 3499720, 6305992, 11363361, 20475625, 36896355, 66484244, 119801329, 215873462, 388991876, 700937471

Offset: 0

N. J. A. Sloane

a(n+1) = S(n) for n>=1, where S(n) is the number of 01-words of length n, having first letter 1, in which all runlengths of 1's are odd. Example: S(4) counts 1000, 1001, 1010, 1110. See A077865. - Clark Kimberling, Jun 26 2004
For n>=1, number of compositions of n into floor(j/2) kinds of j's (see g.f.). - Joerg Arndt, Jul 06 2011
Counts walks of length n between the first and second nodes of P_3, to which a loop has been added at the end. Let A be the adjacency matrix of the graph P_3 with a loop added at the end. A is a 'reverse Jordan matrix' [0,0,1; 0,1,1; 1,1,0]. a(n) is obtained by taking the (1,2) element of A^n. - Paul Barry, Jul 16 2004
Interleaves A094790 and A094789. - Paul Barry, Oct 30 2004
a(n) appears in the formula for the nonnegative powers of rho:= 2*cos(Pi/7), the ratio of the smaller diagonal in the heptagon to the side length s=2*sin(Pi/7), when expressed in the basis <1,rho,sigma>, with sigma:=rho^2-1, the ratio of the larger heptagon diagonal to the side length, as follows. rho^n = C(n)*1 + C(n+1)*rho + a(n)*sigma, n>=0, with C(n) = A052547(n-2). See the Steinbach reference, and a comment under A052547. - Wolfdieter Lang, Nov 25 2010
If with the above notations the power basis <1,rho,rho^2> of Q(rho) is used, nonnegative powers of rho are given by rho^n  = -a(n-1)*1 + A052547(n-1)*rho + a(n)*rho^2. For negative powers see A006054. - Wolfdieter Lang, May 06 2011
-a(n-1) also appears in the formula for the nonpositive powers of sigma (see the above comment for the definition, and the Steinbach basis <1,rho,sigma>) as follows: sigma^(-n) = A(n)*1 -a(n+1)*rho -A(n-1)*sigma, with A(n) = A052547(n), A(-1):=0. - Wolfdieter Lang, Nov 25 2010

			G.f. = x^2 + x^3 + 3*x^4 + 4*x^5 + 9*x^6 + 14*x^7 + 28*x^8 + 47*x^9 + ...
Regarding the description "number of compositions of n into floor(j/2) kinds of j's," the a(6)=9 compositions of 6 are (2a, 2a, 2a), (3a, 3a), (2a, 4a), (2a, 4b), (4a, 2a), (4b, 2a), (6a), (6b), (6c). - _Bridget Tenner_, Feb 25 2022

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. Witula, E. Hetmaniok and D. Slota, Sums of the powers of any order roots taken from the roots of a given polynomial, Proceedings of the 15th International Conference on Fibonacci Numbers and Their Applications (2012).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Robin Chapman and Nicholas C. Singer, Eigenvalues of a bidiagonal matrix, Amer. Math. Monthly, 111 (2004), p. 441.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, On a variant of Flory model, arXiv:2210.12411 [math.CO], 2022.
Jia Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463 [math.CO], 2025. See p. 9.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 433
Mohammed L. Nadji, Moussa Ahmia, Daniel F. Checa, and José L. Ramírez, Arndt Compositions with Restricted Parts, Palindromes, and Colored Variants, J. Int. Seq. (2025) Vol. 28, Issue 3, Article 25.3.6. See p. 11.
László Németh and Dragan Stevanović, Graph solution of system of recurrence equations, Research Gate, 2023. See Table 2 at p. 6.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
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
R. Sachdeva and A. K. Agarwal, Combinatorics of certain restricted n-color composition functions, Discrete Mathematics, 340, (2017), 361-372.
Genki Shibukawa, New identities for some symmetric polynomials and their applications, arXiv:1907.00334 [math.CA], 2019.
P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
Kai Wang, Fibonacci Numbers And Trigonometric Functions Outline, (2019).
Roman Witula, Ramanujan Type Trigonometric Formulas: The General Form for the Argument 2Pi/7, J. Integer Seq., 12 (2009), Article 09.8.5.
Index entries for linear recurrences with constant coefficients, signature (1,2,-1).

Cf. A006054, A052547, A077865, A094789, A094790, A096975, A096976.

Cf. A120757, A187065, A187066, A187067, A214683, A215076, A215100.

a006053 n = a006053_list !! n
a006053_list = 0 : 0 : 1 : zipWith (+) (drop 2 a006053_list)
   (zipWith (-) (map (2 *) $ tail a006053_list) a006053_list)
-- Reinhard Zumkeller, Oct 14 2011

[ n eq 1 select 0 else n eq 2 select 0 else n eq 3 select 1 else Self(n-1) +2*Self(n-2) -Self(n-3): n in [1..40] ]; // Vincenzo Librandi, Aug 19 2011

a[0]:=0: a[1]:=0: a[2]:=1: for n from 3 to 40 do a[n]:=a[n-1]+2*a[n-2]-a[n-3] od:seq(a[n], n=0..40); # Emeric Deutsch
A006053:=z**2/(1-z-2*z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation

LinearRecurrence[{1,2,-1}, {0,0,1}, 50]  (* Vladimir Joseph Stephan Orlovsky, May 25 2011 *)

{a(n) = if( n<0, n = -1-n; polcoeff( -1 / (1 - 2*x - x^2 + x^3) + x * O(x^n), n), polcoeff( x^2 / (1 - x - 2*x^2 + x^3) + x * O(x^n), n))}; /* Michael Somos, Nov 30 2014 */

@CachedFunction
def a(n): # a = A006053
    if (n<3): return (n//2)
    else: return a(n-1) + 2*a(n-2) - a(n-3)
[a(n) for n in range(41)] # G. C. Greubel, Feb 12 2023

G.f.: x^2/(1 - x - 2*x^2 + x^3). - Emeric Deutsch, Dec 14 2004
a(n) = c^(n-2) - a(n-1)*(c-1) + (1/c)*a(n-2) for n > 3 where c = 2*cos(Pi/7). Example: a(7) = 14 = c^5 - 9*(c-1) + 4/c = 18.997607... - 7.21743962... + 2.219832528... - Gary W. Adamson, Jan 24 2010
G.f.: -1 + 1/(1 - Sum_{j>=1} floor(j/2)*x^j). - Joerg Arndt, Jul 06 2011
a(n+2) = A094790(n/2+1)*(1+(-1)^n)/2 + A094789((n+1)/2)*(1-(-1)^n)/2. - Paul Barry, Oct 30 2004
First differences of A028495. - Floor van Lamoen, Nov 02 2005
a(n) = A187065(2*n+1); a(n+1) = A187066(2*n+1) = A187067(2*n). - L. Edson Jeffery, Mar 16 2011
a(n) = 2^n*(c(1)^(n-1)*(c(1)+c(2)) + c(3)^(n-1)*(c(3)+c(6)) + c(5)^(n-1)*(c(5)+c(4)) )/7, with c(j):=cos(Pi*j/7). - Herbert Kociemba, Dec 18 2011
a(n+1)*(-1)^n*49^(1/3) = (c(1)/c(4))^(1/3)*(2*c(1))^n + (c(2)/c(1))^(1/3)*(2*c(2))^n + (c(4)/c(2))^(1/3)*(2c(4))^n = (c(2)/c(1))^(1/3)*(2*c(1))^(n+1) + (c(4)/c(2))^(1/3)*(c(2))^(n+1) + (c(1)/c(4))^(1/3)*(2*c(4))^(n+1), where c(j) := cos(2Pi*j/7); for the proof, see Witula et al.'s papers. - Roman Witula, Jul 21 2012
The previous formula connects the sequence a(n) with A214683, A215076, A215100, A120757. We may call a(n) the Ramanujan-type sequence number 2 for the argument 2*Pi/7. - Roman Witula, Aug 02 2012
a(n) = -A006054(1-n) for all n in Z. - Michael Somos, Nov 30 2014
G.f.: x^2 / (1 - x / (1 - 2*x / (1 + 5*x / (2 - x / (5 - 2*x))))). - Michael Somos, Jan 20 2017
a(n) ~ r*c^n, where r=0.241717... is one of the roots of 49*x^3-7*x+1, and c=2*cos(Pi/7) (as in Gary W. Adamson's formula). - Daniel Checa, Nov 04 2022
a(2n-1) = 2*a(n+1)*a(n) - a(n)^2 - a(n-1)^2. - Richard Peterson, May 25 2023

More terms from Emeric Deutsch, Dec 14 2004

Typo in definition fixed by Reinhard Zumkeller, Oct 14 2011

A160389 Decimal expansion of 2*cos(Pi/7).

Original entry on oeis.org

1, 8, 0, 1, 9, 3, 7, 7, 3, 5, 8, 0, 4, 8, 3, 8, 2, 5, 2, 4, 7, 2, 2, 0, 4, 6, 3, 9, 0, 1, 4, 8, 9, 0, 1, 0, 2, 3, 3, 1, 8, 3, 8, 3, 2, 4, 2, 6, 3, 7, 1, 4, 3, 0, 0, 1, 0, 7, 1, 2, 4, 8, 4, 6, 3, 9, 8, 8, 6, 4, 8, 4, 0, 8, 5, 5, 8, 7, 9, 9, 3, 1, 0, 0, 2, 7, 2, 2, 9, 0, 9, 4, 3, 7, 0, 2, 4, 8, 3, 0, 6, 3, 6, 6, 2

Offset: 1

Harry J. Smith, May 31 2009

Arises in the approximation of 14-fold quasipatterns by 14 Fourier modes.
Let DTS(n^c) denote the set of languages accepted by a deterministic Turing machine with space n^(o(1)) and time n^(c+o(1)), and let SAT denote the Boolean satisfiability problem. Then (1) SAT is not in DTS(n^c) for any c < 2*cos(Pi/7), and (2) the Williams inference rules cannot prove that SAT is not in DTS(n^c) for any c >= 2*cos(Pi/7). These results also apply to the Boolean satisfiability problem mod m where m is in A085971 except possibly for one prime. - Charles R Greathouse IV, Jul 19 2012
rho(7):= 2*cos(Pi/7) is the length ratio (smallest diagonal)/side in the regular 7-gon (heptagon). The algebraic number field Q(rho(7)) of degree 3 is fundamental for the 7-gon. See A187360 for the minimal polynomial C(7, x) of rho(7). The other (larger) diagonal/side ratio in the heptagon is sigma(7) = -1 + rho(7)^2, approx. 2.2469796. (see the decimal expansion in A231187). sigma(7) is the limit of a(n+1)/a(n) for n->infinity for the sequences like A006054 and A077998 which can be considered as analogs of the Fibonacci sequence in the pentagon. Thus sigma(7) plays in the heptagon the role of the golden section in the pentagon. See the P. Steinbach reference. - Wolfdieter Lang, Nov 21 2013
An algebraic integer of degree 3 with minimal polynomial x^3 - x^2 - 2x + 1. - Charles R Greathouse IV, Nov 12 2014
The other two solutions of the minimal polynomial of rho(7) = 2*cos(Pi/7) are 2*cos(3*Pi/7) and 2*cos(5*Pi/7). See eq. (20) of the W. Lang link. - Wolfdieter Lang, Feb 11 2015
The constant is the square root of 3.24697... (cf. A116425). It is the fifth-longest diagonal in the regular 14-gon with unit radius, which equals 2*sin(5*Pi/14). - Gary W. Adamson, Feb 14 2022

			1.801937735804838252472204639014890102331838324263714300107124846398864...

John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 207.

Harry J. Smith, Table of n, a(n) for n = 1..20000
Simon Baker, Exceptional digit frequencies and expansions in non-integer bases, arXiv:1711.10397 [math.DS], 2017. See Theorem 1.1 p. 3.
Sam Buss and Ryan Williams, Limits on alternation-trading proofs for time-space lower bounds, Electronic Colloquium on Computational Complexity 2011
Wolfdieter Lang, The field Q(2cos(pi/n)), its Galois group and length ratios in the regular n-gon, arXiv:1210.1018 [math.GR], Oct 03 2012.
Peter Steinbach, Golden Fields: A Case for the Heptagon, Mathematics Magazine, Vol. 70, No. 1, Feb. 1997.
Ryan Williams, Time-space tradeoffs for counting NP solutions modulo integers, Computational Complexity 17 (2008), pp. 179-219.
Index entries for algebraic numbers, degree 3

Cf. A039921 (continued fraction).
Cf. A047336, A047341, A116425, A255240, A255249.
Cf. A003558 (the constant is cyclic with period 3, for N = 7).

R:= RealField(200); Reverse(Intseq(Floor(10^110*2*Cos(Pi(R)/7)))); // Marius A. Burtea, Nov 13 2019

evalf(2*cos(Pi/7), 100); # Wesley Ivan Hurt, Feb 01 2017

RealDigits[2 Cos[Pi/7], 10, 111][[1]] (* Robert G. Wilson v, Jun 11 2013 *)

default(realprecision, 20080); x=2*cos(Pi/7); for (n=1, 20000, d=floor(x); x=(x-d)*10; write("b160389.txt", n, " ", d));

Equals 2*A073052. - Michel Marcus, Nov 21 2013
Equals (Re((-(4*7)*(1 + 3*sqrt(3)*i))^(1/3)) + 1)/3, with the real part Re, and i = sqrt(-1). - Wolfdieter Lang, Feb 24 2015
Equals i^(2/7) - i^(12/7). - Peter Luschny, Apr 04 2020
From Peter Bala, Oct 20 2021: (Start)
Equals 2 - (1 - z)*(1 - z^6)/((1 - z^3)*(1 - z^4)), where z = exp(2*Pi*i/7).
The other two zeros of the minimal polynomial x^3 - x^2 - 2*x + 1 of 2*cos(Pi/7) are given by 2 - (1 - z^3)*(1 - z^4)/((1 - z^2)*(1 - z^5)) = 2*cos(3*Pi/7) = A255241 and 2 - (1 - z^2)*(1 - z^5)/((1 - z)*(1 - z^6)) = cos(5*Pi/7) = -A362922.
Equals Product_{n >= 0} (7*n+2)*(7*n+5)/((7*n+1)*(7*n+6)) = 1 + Product_{n >= 0} (7*n+2)*(7*n+5)/((7*n+3)*(7*n+4)) = 1/A255240.
The linear fractional mapping r -> 1/(1 - r) cyclically permutes the three zeros of the minimal polynomial x^3 - x^2 - 2*x + 1. The inverse mapping is r -> (r - 1)/r.
The quadratic mapping r -> 2 - r^2 also cyclically permutes the three zeros. The inverse mapping is r -> r^2 - r - 1. (End)
Equals i^(2/7) + i^(-2/7). - Gary W. Adamson, Feb 11 2022
From Amiram Eldar, Nov 22 2024: (Start)
Equals Product_{k>=1} (1 - (-1)^k/A047336(k)).
Equals 1 + cosec(3*Pi/14)/2 = 1 + Product_{k>=1} (1 + (-1)^k/A047341(k)). (End)
Equals sqrt(A116425). - Hugo Pfoertner, Nov 22 2024

cp's OEIS Frontend

A005021 Random walks (binomial transform of A006054).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A180264 Triangle, row sums = A006054; derived from an infinite lower triangular matrix with (1,1,1,...) as the leftmost column and (1,2,1,1,1,...) as other columns.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A144159 Eigentriangle, sum of row n terms = A006054(n+2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A122500 Semiprimes in A006054.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Extensions

A284786 Pisano period of sequence A006054 modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A008619 Positive integers repeated.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Scala

Formula

Extensions

A007583 a(n) = (2^(2*n + 1) + 1)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP