cp's OEIS Frontend

A006012 a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - 2*a(n-2), n >= 2.

%I A006012 M1644 #312 Aug 30 2025 10:11:43
%S A006012 1,2,6,20,68,232,792,2704,9232,31520,107616,367424,1254464,4283008,
%T A006012 14623104,49926400,170459392,581984768,1987020288,6784111616,
%U A006012 23162405888,79081400320,270000789504,921840357376,3147359850496
%N A006012 a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - 2*a(n-2), n >= 2.
%C A006012 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
%C A006012 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
%C A006012 a(n) is the sum of (n+1)-th row terms of triangle A140070. - _Gary W. Adamson_, May 04 2008
%C A006012 The binomial transform is in A083878, the Catalan transform in A084868. - _R. J. Mathar_, Nov 23 2008
%C A006012 Equals row sums of triangle A152252. - _Gary W. Adamson_, Nov 30 2008
%C A006012 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
%C A006012 From _L. Edson Jeffery_, Apr 04 2011: (Start)
%C A006012 Let U_1 and U_3 be the unit-primitive matrices (see [Jeffery])
%C A006012 U_1 = U_(8,1) = [(0,1,0,0); (1,0,1,0); (0,1,0,1); (0,0,2,0)] and
%C A006012 U_3 = U_(8,3) = [(0,0,0,1); (0,0,2,0); (0,2,0,1); (2,0,2,0)]. Then a(n) = (1/4) * Trace(U_1^(2*n)) = (1/2^(n+2)) * Trace(U_3^(2*n)). (See also A084130, A001333.) (End)
%C A006012 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
%C A006012 a(n) is the first superdiagonal of array A228405. - _Richard R. Forberg_, Sep 02 2013
%C A006012 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
%C A006012 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
%C A006012 From _Gary W. Adamson_, Jul 22 2016: (Start)
%C A006012 A production matrix for the sequence is M =
%C A006012   1, 1, 0, 0, 0, 0, ...
%C A006012   1, 0, 3, 0, 0, 0, ...
%C A006012   1, 0, 0, 3, 0, 0, ...
%C A006012   1, 0, 0, 0, 3, 0, ...
%C A006012   1, 0, 0, 0, 0, 3, ...
%C A006012   ...
%C A006012 Take powers of M, extracting the upper left terms; getting the sequence starting: (1, 1, 2, 6, 20, 68, ...). (End)
%C A006012 From _Gary W. Adamson_, Jul 24 2016: (Start)
%C A006012 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:
%C A006012    N=1 (A000079):  1, 2, 4,  8,  16,   32, ...
%C A006012    N=2 (A001519):  1, 2, 5, 13,  34,   89, ...
%C A006012    N=3 (A006012):  1, 2, 6, 20,  68,  232, ...
%C A006012    N=4 (A052961):  1, 2, 7, 29, 124,  533, ...
%C A006012    N=5 (A154626):  1, 2, 8, 40, 208, 1088, ...
%C A006012    N=6:            1, 2, 9, 53, 326, 2017, ...
%C A006012    ... (End)
%C A006012 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
%C A006012 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
%C A006012 Consider a stack of pancakes of height n, where the only allowed operation is reversing the top portion of the stack. First, perform a series of reversals of decreasing sizes, followed by a series of reversals of increasing sizes. The number of distinct permutations of the initial stack that can be reached through these operations is a(n). - _Thomas Baruchel_, May 12 2025
%C A006012 Number of permutations of [n] that are correctly sorted after performing one left-to-right pass and one right-to-left pass of the cocktail sort. - _Thomas Baruchel_, May 16 2025
%D A006012 D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms. Birkhäuser, Boston, 3rd edition, 1990, p. 86.
%D A006012 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.8 Answer to Exer. 8.
%D A006012 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006012 Vincenzo Librandi, <a href="/A006012/b006012.txt">Table of n, a(n) for n = 0..1000</a>
%H A006012 Andrei Asinowski and Cyril Banderier, <a href="https://arxiv.org/abs/2401.05558">From geometry to generating functions: rectangulations and permutations</a>, arXiv:2401.05558 [cs.DM], 2024. See page 2.
%H A006012 Andrei Asinowski and Toufik Mansour, <a href="http://arxiv.org/abs/0803.3414">Separable d-Permutations and Guillotine Partitions</a>, arXiv 0803.3414 [math.CO], 2008. Annals of Combinatorics 14 (1) pp.17-43 Springer, 2010; <a href="http://www.combinatorics.net/Annals/Abstract/14_1_17.aspx">Abstract</a>
%H A006012 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=155">Encyclopedia of Combinatorial Structures 155</a>
%H A006012 George Balla, Ghislain Fourier, and Kunda Kambaso, <a href="https://arxiv.org/abs/2205.01747">PBW filtration and monomial bases for Demazure modules in types A and C</a>, arXiv:2205.01747 [math.RT], 2022.
%H A006012 M. Barnabei, F. Bonetti, and M. Silimbani, <a href="https://doi.org/10.37236/2556">Two permutation classes related to the Bubble Sort operator</a>, Electronic Journal of Combinatorics 19(3) (2012), #P25. - From _N. J. A. Sloane_, Dec 25 2012
%H A006012 Yonah Biers-Ariel, <a href="https://arxiv.org/abs/1706.07064">A New Quantity Counted by OEIS Sequence A006012</a>, arXiv:1706.07064 [math.CO], 2017.
%H A006012 Yonah Biers-Ariel, <a href="https://www.emis.de/journals/JIS/VOL20/Biers/biers3.html">The Number of Permutations Avoiding a Set of Generalized Permutation Patterns</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.3.
%H A006012 Rocco Chirivì, Xin Fang, and Ghislain Fourier, <a href="https://doi.org/10.1007/s00031-020-09558-4">Degenerate Schubert varieties in type A</a>, Transformation Groups (2020).
%H A006012 CombOS - Combinatorial Object Server, <a href="http://combos.org/jump">Generate pattern-avoiding permutations</a>
%H A006012 Sergi Elizalde, <a href="https://arxiv.org/abs/0710.5168">The X-class and almost-increasing permutations</a>, arXiv:0710.5168 [math:CO], 2007. Ann. Comb. 15 (2011), 51-68.
%H A006012 S. Felsner and D. Heldt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Felsner/felsner2.html">Lattice Path Enumeration and Toeplitz Matrices</a>, J. Int. Seq. 18 (2015) # 15.1.3.
%H A006012 Luca Ferrari, <a href="https://arxiv.org/abs/1906.10553">Enhancing the connections between patterns in permutations and forbidden configurations in restricted elections</a>, arXiv:1906.10553 [math.CO], 2019.
%H A006012 Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.
%H A006012 Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H A006012 Alice L. L. Gao and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H A006012 L. E. Jeffery, <a href="/wiki/User:L._Edson_Jeffery/Unit-Primitive_Matrices">Unit-primitive matrices</a>
%H A006012 Donghyun Kim and Lauren Williams, <a href="https://arxiv.org/abs/2106.13378">Schubert polynomials, the inhomogeneous TASEP, and evil-avoiding permutations</a>, arXiv:2106.13378 [math.CO], 2021.
%H A006012 Sergey Kitaev and Artem Pyatkin, <a href="https://arxiv.org/abs/2204.08936">On permutations avoiding partially ordered patterns defined by bipartite graphs</a>, arXiv:2204.08936 [math.CO], 2022.
%H A006012 Joshua Marsh and Nathan Williams, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Williams/williams9.html">Nesting Nonpartitions</a>, J. Int. Seq., Vol. 25 (2022), Article 22.8.8.
%H A006012 Arturo Merino and Torsten Mütze, <a href="https://arxiv.org/abs/2103.09333">Combinatorial generation via permutation languages. III. Rectangulations</a>, arXiv:2103.09333 [math.CO], 2021.
%H A006012 Joris Nieuwveld, <a href="https://arxiv.org/abs/2108.11382">Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding</a>, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.
%H A006012 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A006012 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A006012 J. Riordan, <a href="http://www.jstor.org/stable/2005477">The distribution of crossings of chords joining pairs of 2n points on a circle</a>, Math. Comp., 29 (1975), 215-222.
%H A006012 Markus Saers, Dekai Wu, and Chris Quirk, <a href="http://www.cse.ust.hk/~dekai/library/WU_Dekai/SaersWuQuirk_Mtsummit2011.pdf">On the Expressivity of Linear Transductions</a>.
%H A006012 Yi-dong Sun and Cang-zhi Jia, <a href="http://dx.doi.org/10.3770/j.issn:1000-341X.2007.02.005">Counting Dyck paths with strictly increasing peak sequences</a>, J. Math. Res. Expos. 27 (2) (2007) 253, Theorem 3.11.
%H A006012 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2).
%F A006012 G.f.: (1-2*x)/(1 - 4*x + 2*x^2).
%F A006012 a(n) = 2*A007052(n-1) = A056236(n)/2.
%F A006012 Limit_{n -> oo} a(n)/a(n-1) = 2 + sqrt(2). - _Zak Seidov_, Oct 12 2002
%F A006012 From _Paul Barry_, May 08 2003: (Start)
%F A006012 Binomial transform of A001333.
%F A006012 E.g.f.: exp(2*x)*cosh(sqrt(2)*x). (End)
%F A006012 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)^k)/2. - _Paul Barry_, Nov 22 2003 (typo corrected by _Manfred Scheucher_, Jan 17 2023)
%F A006012 a(n) = ((2+sqrt(2))^n + (2-sqrt(2))^n)/2.
%F A006012 a(n) = [M^n]_{2,2}, where M is the 3 X 3 matrix: M = [1,1,1;1,2,1;1,1,1]. - _Simone Severini_, Jun 11 2006
%F A006012 a(n) = Sum_{k=0..n} 2^k*A098158(n,k). - _Philippe Deléham_, Dec 04 2006
%F A006012 a(n) = A007070(n) - 2*A007070(n-1). - _R. J. Mathar_, Nov 16 2007
%F A006012 a(n) = Sum_{k=0..n} A147703(n,k). - _Philippe Deléham_, Nov 29 2008
%F A006012 a(n) = Sum_{k=0..n} A201730(n,k). - _Philippe Deléham_, Dec 05 2011
%F A006012 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
%F A006012 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
%F A006012 a(-n) = a(n) / 2^n for all n in Z. - _Michael Somos_, Aug 24 2014
%F A006012 a(n) = A265185(n) / 4, connecting this sequence to the simple Lie algebra B_4. - _Tom Copeland_, Dec 04 2015
%F A006012 From _G. C. Greubel_, Aug 27 2025: (Start)
%F A006012 a(n) = 2^((n-2)/2)*( (n+1 mod 2)*A002203(n) + 2*sqrt(2)*(n mod 2)*A000129(n) ).
%F A006012 a(n) = 2^(n/2)*ChebyshevT(n, sqrt(2)). (End)
%p A006012 A006012:=-(-1+2*z)/(1-4*z+2*z**2); # _Simon Plouffe_ in his 1992 dissertation
%p A006012 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
%t A006012 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 *)
%o A006012 (PARI) {a(n) = real(((2 + quadgen(8))^n))}; /* _Michael Somos_, Feb 12 2004 */
%o A006012 (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 */
%o A006012 (PARI) Vec((1-2*x)/(1-4*x+2*x^2) + O(x^100)) \\ _Altug Alkan_, Dec 05 2015
%o A006012 (Magma) [n le 2 select n else 4*Self(n-1)- 2*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Apr 05 2011
%o A006012 (Haskell)
%o A006012 a006012 n = a006012_list !! n
%o A006012 a006012_list = 1 : 2 : zipWith (-) (tail $ map (* 4) a006012_list)
%o A006012 (map (* 2) a006012_list)
%o A006012 -- _Reinhard Zumkeller_, Oct 03 2011
%o A006012 (Python)
%o A006012 l = [1, 2]
%o A006012 for n in range(2, 101): l.append(4 * l[n - 1] - 2 * l[n - 2])
%o A006012 print(l)  # _Indranil Ghosh_, Jul 02 2017
%o A006012 (SageMath)
%o A006012 A006012=BinaryRecurrenceSequence(4,-2,1,2)
%o A006012 print([A006012(n) for n in range(41)]) # _G. C. Greubel_, Aug 27 2025
%Y A006012 Cf. A000079, A000129, A001333, A001519, A002203, A003480, A007052, A007070, A024175, A030436, A052961, A056236, A083978, A084130, A084868, A094803, A098158, A140070, A147703, A152252, A154626, A201730, A228405, A265185.
%K A006012 nonn,easy,changed
%O A006012 0,2
%A A006012 _N. J. A. Sloane_