login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

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)
45
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

From Gary W. Adamson, Jul 22 2016: (Start)

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, ...).

(End)

From Gary W. Adamson, Jul 24 2016: (Start)

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,...

...

(End)

Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>2, 1>3, 4>2, 4>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first and fourth elements are larger than the second and third elements. - Sergey Kitaev, Dec 08 2020

a(n-1) is the number of permutations of [n] that can be obtained by placing n points on an X-shape (two crossing lines with slopes 1 and -1), labeling them 1,2,...,n by increasing y-coordinate, and then reading the labels by increasing x-coordinate. - Sergi Elizalde, Sep 27 2021

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.

Rocco Chirivì, Xin Fang, and Ghislain Fourier, Degenerate Schubert varieties in type A, Transformation Groups (2020).

CombOS - Combinatorial Object Server, Generate pattern-avoiding permutations

Sergi Elizalde, The X-class and almost-increasing permutations, arXiv:0710.5168 [math:CO], 2007.  Ann. Comb. 15 (2011), 51-68.

S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.

Luca Ferrari, Enhancing the connections between patterns in permutations and forbidden configurations in restricted elections, arXiv:1906.10553 [math.CO], 2019.

Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.

Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

L. E. Jeffery, Unit-primitive matrices

Donghyun Kim and Lauren Williams, Schubert polynomials, the inhomogeneous TASEP, and evil-avoiding permutations, arXiv:2106.13378 [math.CO], 2021.

Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.

Joris Nieuwveld, Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.

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, Appendix to Thesis, Montreal, 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 and 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

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

E.g.f.: exp(2*x)*cosh(sqrt(2)*x). - Stefano Spezia, Nov 13 2019

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 range(2, 101): l.append(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

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 12:47 EST 2021. Contains 349463 sequences. (Running on oeis4.)