login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006012 a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - 2*a(n-2), n >= 2.
(Formerly M1644)
43
1, 2, 6, 20, 68, 232, 792, 2704, 9232, 31520, 107616, 367424, 1254464, 4283008, 14623104, 49926400, 170459392, 581984768, 1987020288, 6784111616, 23162405888, 79081400320, 270000789504, 921840357376, 3147359850496 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n)/a(n-1) approaches 2 + sqrt(2). - Zak Seidov, Oct 12 2002

Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 8 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 4, s(2n) = 4. - Herbert Kociemba, Jun 12 2004

a(k) = [M^k]_{2,2}, where M is the following 3 X 3 matrix: M = [1,1,1;1,2,1;1,1,1]. - Simone Severini, Jun 11 2006

a(n-1) counts permutations pi on [n] for which the pairs {i, pi(i)} with i < pi(i), considered as closed intervals [i+1,pi(i)], do not overlap; equivalently, for each i in [n] there is at most one j <= i with pi(j) > i. Counting these permutations by the position of n yields the recurrence relation. - David Callan, Sep 02 2003

a(n) = sum of (n+1)-th row terms of triangle A140070. - Gary W. Adamson, May 04 2008

The binomial transform is in A083878, the Catalan transform in A084868. - R. J. Mathar, Nov 23 2008

Equals row sums of triangle A152252. - Gary W. Adamson, Nov 30 2008

Counts all paths of length (2*n), n>=0, starting at the initial node on the path graph P_7, see the second Maple program. - Johannes W. Meijer, May 29 2010

From L. Edson Jeffery, Apr 04 2011: (Start)

Let U_1 and U_3 be the unit-primitive matrices (see [Jeffery])

U_1 = U_(8,1) = [(0,1,0,0);(1,0,1,0);(0,1,0,1);(0,0,2,0)] and

U_3 = U_(8,3) = [(0,0,0,1);(0,0,2,0);(0,2,0,1);(2,0,2,0)]. Then A006012(n) = (1/4) * Trace(U_1^(2*n)) = 1/2^(n+2) * Trace(U_3^(2*n)). (See also A084130, A001333.) (End)

Pisano period lengths: 1, 1, 8, 1, 24, 8, 6, 1, 24, 24, 120, 8, 168, 6, 24, 1, 8, 24, 360, 24, ... - R. J. Mathar, Aug 10 2012

a(n) is the first supra-diagonal of array A228405. - Richard R. Forberg, Sep 02 2013

Conjecture: With offset 1, a(n) is the number of permutations on [n] with no subsequence abcd such that (i) bc are adjacent in position and (ii) max(a,c) < min(b,d). For example, the 4 permutations of [4] not counted by a(4) are 1324, 1423, 2314, 2413. - David Callan, Aug 27 2014

The conjecture of David Callan above is correct - with offset 1, a(n) is the number of permutations on [n] with no subsequence abcd such that (i) bc are adjacent in position and (ii) max(a,c) < min(b,d). - Yonah Biers-Ariel, Jun 27 2017

a(n) = A265185(n) / 4, connecting this sequence to the simple Lie algebra B_4. - Tom Copeland, Dec 04 2015

A production matrix for the sequence is M =

1, 1, 0, 0, 0, 0, ...

1, 0, 3, 0, 0, 0, ...

1, 0, 0, 3, 0, 0, ...

1, 0, 0, 0, 3, 0, ...

1, 0, 0, 0, 0, 3, ...

...Take powers of M, extracting the upper left terms; getting the sequence starting:

(1, 1, 2, 6, 20, 68, ...). - Gary W. Adamson, Jul 22 2016

The sequence is the INVERT transform of the powers of 3 prefaced with a "1": (1, 1, 3, 9, 27, ...) and is N=3 in an infinite of analogous sequences starting:

N=1 (A000079):..1, 2, 4,..8,..16,...32,...

N-2 (A001519):..1, 2, 5, 13,..34,...89,...

N=3 (A006012):..1, 2, 6, 20,..68,..232,...

N=4 (A052961):..1, 2, 7, 29,.124,..533,...

N=5 (A154626):..1, 2, 8, 40,.208,.1088,...

N=6 ............1, 2, 9, 53,.326,.2017,...

... - Gary W. Adamson, Jul 24 2016

REFERENCES

D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms. Birkhäuser, Boston, 3rd edition, 1990, p. 86.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.8 Answer to Exer. 8.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Andrei Asinowski and Toufik Mansour, Separable d-Permutations and Guillotine Partitions, arXiv 0803.3414 [math.CO], 2008. Annals of Combinatorics 14 (1) pp.17-43 Springer, 2010; Abstract

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 155

