|
| |
|
|
A006012
|
|
a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - 2*a(n-2), 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(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
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 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
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 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, ...
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
|
|
|
|
FORMULA
|
G.f.: (1-2*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^(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)
a(n) = ((2+sqrt(2))^n + (2-sqrt(2))^n)/2.
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) = 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)(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 */
(PARI) Vec((1-2*x)/(1-4*x+2*x^2) + O(x^100)) \\ Altug Alkan, Dec 05 2015
(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)
(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
|
| |
|
|
