A078008 -id:A078008 - cp's OEIS frontend

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

1, 0, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 10, 9, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 14, 13, 14, 15, 14, 15, 16, 15, 16, 17, 16, 17, 18, 17, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 22, 21, 22, 23, 22, 23, 24, 23, 24, 25, 24, 25, 26, 25, 26, 27, 26, 27, 28

Offset: 0

N. J. A. Sloane, Mar 15 1996

Molien series of 2-dimensional representation of cyclic group of order 3 over GF(2).
One step back, two steps forward.
The crossing number of the graph C(n, {1,3}), n >= 8, is [n/3] + n mod 3, which gives this sequence starting at the first 4. [Yang Yuansheng et al.]
A Chebyshev transform of A078008. The g.f. is the image of (1-x)/(1-x-2*x^2) (g.f. of A078008) under the Chebyshev transform A(x)-> (1/(1+x^2))*A(x/(1+x^2)). - Paul Barry, Oct 15 2004
A047878 is an essentially identical sequence. - Anton Chupin, Oct 24 2009
Rhyme scheme of Dante Alighieri's "Divine Comedy." - David Gaita, Feb 11 2011
A194960 results from deleting the first four terms of A008611. Note that deleting the first term or first four terms of A008611 leaves a concatenation of segments (n, n+1, n+2); for related concatenations, see
  A008619, (n,n+1) after deletion of first term;
  A053737, (n,n+1,n+2,n+3) beginning with n=0;
  A053824, (n to n+4) beginning with n=0. - Clark Kimberling, Sep 07 2011
It appears that a(n) is the number of roots of x^(n+1) + x + 1 inside the unit circle. - Michel Lagneau, Nov 02 2012
Also apparently for n >= 2: a(n) is the largest remainder r that results from dividing n+2 by 1..n+2 more than once, i.e., a(n) = max(i, A072528(n+2,i)>1). - Ralf Stephan, Oct 21 2013
Number of n-element subsets of [n+1] whose sum is a multiple of 3. a(4) = 1: {1,2,4,5}. - Alois P. Heinz, Feb 06 2017
It appears that a(n) is the number of roots of the Fibonacci polynomial F(n+2,x) strictly inside the unit circle of the complex plane. - Michel Lagneau, Apr 07 2017
For the proof of the preceding conjecture see my comments under A008615 and A049310. Chebyshev S(n,x) = i^n*F(n+1,-i*x), with i = sqrt(-1). - Wolfdieter Lang, May 06 2017
The sequence is the interleaving of three sequences: the positive integers (A000027), the nonnegative integers (A001477), and the positive integers, in that order. - Guenther Schrack, Nov 07 2020
a(n) is the number of multiples of 3 between n and 2n. - Christian Barrientos, Dec 20 2021
a(n) is the least number of football games a team has to play to be able to get n-1 points, where a win is 3 points, a draw is 1 point, and a loss is 0 points. - Sigurd Kittilsen, Dec 01 2022

			G.f. = 1 + x^2 + 2*x^3 + x^4 + 2*x^5 + 3*x^6 + 2*x^7 + 3*x^8 + 4*x^9 + ...

D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 103.

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Cristian Cobeli, Aaditya Raghavan, and Alexandru Zaharescu, On the central ball in a translation invariant involutive field, arXiv:2408.01864 [math.NT], 2024. See p. 7.
Frederik Glitzner and David Manlove, Perspectives on Unsolvability in Roommates Markets, arXiv:2505.06717 [cs.GT], 2025. See p. 13.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 447.
Gerard P. Michon, Counting Polyhedra.
Yang Yuansheng et al., The crossing number of C(n; {1,3}), Discr. Math. 289 (2004), 107-118.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).
Index entries for Molien series.

Cf. A000027, A001477, A008619, A047878, A049310, A049347, A053737, A053824, A058207, A058788, A072528, A078008, A194960, A257075, A330396.

a008611 n = n' + mod r 2 where (n', r) = divMod (n + 1) 3
a008611_list = f [1,0,1] where f xs = xs ++ f (map (+ 1) xs)
-- Reinhard Zumkeller, Nov 25 2013

[(n-1)-2*Floor((n-1)/3): n in [0..90]]; // Vincenzo Librandi, Aug 21 2011

with(numtheory): for n from 1 to 70 do:it:=0:
y:=[fsolve(x^n+x+1, x, complex)] : for m from 1 to nops(y) do : if abs(y[m])< 1 then it:=it+1:else fi:od: printf(`%d, `,it):od:
A008611:=n->(n-1)-2*floor((n-1)/3); seq(A008611(n), n=0..50); # Wesley Ivan Hurt, May 18 2014

With[{nn=30},Riffle[Riffle[Range[nn],Range[0,nn-1]],Range[nn],3]] (* or *) RecurrenceTable[{a[0]==a[2]==1,a[1]==0,a[n]==a[n-3]+1},a,{n,90}] (* Harvey P. Dale, Nov 06 2011 *)
LinearRecurrence[{1, 0, 1, -1}, {1, 0, 1, 2}, 100] (* Vladimir Joseph Stephan Orlovsky, Feb 23 2012 *)
a[ n_] := Quotient[n - 1, 3] + Mod[n + 2, 3]; (* Michael Somos, Jan 23 2014 *)

{a(n) = (n-1) \ 3 + (n+2) % 3}; /* Michael Somos, Jan 23 2014 */

