|
%I M1644 #284 Mar 28 2024 21:56:36
%S 1,2,6,20,68,232,792,2704,9232,31520,107616,367424,1254464,4283008,
%T 14623104,49926400,170459392,581984768,1987020288,6784111616,
%U 23162405888,79081400320,270000789504,921840357376,3147359850496
%N a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - 2*a(n-2), n >= 2.
%C a(n)/a(n-1) approaches 2 + sqrt(2). - _Zak Seidov_, Oct 12 2002
%C 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 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
%C 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 a(n) is the sum of (n+1)-th row terms of triangle A140070. - _Gary W. Adamson_, May 04 2008
%C The binomial transform is in A083878, the Catalan transform in A084868. - _R. J. Mathar_, Nov 23 2008
%C Equals row sums of triangle A152252. - _Gary W. Adamson_, Nov 30 2008
%C 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 From _L. Edson Jeffery_, Apr 04 2011: (Start)
%C Let U_1 and U_3 be the unit-primitive matrices (see [Jeffery])
%C U_1 = U_(8,1) = [(0,1,0,0); (1,0,1,0); (0,1,0,1); (0,0,2,0)] and
%C 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)
%C 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 a(n) is the first superdiagonal of array A228405. - _Richard R. Forberg_, Sep 02 2013
%C 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 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 From _Gary W. Adamson_, Jul 22 2016: (Start)
%C A production matrix for the sequence is M =
%C 1, 1, 0, 0, 0, 0, ...
%C 1, 0, 3, 0, 0, 0, ...
%C 1, 0, 0, 3, 0, 0, ...
%C 1, 0, 0, 0, 3, 0, ...
%C 1, 0, 0, 0, 0, 3, ...
%C ...
%C Take powers of M, extracting the upper left terms; getting the sequence starting: (1, 1, 2, 6, 20, 68, ...).
%C (End)
%C From _Gary W. Adamson_, Jul 24 2016: (Start)
%C 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 N=1 (A000079): 1, 2, 4, 8, 16, 32, ...
%C N-2 (A001519): 1, 2, 5, 13, 34, 89, ...
%C N=3 (A006012): 1, 2, 6, 20, 68, 232, ...
%C N=4 (A052961): 1, 2, 7, 29, 124, 533, ...
%C N=5 (A154626): 1, 2, 8, 40, 208, 1088, ...
%C N=6: 1, 2, 9, 53, 326, 2017, ...
%C ...
%C (End)
%C 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 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
%D D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms. Birkhäuser, Boston, 3rd edition, 1990, p. 86.
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.8 Answer to Exer. 8.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A006012/b006012.txt">Table of n, a(n) for n = 0..1000</a>
%H 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 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 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=155">Encyclopedia of Combinatorial Structures 155</a>
%H 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 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 Yonah Biers-Ariel, <a href="https://arxiv.org/abs/1706.07064">A New Sequence Counted by OEIS Sequence a006012</a>, arXiv:1706.07064 [math.CO], 2017.
%H 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 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 CombOS - Combinatorial Object Server, <a href="http://combos.org/jump">Generate pattern-avoiding permutations</a>
%H 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 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 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 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 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 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 L. E. Jeffery, <a href="/wiki/User:L._Edson_Jeffery/Unit-Primitive_Matrices">Unit-primitive matrices</a>
%H 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 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 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 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 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 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 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H 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 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 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 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2).
%F G.f.: (1-2*x)/(1 - 4*x + 2*x^2).
%F a(n) = 2*A007052(n-1) = A056236(n)/2.
%F Binomial transform of A001333. E.g.f. exp(2x)cosh(x*sqrt(2)). - _Paul Barry_, May 08 2003
%F 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 a(n) = ((2+sqrt(2))^n + (2-sqrt(2))^n)/2.
%F a(n) = Sum_{k=0..n} 2^k*A098158(n,k). - _Philippe Deléham_, Dec 04 2006
%F a(n) = A007070(n) - 2*A007070(n-1). - _R. J. Mathar_, Nov 16 2007
%F a(n) = Sum_{k=0..n} A147703(n,k). - _Philippe Deléham_, Nov 29 2008
%F a(n) = Sum_{k=0..n} A201730(n,k). - _Philippe Deléham_, Dec 05 2011
%F 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 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 a(-n) = a(n) / 2^n for all n in Z. - _Michael Somos_, Aug 24 2014
%F a(n) = A265185(n) / 4, connecting this sequence to the simple Lie algebra B_4. - _Tom Copeland_, Dec 04 2015
%F E.g.f.: exp(2*x)*cosh(sqrt(2)*x). - _Stefano Spezia_, Nov 13 2019
%p A006012:=-(-1+2*z)/(1-4*z+2*z**2); # _Simon Plouffe_ in his 1992 dissertation
%p 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 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 (PARI) {a(n) = real(((2 + quadgen(8))^n))}; /* _Michael Somos_, Feb 12 2004 */
%o (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 (PARI) Vec((1-2*x)/(1-4*x+2*x^2) + O(x^100)) \\ _Altug Alkan_, Dec 05 2015
%o (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 (Haskell)
%o a006012 n = a006012_list !! n
%o a006012_list = 1 : 2 : zipWith (-) (tail $ map (* 4) a006012_list)
%o (map (* 2) a006012_list)
%o -- _Reinhard Zumkeller_, Oct 03 2011
%o (Python)
%o l = [1, 2]
%o for n in range(2, 101): l.append(4 * l[n - 1] - 2 * l[n - 2])
%o print(l) # _Indranil Ghosh_, Jul 02 2017
%Y Cf. A140070, A152252, A024175, A030436, A094803, A003480, A265185, A000079, A001519, A052961, A154626.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
|