M. Barnabei, F. Bonetti and M. Silimbani, Two permutation classes related to the Bubble Sort operator, Electronic Journal of Combinatorics 19(3) (2012), #P25. - From N. J. A. Sloane, Dec 25 2012

Yonah Biers-Ariel, A New Sequence Counted by OEIS Sequence a006012, arXiv:1706.07064 [math.CO], 2017.

Yonah Biers-Ariel, The Number of Permutations Avoiding a Set of Generalized Permutation Patterns, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.3.

L. E. Jeffery, Unit-primitive matrices

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.

Markus Saers, Dekai Wu and Chris Quirk, On the Expressivity of Linear Transductions.

Yi-dong Sun, Cang-zhi Jia, Counting Dyck paths with strictly increasing peak sequences, J. Math. Res. Expos. 27 (2) (2007) 253, Theorem 3.11.

Index entries for linear recurrences with constant coefficients, signature (4,-2).

FORMULA

G.f.: (1-2*x)/(1 - 4*x + 2*x^2).

a(n) = 2*A007052(n-1) = A056236(n)/2.

Binomial transform of A001333. E.g.f. exp(2x)cosh(x*sqrt(2)). - Paul Barry, May 08 2003

a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)*2^(n-k) = Sum_{k=0..n} binomial(n, k)*2^(n-k/2)(1+(-1)^n)/2. - Paul Barry, Nov 22 2003

a(n) = ((2+sqrt(2))^n + (2-sqrt(2))^n)/2.

a(n) = Sum_{k=0..n} 2^k*A098158(n,k). - Philippe Deléham, Dec 04 2006

a(n) = A007070(n) - 2*A007070(n-1). - R. J. Mathar, Nov 16 2007

a(n) = Sum_{k=0..n} A147703(n,k). - Philippe Deléham, Nov 29 2008

a(n) = Sum_{k=0..n} A201730(n,k). - Philippe Deléham, Dec 05 2011

G.f.: G(0) where G(k)= 1 + 2*x/((1-2*x) - 2*x*(1-2*x)/(2*x + (1-2*x)*2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 10 2012

G.f.: G(0)*(1-2*x)/2, where G(k) = 1 + 1/(1 - 2*x*(4*k+2-x)/( 2*x*(4*k+4-x) + 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Jan 27 2014

a(-n) = a(n) / 2^n for all n in Z. - Michael Somos, Aug 24 2014

MAPLE

A006012:=-(-1+2*z)/(1-4*z+2*z**2); # Simon Plouffe in his 1992 dissertation

with(GraphTheory): G:=PathGraph(7): A:= AdjacencyMatrix(G): nmax:=24; n2:=2*nmax: for n from 0 to n2 do B(n):=A^n; a(n):=add(B(n)[1, k], k=1..7); od: seq(a(2*n), n=0..nmax); # Johannes W. Meijer, May 29 2010

MATHEMATICA

LinearRecurrence[{4, -2}, {1, 2}, 50] (* or *) With[{c=Sqrt[2]}, Simplify[ Table[((2+c)^n+(3+2c)(2-c)^n)/(2(2+c)), {n, 50}]]] (* Harvey P. Dale, Aug 29 2011 *)

PROG

(PARI) {a(n) = real(((2 + quadgen(8))^n))}; /* Michael Somos, Feb 12 2004 */

(PARI) {a(n) = if( n<0, 2^n, 1) * polsym(x^2 - 4*x + 2, abs(n))[abs(n)+1] / 2}; /* Michael Somos, Feb 12 2004 */

(MAGMA) [n le 2 select n else 4*Self(n-1)- 2*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Apr 05 2011

(Haskell)

a006012 n = a006012_list !! n

a006012_list = 1 : 2 : zipWith (-) (tail $ map (* 4) a006012_list)

(map (* 2) a006012_list)

-- Reinhard Zumkeller, Oct 03 2011

(PARI) Vec((1-2*x)/(1-4*x+2*x^2) + O(x^100)) \\ Altug Alkan, Dec 05 2015

(Python)

l=[1, 2]

for n in xrange(2, 101): l+=[4*l[n - 1] - 2*l[n - 2], ]

print l # Indranil Ghosh, Jul 02 2017

CROSSREFS

Cf. A140070, A152252, A024175, A030436, A094803, A003480, A265185, A000079, A001519, A052961, A154626.

Sequence in context: A027065 A231057 A295873 * A127152 A279557 A150120

Adjacent sequences:  A006009 A006010 A006011 * A006013 A006014 A006015

KEYWORD

nonn,easy,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Feb 21 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 12:59 EST 2018. Contains 299623 sequences. (Running on oeis4.)