a(n) = a(n-3) + 1.
a(n) = (n-1) - 2*floor((n-1)/3).
G.f.: (1 + x^2 + x^4)/(1 - x^3)^2.
After the initial term, has form {n, n+1, n+2} for n=0, 1, 2, ...
From Paul Barry, Mar 18 2004: (Start)
a(n) = Sum_{k=0..n} (-1)^floor(2*(k-2)/3);
a(n) = 4*sqrt(3)*cos(2*Pi*n/3 + Pi/6)/9 + (n+1)/3. (End)
From Paul Barry, Oct 15 2004: (Start)
G.f.: (1 - x + x^2)/((1 + x + x^2)*(x-1)^2);
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*A078008(n-2k)*(-1)^k. (End)
a(n) = -a(-2-n) for all n in Z.
Euler transform of length 6 sequence [0, 1, 2, 0, 0, -1]. - Michael Somos, Jan 23 2014
a(n) = ((n-1) mod 3) + floor((n-1)/3). - Wesley Ivan Hurt, May 18 2014
PSUM transform of A257075. - Michael Somos, Apr 15 2015
a(n) = A194960(n-3), n >= 0, with extended A194960. See the a(n) formula two lines above. - Wolfdieter Lang, May 06 2017
From Guenther Schrack, Nov 07 2020: (Start)
a(n) = (3*n + 3 + 2*(w^(2*n)*(1 - w) + w^n*(2 + w)))/9, where w = (-1 + sqrt(-3))/2, a primitive third root of unity;
a(n) = (n + 1 + 2*A049347(n))/3;
a(n) = (2*n - A330396(n-1))/3. (End)
E.g.f.: (3*exp(x)*(1 + x) + exp(-x/2)*(6*cos(sqrt(3)*x/2) - 2*sqrt(3)*sin(sqrt(3)*x/2)))/9. - Stefano Spezia, May 06 2022
Sum_{n>=2} (-1)^n/a(n) = 3*log(2) - 1. - Amiram Eldar, Sep 10 2023

A047849 a(n) = (4^n + 2)/3.

Original entry on oeis.org

1, 2, 6, 22, 86, 342, 1366, 5462, 21846, 87382, 349526, 1398102, 5592406, 22369622, 89478486, 357913942, 1431655766, 5726623062, 22906492246, 91625968982, 366503875926, 1466015503702, 5864062014806, 23456248059222, 93824992236886, 375299968947542

Offset: 0

Clark Kimberling

Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6. - Paul Barry, Mar 10 2004
The number of closed walks of odd length of the cyclic graph is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case. - Wolfdieter Lang, Nov 08 2011
A. A. Ivanov conjectures that the dimension of the universal embedding of the unitary dual polar space DSU(2n,4) is a(n). - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004
Permutations with two fixed points avoiding 123 and 132.
Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302. - Paul Curtz, Mar 25 2008
Also the number of permutations of length n which avoid 4321 and 4123 (or 4321 and 3412, or 4123 and 3214, or 4123 and 2143). - Vincent Vatter, Aug 17 2009; minor correction by Henning Ulfarsson, May 14 2017
This sequence is related to A014916 by A014916(n) = n*a(n)-Sum_{i=0..n-1} a(i). - Bruno Berselli, Jul 27 2010, Mar 02 2012
For n >= 2, a(n) equals 2^n times the permanent of the (2n-2) X (2n-2) tridiagonal matrix with 1/sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
For n > 0, counts closed walks of length (n) at a vertex of a triangle with two (x2) loops at each vertex. - David Neil McGrath, Sep 11 2014
From Michel Lagneau, Feb 26 2015: (Start)
a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.
Proof:
All integers of the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} are of the form 2^k(2m+1) where k and m integers. The greatest odd divisor of a such integer is 2m+1. Reciprocally, if 2m+1 is an odd integer <= 2^n, there exists a unique integer in the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} where 2m+1 is the greatest odd divisor. Hence the recurrence relation:
   a(n) = a(n+1) + (1 + 3 + ... + 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) for n >= 2.
We obtain immediately: a(n) = a(1) + 4 + ... + 4^n = (4^n+2)/3. (End)
The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - Peter Bala, Aug 12 2021
Let q = 2^(2n+1) and Omega_n be the Suzuki ovoid with q^2 + 1 points. Then a(n) is the number of orbits of the finite Suzuki group Sz(q) on 3-subsets of Omega_n. Link to result in References. - Paul M. Bradley, Jun 04 2023
Also the cogrowth sequence for the 8-element dihedral group D8 = . - Sean A. Irvine, Nov 04 2024

			a(2) = 6 for the number of round trips in C_6 from the six round trips from, say, vertex no. 1: 12121, 16161, 12161, 16121, 12321 and 16561. - _Wolfdieter Lang_, Nov 08 2011

Bruno Berselli, Table of n, a(n) for n = 0..1000
Jeffrey M. Barnes, Georgia Benkart, and Tom Halverson, McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 37-51.
Pascal Caron, Jean-Gabriel Luque, and Bruno Patrou, A combinatorial approach for the state complexity of the Shuffle product, arXiv:1905.08120 [cs.FL], 2019.
Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, and Seyed Ahmad Mojallal, Riordan graphs I: structural properties, Linear Algebra and its Applications, 579. pp. 89-135, Prop. 2.8. (2019).
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 37-48. See Conjecture 5.5.
Kittitat Iamthong, Ji-Hwan Jung, and Sergey Kitaev, Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations, arXiv:2009.01410 [math.CO], 2020.
D. Kremer and W. C. Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Mathematics 268 (2003), 171-183.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.
Wikipedia, Permutation classes avoiding two patterns of length 4.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A000302, A001045, A002450, A007583, A024493, A047848, A078008, A121314, A131708, A178789, A199571.

Cf. A014916, A073724, A020988, A039301.

