

A006012


a(0) = 1, a(1) = 2, a(n) = 4*a(n1)  2*a(n2), n >= 2.
(Formerly M1644)


52



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(n1) 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(i1) = 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(n1) 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
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
Let U_1 and U_3 be the unitprimitive 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
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 BiersAriel, Jun 27 2017
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)
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, ...
N2 (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(n1) is the number of permutations of [n] that can be obtained by placing n points on an Xshape (two crossing lines with slopes 1 and 1), labeling them 1,2,...,n by increasing ycoordinate, and then reading the labels by increasing xcoordinate.  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. AddisonWesley, 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



FORMULA

G.f.: (12*x)/(1  4*x + 2*x^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^(nk) = Sum_{k=0..n} binomial(n, k)*2^(nk/2)(1+(1)^k)/2.  Paul Barry, Nov 22 2003 (typo corrected by Manfred Scheucher, Jan 17 2023)
a(n) = ((2+sqrt(2))^n + (2sqrt(2))^n)/2.
G.f.: G(0) where G(k)= 1 + 2*x/((12*x)  2*x*(12*x)/(2*x + (12*x)*2/G(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Dec 10 2012
G.f.: G(0)*(12*x)/2, where G(k) = 1 + 1/(1  2*x*(4*k+2x)/( 2*x*(4*k+4x) + 1/G(k+1) ); (continued fraction).  Sergei N. Gladkovskii, Jan 27 2014
a(n) = A265185(n) / 4, connecting this sequence to the simple Lie algebra B_4.  Tom Copeland, Dec 04 2015


MAPLE

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)(2c)^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 */
(PARI) Vec((12*x)/(14*x+2*x^2) + O(x^100)) \\ Altug Alkan, Dec 05 2015
(Magma) [n le 2 select n else 4*Self(n1) 2*Self(n2): 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)
(Python)
l = [1, 2]
for n in range(2, 101): l.append(4 * l[n  1]  2 * l[n  2])


CROSSREFS

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


KEYWORD

nonn,easy


AUTHOR



STATUS

approved