[(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015

(4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* Harvey P. Dale, Nov 27 2015 *)

PARI
```
a(n)=(4^n+2)/3;
```

def A047849(n): return (pow(4, n) +2)//3
print([A047849(n) for n in range(41)]) # G. C. Greubel, Jan 17 2025

def A047849(n): return ((1 << (2 * n)) + 2) // 3 # John Reimer Morales, Aug 05 2025

n-th difference of a(n), a(n-1), ..., a(0) is 3^(n-1) for n >= 1.
From Henry Bottomley, Aug 29 2000: (Start)
a(n) = (4^n + 2)/3.
a(n) = 4*a(n-1) - 2.
a(n) = 5*a(n-1) - 4*a(n-2).
a(n) = 2*A007583(n-1) = A002450(n) + 1. (End)
a(n) = A047848(1,n).
With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - Paul Barry, Aug 26 2003
a(n) = A007583(n) - A002450(n) = A001045(2n+1) - A001045(2n) . - Philippe Deléham, Feb 25 2004
Second binomial transform of A078008. Binomial transform of 1, 1, 3, 9, 81, ... (3^n/3 + 2*0^n/3). a(n) = A078008(2n). - Paul Barry, Mar 14 2004
G.f.: (1-3*x)/((1-x)*(1-4*x)). - Herbert Kociemba, Jun 06 2004
a(n) = Sum_{k=0..n} 2^k*A121314(n,k). - Philippe Deléham, Sep 15 2006
a(n) = (A001045(2*n+1) + 1)/2. - Paul Barry, Dec 05 2007
From Bruno Berselli, Jul 27 2010: (Start)
a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2.
Sum_{i=0..n} a(i) = A073724(n). (End)
For n >= 3, a(n) equals [2, 1, 1; 1, 2, 1; 1, 1, 2]^(n - 2)*{1, 1, 2}*{1, 1, 2}. - John M. Campbell, Jul 09 2011
a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - Oboifeng Dira, May 29 2020
From Elmo R. Oliveira, Dec 21 2023: (Start)
E.g.f.: (exp(x)*(exp(3*x) + 2))/3.
a(n) = A178789(n+1)/3. (End)
a(n) = A000302(n) - A020988(n). - John Reimer Morales, Aug 03 2025

New name from Charles R Greathouse IV, Dec 22 2011

A060747 a(n) = 2*n - 1.

Original entry on oeis.org

-1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151

Offset: 0

Henry Bottomley, Apr 26 2001

If you put n red balls and n blue balls in a bag and draw them one by one without replacement, the probability of never having drawn equal numbers of the two colors before the final ball is drawn is 1/a(n) unsigned.
abs(a(n)) = 2n - 1 + 2*0^n. It has A048495 as binomial transform. - Paul Barry, Jun 09 2003
For n >= 1, a(n) = numbers k such that arithmetic mean of the first k positive integers is an integer. A040001(a(n)) = 1. See A145051 and A040001. -  Jaroslav Krizek, May 28 2010
From Jaroslav Krizek, May 28 2010: (Start)
For n >= 1, a(n) = corresponding values of antiharmonic means to numbers from A016777 (numbers k such that antiharmonic mean of the first k positive integers is an integer).
a(n) = A000330(A016777(n)) / A000217(A016777(n)) = A146535(A016777(n)+1). (End)

Tanya Khovanova, Recursive Sequences
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A000217, A000330, A000984, A001477, A002420, A005408, A005843, A016777, A023443, A040001, A048495, A078008, A145051, A146535, A161680.

a060747 = subtract 1 . (* 2)
a060747_list = [-1, 1 ..] -- Reinhard Zumkeller, Jul 05 2015
-- Reinhard Zumkeller, Jul 05 2015

Table[2*n - 1, {n, 0, 200}] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)
LinearRecurrence[{2,-1},{-1,1},80] (* Harvey P. Dale, Mar 27 2020 *)

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

a(n) = A005408(n)-2 = A005843(n)-1 = -A000984(n)/A002420(n) = A001477(n)+A023443(n).
G.f.: (3*x - 1)/(1 - x)^2.
Abs(a(n)) = Sum_{k=0..n} (A078008(k) mod 4). - Paul Barry, Mar 12 2004
E.g.f.: exp(x)*(2*x-1). - Paul Barry, Mar 31 2007
a(n) = 2*a(n-1) - a(n-2); a(0)=-1, a(1)=1. - Philippe Deléham, Nov 03 2008
a(n) = 4*n - a(n-1) - 4 for n>0, with a(0)=-1. - Vincenzo Librandi, Aug 07 2010
a(n) = A161680(A005843(n))/n for n > 0. - Stefano Spezia, Feb 14 2025

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

Original entry on oeis.org

1, 0, 1, 2, 6, 10, 26, 42, 106, 170, 426, 682, 1706, 2730, 6826, 10922, 27306, 43690, 109226, 174762, 436906, 699050, 1747626, 2796202, 6990506, 11184810, 27962026, 44739242, 111848106, 178956970, 447392426, 715827882, 1789569706, 2863311530, 7158278826

Offset: 0

Emeric Deutsch, May 16 2001

Or, number of permutations with no fixed points avoiding 213 and 132.
Number of derangements of {1,2,...,n} having ascending runs consisting of consecutive integers. Example: a(4)=6 because we have 234/1, 34/12, 34/2/1, 4/123, 4/3/12, 4/3/2/1, the ascending runs being as indicated. - Emeric Deutsch, Dec 08 2004
Let c be twice the sequence A002450 interlaced with itself (from the second term), i.e., c = 2*(0, 1, 1, 5, 5, 21, 21, 85, 85, 341, 341, ...). Let d be powers of 4 interlaced with the zero sequence: d = (1, 0, 4, 0, 16, 0, 64, 0, 256, 0, ...). Then a(n+1) = c(n) + d(n). - Creighton Dement, May 09 2005
Inverse binomial transform of A094705 (0, 1, 4, 15). - Paul Curtz, Jun 15 2008
Equals row sums of triangle A177993. - Gary W. Adamson, May 16 2010
a(n-1) is also the number of order preserving partial isometries (of an n-chain) of fix 1 (fix of alpha equals the number of fixed points of alpha). - Abdullahi Umar, Dec 28 2010
a(n+1) <= A218553(n) is also the Moore lower bound on the order of a (5,n)-cage. - Jason Kimberley, Oct 31 2011
For n > 0, a(n) is the location of the n-th new number to make a first appearance in A087230. E.g., the 17th number to make its first appearance in A087230 is 18 and this occurs at A087230(43690) and a(17)=43690. - K D Pegrume, Jan 26 2022
Position in A002487 of 2 adjacent terms of A000045. E.g., 3/5 at 10, 5/8 at 26, 8/13 at 42, ... - Ed Pegg Jr, Dec 27 2022

			a(4)=6 because the only 132 and 213-avoiding permutations of {1,2,3,4} without fixed points are: 2341, 3412, 3421, 4123, 4312 and 4321.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
F. Al-Kharousi, R. Kehinde and A. Umar, Combinatorial results for certain semigroups of partial isometries of a finite chain, The Australasian Journal of Combinatorics, Volume 58 (3) (2014), 363-375.
J. Brillhart and P. Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869 (contains the sequence of the odd-subscripted terms and that of the even-subscripted terms).
Emeric Deutsch, Derangements That Don't Rise Too Fast: 10902, Amer. Math. Monthly, Vol. 110, No. 7 (2003), pp. 639-640.
K. Dilcher and K. B. Stolarsky, Stern polynomials and double-limit continued fractions, Acta Arithmetica 140 (2009), 119-134
R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049 [math.GR], 2010.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002
Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Cf. A000166, A020988, A020989, A068018.
Cf. A177993. - Gary W. Adamson, May 16 2010
Cf. A183158, A183159. - Abdullahi Umar, Dec 28 2010
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), this sequence (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 31 2011

[(3/8)*2^n +(1/24)*(-2)^n - 2/3: n in [1..35]]; // Vincenzo Librandi, Aug 13 2011

A061547:=n->ceil(abs((3/8)*2^n +(1/24)*(-2)^n - 2/3)); seq(A061547(n), n=1..30); # Wesley Ivan Hurt, Apr 03 2014

f[n_] := (9*2^(n-3) - (-2)^(n-3) - 2)/3; Array[f, 32] (* Robert G. Wilson v, Aug 13 2011 *)

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

a(n) = (3/8)*2^n + (1/24)*(-2)^n - 2/3 for n>=1.
a(n) = 4*a(n-2) + 2, a(0)=1, a(1)=0, a(2)=1.
G.f: (5*z^3-3*z^2-z+1)/((z-1)*(4*z^2-1)).
a(n) = A020989((n-2)/2) for n=2, 4, 6, ... and A020988((n-3)/2) for n=3, 5, 7, ... .
a(n+1)-2*a(n) = A078008 signed. Differences: doubled A000302. - Paul Curtz, Jun 15 2008
a(2i+1) = 2*Sum_{j=0..i-1} 4^j = string "2"^i read in base 4.
a(2i+2) = 4^i + 2*Sum_{j=0..i-1} 4^j = string "1"*"2"^i read in base 4.
a(n+2) = Sum_{k=0..n} A144464(n,k)^2 = Sum_{k=0..n} A152716(n,k). - Philippe Deléham and Michel Marcus, Feb 26 2014
a(2*n-1) = A176965(2*n), a(2*n) = A176965(2*n-1) for n>0. - Yosu Yurramendi, Dec 23 2016
a(2*n-1) = A020988(k-1), a(2*n)= A020989(n-1) for n>0. - Yosu Yurramendi, Jan 03 2017
a(n+2) = 2*A086893(n), n > 0. - Yosu Yurramendi, Mar 07 2017
E.g.f.: (15 - 8*cosh(x) + 5*cosh(2*x) - 8*sinh(x) + 4*sinh(2*x))/12. - Stefano Spezia, Apr 07 2022

a(0)=1 prepended by Alois P. Heinz, Jan 27 2022

A015531 Linear 2nd order recurrence: a(n) = 4a(n-1) + 5a(n-2).

Original entry on oeis.org

0, 1, 4, 21, 104, 521, 2604, 13021, 65104, 325521, 1627604, 8138021, 40690104, 203450521, 1017252604, 5086263021, 25431315104, 127156575521, 635782877604, 3178914388021, 15894571940104, 79472859700521, 397364298502604, 1986821492513021, 9934107462565104

Offset: 0

Olivier Gérard

Number of walks of length n between any two distinct vertices of the complete graph K_6. Example: a(2)=4 because the walks of length 2 between the vertices A and B of the complete graph ABCDEF are: ACB, ADB, AEB and AFB. - Emeric Deutsch, Apr 01 2004
General form: k=5^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-4, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=charpoly(A,1). - Milan Janjic, Jan 27 2010
Pisano period lengths: 1, 2, 6, 2, 2, 6, 6, 4, 18, 2, 10, 6, 4, 6, 6, 8, 16, 18, 18, 2,... - R. J. Mathar, Aug 10 2012
The ratio a(n+1)/a(n) converges to 5 as n approaches infinity. - Felix P. Muga II, Mar 09 2014
For odd n, a(n) is congruent to 1 (mod 10). For even n > 0, a(n) is congruent to 4 (mod 10). - Iain Fox, Dec 30 2017

Iain Fox, Table of n, a(n) for n = 0..1431 (terms 0..1000 from Vincenzo Librandi)
Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014.
Index entries for linear recurrences with constant coefficients, signature (4,5).

A083425 shifted right.

Cf. A033115 (partial sums), A213128.

[Round(5^n/6): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

seq(round(5^n/6), n=0..25); # Mircea Merca, Dec 28 2010

LinearRecurrence[{4,5},{0,1},30] (* Harvey P. Dale, Jul 09 2017 *)

a(n)=5^n\/6 ; \\ Charles R Greathouse IV, Apr 14 2014

first(n) = Vec(x/((1 - 5*x)*(1 + x)) + O(x^n), -n) \\ Iain Fox, Dec 30 2017

[lucas_number1(n,4,-5) for n in range(0, 22)] # Zerinvary Lajos, Apr 23 2009

From Paul Barry, Apr 20 2003: (Start)
a(n) = (5^n -(-1)^n)/6.
G.f.: x/((1-5*x)*(1+x)).
E.g.f.(exp(5*x)-exp(-x))/6. (End) (corrected by M. F. Hasler, Jan 29 2012)
a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*6^(k-1). - Paul Barry, May 13 2003
a(n) = 5^(n-1) - a(n-1). - Emeric Deutsch, Apr 01 2004
a(n) = ((2+sqrt(9))^n - (2-sqrt(9))^n)/6. - Al Hakanson (hawkuu(AT)gmail.com), Jan 07 2009
a(n) = round(5^n/6). - Mircea Merca, Dec 28 2010
The logarithmic generating function 1/6*log((1+x)/(1-5*x)) = x + 4*x^2/2 + 21*x^3/3 + 104*x^4/4 + ... has compositional inverse 6/(5+exp(-6*x)) - 1, the e.g.f. for a signed version of A213128. - Peter Bala, Jun 24 2012
a(n) = (-1)^(n-1)*Sum_{k=0..(n-1)} A135278(n-1,k)*(-6)^k = (5^n - (-1)^n)/6 = (-1)^(n-1)*Sum_{k=0..(n-1)} (-5)^k. Equals (-1)^(n-1)*Phi(n,-5) when n is an odd prime, where Phi is the cyclotomic polynomial. - Tom Copeland, Apr 14 2014

A059570 Number of fixed points in all 231-avoiding involutions in S_n.

Original entry on oeis.org

1, 2, 6, 14, 34, 78, 178, 398, 882, 1934, 4210, 9102, 19570, 41870, 89202, 189326, 400498, 844686, 1776754, 3728270, 7806066, 16311182, 34020466, 70837134, 147266674, 305718158, 633805938, 1312351118, 2714180722, 5607318414, 11572550770, 23860929422

Offset: 1

Emeric Deutsch, Feb 16 2001

Number of odd parts in all compositions (ordered partitions) of n: a(3)=6 because in 3=2+1=1+2=1+1+1 we have 6 odd parts. Number of even parts in all compositions (ordered partitions) of n+1: a(3)=6 because in 4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1 we have 6 even parts.
Convolved with (1, 2, 2, 2, ...) = A001787: (1, 4, 12, 32, 80, ...). - Gary W. Adamson, May 23 2009
An elephant sequence, see A175654. For the corner squares 36 A[5] vectors, with decimal values between 15 and 480, lead to this sequence. For the central square these vectors lead to the companion sequence 4*A172481, for n>=-1. - Johannes W. Meijer, Aug 15 2010
a(n) is the total number of runs of equal parts in the compositions of n. a(5) = 34 because there are 34 runs of equal parts in the compositions of 5, with parentheses enclosing each run: (5), (4)(1), (1)(4), (3)(2), (2)(3), (3)(1,1), (1)(3)(1), (1,1)(3), (2,2)(1), (2)(1)(2), (1)(2,2), (2)(1,1,1), (1)(2)(1,1), (1,1)(2)(1), (1,1,1)(2), (1,1,1,1,1). - Gregory L. Simay, Apr 28 2017
a(n) - a(n-2) is the number of 1's in all compositions of n and more generally, the number of k's in all compositions of n+k-1. - Gregory L. Simay, May 01 2017

			a(3) = 6 because in the 231-avoiding involutions of {1,2,3}, i.e., in 123, 132, 213, 321, we have altogether 6 fixed points (3+1+1+1).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
S. Heubach and T. Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
Brian Hopkins, Andrew V. Sills, Thotsaporn "Aek" Thanatipanonda, and Hua Wang, Parts and subword patterns in compositions, Preprint 2015.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 30.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Cf. A001787, A027934, A045623, A127984, A128255, A172481, A225084.

[(3*n+4)*2^n/18-2*(-1)^n/9: n in [1..40]]; // Vincenzo Librandi, May 01 2017

LinearRecurrence[{3,0,-4},{1,2,6},30] (* Harvey P. Dale, Dec 29 2013 *)
Table[(3 n + 4) 2^n/18 - 2 (-1)^n/9, {n, 30}] (* Vincenzo Librandi, May 01 2017 *)

a(n) = (3*n+4)*2^n/18 - 2*(-1)^n/9.
G.f.: z*(1-z)/((1+z)*(1-2*z)^2).
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(n-k, k+j)*2^k. - Paul Barry, Aug 29 2004
a(n) = Sum_{k=0..n+1} (-1)^(k+1)*binomial(n+1, k+j)*A001045(k). - Paul Barry, Jan 30 2005
Convolution of "Expansion of (1-x)/(1-x-2*x^2)" (A078008) with "Powers of 2" (A000079), treating the result as if offset=1. - Graeme McRae, Jul 12 2006
Convolution of "Difference sequence of A045623" (A045891) with "Positive integers repeated" (A008619), treating the result as if offset=1. - Graeme McRae, Jul 12 2006
a(n) = 3*a(n-1)-4*a(n-3); a(1)=1,a(2)=2,a(3)=6. - Philippe Deléham, Aug 30 2006
Equals row sums of A128255. (1, 2, 6, 14, 34, ...) - (0, 0, 1, 2, 6, 14, 34, ...) = A045623: (1, 2, 5, 12, 28, 64, ...). - Gary W. Adamson, Feb 20 2007
Equals triangle A059260 * [1, 2, 3, ...] as a vector. - Gary W. Adamson, Mar 06 2012
a(n) + a(n-1) = A001792(n-1). - Gregory L. Simay, Apr 30 2017
a(n) - a(n-2) = A045623(n-1). - Gregory L. Simay, May 01 2017
a(n) = A045623(n-1) + A045623(n-3) + A045623(n-5) + ... - Gregory L. Simay, Feb 19 2018
a(n) = A225084(2n,n). - Alois P. Heinz, Aug 30 2018

More terms from Eugene McDonnell (eemcd(AT)mac.com), Jan 13 2005

A072547 Main diagonal of the array in which first column and row are filled alternatively with 1's or 0's and then T(i,j) = T(i-1,j) + T(i,j-1).

Original entry on oeis.org

1, 0, 2, 6, 22, 80, 296, 1106, 4166, 15792, 60172, 230252, 884236, 3406104, 13154948, 50922986, 197519942, 767502944, 2987013068, 11641557716, 45429853652, 177490745984, 694175171648, 2717578296116, 10648297329692, 41757352712480

Offset: 1

Benoit Cloitre, Aug 05 2002

nonn

A Catalan transform of A078008 under the mapping g(x)->g(xc(x)). - Paul Barry, Nov 13 2004
Number of positive terms in expansion of (x_1 + x_2 + ... + x_{n-1} - x_n)^n. - Sergio Falcon, Feb 08 2007
Hankel transform is A088138(n+1). - Paul Barry, Feb 17 2009
Without the beginning "1", we obtain the first diagonal over the principal diagonal of the array notified by B. Cloitre in A026641 and used by R. Choulet in A172025, and from A172061 to A172066. - Richard Choulet, Jan 25 2010
Also central terms of triangles A108561 and A112465. - Reinhard Zumkeller, Jan 03 2014
With offset 0 and for p prime, the p-th term is divisible by p. - F. Chapoton, Dec 03 2021

			The array begins:
  1 0 1 0 1..
  0 0 1 1 2..
  1 1 2 3 5..
  0 1 3 6 11..
so sequence begins : 1, 0, 2, 6, ...

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
David Anderson, E. S. Egge, M. Riehl, L. Ryan, R. Steinke, and Y. Vaughan, Pattern Avoiding Linear Extensions of Rectangular Posets, arXiv:1605.06825 [math.CO], 2016.
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015. [It is only a conjecture that this is the same sequence. It would be nice to have a proof.]
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, J. Integer Sequ., Vol. 8 (2005), Article 05.4.5.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)

Cf. A014300, A014301, A026641, A092785, A000957.

Cf. A026641, A172025, A172061, A172062, A172063, A172064, A172065, A172066. - Richard Choulet, Jan 25 2010

a072547 n = a108561 (2 * (n - 1)) (n - 1)
-- Reinhard Zumkeller, Jan 03 2014

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( x*(1 + Sqrt(1-4*x))/(Sqrt(1-4*x)*(3-Sqrt(1-4*x))) )); // G. C. Greubel, Feb 17 2019

taylor( (2/(3*sqrt(1-4*z)-1+4*z))*((1-sqrt(1-4*z))/(2*z))^(-1),z=0,42); for n from -1 to 40 do a(n):=sum('(-1)^(p)*binomial(2n-p+1,1+n-p)',p=0..n+1): od:seq(a(n),n=-1..40):od; # Richard Choulet, Jan 25 2010

CoefficientList[Series[(2/(3*Sqrt[1-4*x]-1+4*x))*((1-Sqrt[1-4*x]) /(2*x))^(-1), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 13 2014 *)
a[n_] := Binomial[2 n - 2, n] Hypergeometric2F1[1, 2 - n, n + 1, 1/2] / 2 + (-2)^(1 - n); Table[a[n], {n, 1, 26}] (* Peter Luschny, Dec 03 2021 *)

a(n) = (-1)^n*sum(k=0, n, binomial(-n, k));
vector(100, n, a(n-1)) \\ Altug Alkan, Oct 02 2015

a=(x*(1+sqrt(1-4*x))/(sqrt(1-4*x)*(3-sqrt(1-4*x)))).series(x, 30).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Feb 17 2019

If offset is 0, a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - Vladeta Jovovic, Feb 18 2003
G.f.: x*(1-x*C)/(1-2*x*C)/(1+x*C), where C = (1-sqrt(1-4*x))/(2*x) is g.f. for Catalan numbers (A000108). - Vladeta Jovovic, Feb 18 2003
a(n) = Sum_{j=0..floor((n-1)/2)} binomial(2*n-2*j-4, n-3). - Emeric Deutsch, Jan 28 2004
a(n) = A108561(2*(n-1),n-1). - Reinhard Zumkeller, Jun 10 2005
a(n) = (-1)^n*Sum_{k=0..n} binomial(-n,k) (offset 0). - Paul Barry, Feb 17 2009
Other form of the G.f: f(z) = (2/(3*sqrt(1-4*z) -1 +4*z))*((1 -sqrt(1-4*z))/(2*z))^(-1). - Richard Choulet, Jan 25 2010
D-finite with recurrence 2*(-n+1)*a(n) + (9*n-17)*a(n-1) + (-3*n+19)*a(n-2) + 2*(-2*n+7)*a(n-3) = 0. - R. J. Mathar, Nov 30 2012
From Peter Bala, Oct 01 2015: (Start)
a(n) = [x^n] ((1 - x)^2/(1 - 2*x))^n.
Exp( Sum_{n >= 1} a(n+1)*x^n/n ) = 1 + x^2 + 2*x^3 + 6*x^4 + 18*x^5 + ... is the o.g.f for A000957. (End)
a(n) = binomial(2*n-2, n)*hypergeom([1, 2-n], [n+1], 1/2) / 2 + (-2)^(1-n). - Peter Luschny, Dec 03 2021
a(n) = 2 * A014301(n-1) for n>=3. - Alois P. Heinz, Dec 27 2023

Corrected and extended by Vladeta Jovovic, Feb 17 2003

A015565 a(n) = 7a(n-1) + 8a(n-2), a(0) = 0, a(1) = 1.

Original entry on oeis.org

0, 1, 7, 57, 455, 3641, 29127, 233017, 1864135, 14913081, 119304647, 954437177, 7635497415, 61083979321, 488671834567, 3909374676537, 31274997412295, 250199979298361, 2001599834386887, 16012798675095097, 128102389400760775, 1024819115206086201, 8198552921648689607

Offset: 0

Olivier Gérard

A linear 2nd order recurrence. A Jacobsthal number sequence.
Binomial transform of A053573 (preceded by zero). - Paul Barry, Apr 09 2003
Second binomial transform of A080424. Binomial transform of A053573, with leading zero. Binomial transform is 0,1,9,81,729,....(9^n - 0^n)/9. Second binomial transform is 0,1,11,111,1111,... (A002275: repunits). - Paul Barry, Mar 14 2004
Number of walks of length n between any two distinct nodes of the complete graph K_9. Example: a(2)=7 because the walks of length 2 between the nodes A and B of the complete graph ABCDEFGHI are: ACB, ADB, AEB, AFB, AGB, AHB and AIB. - Emeric Deutsch, Apr 01 2004
Unsigned version of A014990. - Philippe Deléham, Feb 13 2007
General form: k=8^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499, A015531, A109500, A109501, A015552. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
The ratio a(n+1)/a(n) converges to 8 as n approaches infinity. - Felix P. Muga II, Mar 09 2014

			G.f. = x + 7*x^2 + 57*x^3 + 455*x^4 + 3641*x^5 + 29127*x^6 + 233017*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
Dale Gerdemann, Fractal generated from (7,8) recursion, YouTube Video, Dec 5, 2014.
Index entries for linear recurrences with constant coefficients, signature (7,8).

Cf. A002275, A014990, A053573, A080424, A082311, A082365.
Cf. A062160, A099322, A106566.
Cf. A001045, A078008, A097073, A115341, A015518, A054878, A015521, A109499, A015531, A109500, A109501, A015552. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

[Round(8^n/9): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

seq(round(8^n/9),n=0..25); # Mircea Merca, Dec 28 2010

k=0;lst={k};Do[k=8^n-k;AppendTo[lst, k], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008 *)
LinearRecurrence[{7,8},{0,1},30] (* Harvey P. Dale, Mar 04 2016 *)

x='x+O('x^30); concat([0], Vec(x/(1-7*x-8*x^2))) \\ G. C. Greubel, Dec 30 2017

[lucas_number1(n,7,-8) for n in range(0, 21)] # Zerinvary Lajos, Apr 24 2009

From Paul Barry, Apr 09 2003: (Start)
a(n) = (8^n - (-1)^n)/9.
a(n) = J(3*n)/3 = A001045(3*n)/3. (End)
From Emeric Deutsch, Apr 01 2004: (Start)
a(n) = 8^(n-1) - a(n-1).
G.f.: x/(1-7*x-8*x^2). (End)
a(n) = Sum_{k = 0..n} A106566(n,k)*A099322(k). - Philippe Deléham, Oct 30 2008
a(n) = round(8^n/9). - Mircea Merca, Dec 28 2010
From Peter Bala, May 31 2024: (Start)
G.f: A(x) = x/(1 - x^2) o x/(1 - x^2), where o denotes the black diamond product of power series as defined by Dukes and White. Cf. A054878.
The black diamond product A(x) o A(x) is the g.f. for the number of walks of length n between any two distinct nodes of the complete graph K_81.
Row 8 of A062160. (End)
E.g.f.: exp(-x)*(exp(9*x) - 1)/9. - Elmo R. Oliveira, Aug 17 2024

A097073 Expansion of (1-x+2x^2)/((1+x)(1-2*x)).

Original entry on oeis.org

1, 0, 4, 4, 12, 20, 44, 84, 172, 340, 684, 1364, 2732, 5460, 10924, 21844, 43692, 87380, 174764, 349524, 699052, 1398100, 2796204, 5592404, 11184812, 22369620, 44739244, 89478484, 178956972, 357913940, 715827884, 1431655764, 2863311532

Offset: 0

Paul Barry, Jul 22 2004

Partial sums are A097074.

Pairwise sums are {1, 1, 4, 16, 32, ...} or 2^n -Sum_{k=0..n} binomial(n,k)*(-1)^(n+k)*k.

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

Cf. A046055, A097074.

Cf. A001045, A078008 (form a(n)=2^n-a(n-1)).

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

k=0;lst={1, k};Do[k=2^n-k;AppendTo[lst, k], {n, 2, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008 *)
CoefficientList[Series[(1-x+2x^2)/((1+x)(1-2x)),{x,0,40}],x] (* Harvey P. Dale, Dec 10 2012 *)

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

def A097073(n): return ((1<Chai Wah Wu, Apr 18 2025

def A097073(n): return 1 if (n==0) else 2*(2^n +2*(-1)^n)/3
[A097073(n) for n in (0..40)] # G. C. Greubel, Aug 19 2022

a(n) = (2*2^n + 4*(-1)^n)/3 - 0^n.
a(n) = A001045(n+1) + (-1)^n - 0^n.
a(n) = 2*A078008(n) - 0^n.
a(2*n+1) + a(2*n+2) = A000302(n+1). - Paul Curtz, Jun 30 2008
G.f.: 1 - x + x*Q(0), where Q(k) = 1 + 2*x^2 + (4*k+5)*x - x*(4*k+1 + 2*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013
E.g.f.: (1/3)*( 2*exp(2*x) + 4*exp(-x) - 3 ). - G. C. Greubel, Aug 19 2022

Obscure variable k in Orlovsky comment replaced with a(n) by R. J. Mathar, Apr 23 2009

A026465 Length of n-th run of identical symbols in the Thue-Morse sequence A010060 (or A001285).

Original entry on oeis.org

1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1

Offset: 1

Clark Kimberling

It appears that the sequence can be calculated by any of the following methods:
(1) Start with 1 and repeatedly replace 1 with 1, 2, 1 and 2 with 1, 2, 2, 2, 1;
(2) a(1) = 1, all terms are either 1 or 2 and, for n > 0, a(n) = 1 if the length of the n-th run of 2's is 1; a(n) = 2 if the length of the n-th run of consecutive 2's is 3, with each run of 2's separated by a run of two 1's;
(3) replace each 3 in A080426 with 2. - John W. Layman, Feb 18 2003
Number of representations of n as a sum of Jacobsthal numbers (1 is allowed twice as a part). Partial sums are A003159. With interpolated zeros, g.f. is (Product_{k>=1} (1 + x^A078008(k)))/2. - Paul Barry, Dec 09 2004
In other words, the consecutive 0's or 1's in A010060 or A010059. - Robin D. Saunders (saunders_robin_d(AT)hotmail.com), Sep 06 2006
From Carlo Carminati, Feb 25 2011: (Start)
The sequence (starting with the second term) can also be calculated by the following method:
Apply repeatedly to the string S_0 = [2] the following algorithm: take a string S, double it, if the last figure is 1, just add the last figure to the previous one, if the last figure is greater than one, decrease it by one unit and concatenate a figure 1 at the end. (This algorithm is connected with the interpretation of the sequence as a continued fraction expansion.) (End)
This sequence, starting with the second term, happens to be the continued fraction expansion of the biggest cluster point of the set {x in [0,1]: F^k(x) >= x, for all k in N}, where F denotes the Farey map (see A187061). - Carlo Carminati, Feb 28 2011
Starting with the second term, the fixed point of the substitution 2 -> 211, 1 -> 2. - Carlo Carminati, Mar 03 2011
It appears that this sequence contains infinitely many distinct palindromic subsequences. - Alexander R. Povolotsky, Oct 30 2016
From Michel Dekking, Feb 13 2019: (Start)
Let tau defined by tau(0) = 01, tau(1) = 10 be the Thue-Morse morphism, with fixed point A010060. Consecutive runs in A010060 are 0, 11, 0, 1, 00, 1, 1, ..., which are coded by their lengths 1, 2, 1, 1, 2, ... Under tau^2 consecutive runs are mapped to consecutive runs:
      tau^2(0) = 0110, tau^2(1) = 1001,
      tau^2(00) = 01100110, tau^2(11) = 10011001.
The reason is that (by definition of a run!) runs of 0's and runs of 1's alternate in the sequence of runs, and this is inherited by the image of these runs under tau^2.
Under tau^2 the runs of length 1 are mapped to the sequence 1,2,1 of run lengths, and the runs of length 2 are mapped to the sequence 1,2,2,2,1 of run lengths. This proves John Layman's conjecture number (1): it follows that (a(n)) is fixed point of the morphism alpha
      alpha: 1 -> 121, 2 -> 12221.
Since alpha(1) and alpha(2) are both palindromes, this also proves Alexander Povolotsky's conjecture.
(End)

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
G. Allouche, Jean-Paul Allouche and Jeffrey Shallit, Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde, Ann. Inst. Fourier (Grenoble), Vol. 56, No. 7 (2006), pp. 2115-2130.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See pp. 1-3, 7.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
Jean-Paul Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., Vol. 139, No. 1-3 (1995), pp. 455-461.
Claudio Bonanno, Carlo Carminati, Stefano Isola and Giulio Tiozzo, Dynamics of continued fractions and kneading sequences of unimodal maps, arXiv:1012.2131 [math.DS], 2010-2012.
Srećko Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math., Vol. 24, No. 1-3 (1989), pp. 83-96.
Julien Cassaigne, Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comput. Sci., Vol. 218, No. 1 (1999), pp. 3-12.
Artūras Dubickas, On the distance from a rational power to the nearest integer, Journal of Number Theory, Vol. 117, No. 1 (March 2006), pp. 222-239.
Artūras Dubickas, On a sequence related to that of Thue-Morse and its applications, Discrete Math., Vol. 307, No. 9-10 (2007), pp. 1082-1093. MR2292537 (2008b:11086).
Cor Kraaikamp, Thomas A. Schmidt and Wolfgang Steiner, Natural extensions and entropy of alpha-continued fractions, arXiv:1011.4283 [math.DS], 2010-2012.
Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003. - _N. J. A. Sloane_, Sep 09 2018. See page 2.
Kevin Ryde, PARI/GP Code
Jeffrey Shallit, Automaticity IV: Sequences, sets, and diversity, J. Théor. Nombres Bordeaux, Vol. 8, No. 2 (1996), pp. 347-367. See page 354.

Cf. A010060, A001285, A101615, A026490 (run lengths).
A080426 is an essentially identical sequence with another set of constructions.
Cf. A104248 (bisection odious), A143331 (bisection evil), A003159 (partial sums).
Cf. A187061, A363361 (as continued fraction).

import Data.List (group)
a026465 n = a026465_list !! (n-1)
a026465_list = map length $ group a010060_list
-- Reinhard Zumkeller, Jul 15 2014

# From Carlo Carminati, Feb 25 2011:
## period-doubling routine:
double:=proc(SS)
NEW:=[op(S), op(S)]:
if op(nops(NEW),NEW)=1
then NEW:=[seq(op(j,NEW), j=1..nops(NEW)-2),op(nops(NEW)-1,NEW)+1]:
else NEW:=[seq(op(j,NEW), j=1..nops(NEW)-1),op(nops(NEW)-1,NEW)-1,1]:
fi:
end proc:
# 10 loops of the above routine generate the first 1365 terms of the sequence
# (except for the initial term):
S:=[2]:
for j from 1 to 10  do S:=double(S); od:
S;
# From N. J. A. Sloane, Dec 31 2013:
S:=[b]; M:=14;
for n from 1 to M do T:=subs({b=[b,a,a], a=[b]}, S);
    S := map(x->op(x),T); od:
T:=subs({a=1,b=2},S): T:=[1,op(T)]: [seq(T[n],n=1..40)];

Length /@ Split@ Nest[ Flatten@ Join[#, # /. {1 -> 2, 2 -> 1}] &, {1}, 7]
NestList[ Flatten[# /. {1 -> {2}, 2 -> {1, 1, 2}}] &, {1}, 7] // Flatten (* Robert G. Wilson v, May 20 2014 *)

PARI
```
\\ See links.
```

def A026465(n):
    if n==1: return 1
    def iterfun(f,n=0):
        m, k = n, f(n)
        while m != k: m, k = k, f(k)
        return m
    def f(x):
        c, s = x, bin(x)[2:]
        l = len(s)
        for i in range(l&1^1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    return iterfun(lambda x:f(x)+n,n)-iterfun(lambda x:f(x)+n-1,n-1) # Chai Wah Wu, Jan 29 2025

a(1) = 1; for n > 1, a(n) = A003159(n) - A003159(n-1). - Benoit Cloitre, May 31 2003
G.f.: Product_{k>=1} (1 + x^A001045(k)). - Paul Barry, Dec 09 2004
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 3/2. - Amiram Eldar, Jan 16 2022

Corrected and extended by John W. Layman, Feb 18 2003

Definition revised by N. J. A. Sloane, Dec 30 2013

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A047849 a(n) = (4^n + 2)/3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Python

Formula

Extensions

A060747 a(n) = 2*n - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A015531 Linear 2nd order recurrence: a(n) = 4*a(n-1) + 5*a(n-2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A059570 Number of fixed points in all 231-avoiding involutions in S_n.

Views

Author

Keywords

Comments

A015531 Linear 2nd order recurrence: a(n) = 4a(n-1) + 5a(n-2).

A015565 a(n) = 7a(n-1) + 8a(n-2), a(0) = 0, a(1) = 1.

A097073 Expansion of (1-x+2x^2)/((1+x)(1-2*x)).