

A047849


a(n) = (4^n + 2)/3.


30



1, 2, 6, 22, 86, 342, 1366, 5462, 21846, 87382, 349526, 1398102, 5592406, 22369622, 89478486, 357913942, 1431655766, 5726623062, 22906492246, 91625968982, 366503875926, 1466015503702, 5864062014806, 23456248059222, 93824992236886, 375299968947542
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6.  Paul Barry, Mar 10 2004
The number of closed walks of odd length of the cyclic graph is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case.  Wolfdieter Lang, Nov 08 2011
A. A. Ivanov conjectures that the dimension of the universal embedding of the unitary dual polar space DSU(2n,4) is a(n).  J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004
Permutations with two fixed points avoiding 123 and 132.
Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302.  Paul Curtz, Mar 25 2008
Also the number of permutations of length n which avoid 4321 and 4123 (or 4321 and 3412, or 4123 and 3214, or 4123 and 2143).  Vincent Vatter, Aug 17 2009
This sequence is related to A014916 by A014916(n) = n*a(n)sum(a(i), i=0..n1).  Bruno Berselli, Jul 27 2010, Mar 02 2012
For n>=2, a(n) equals 2^n times the permanent of the (2n2)X(2n2) tridiagonal matrix with 1/sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal.  John M. Campbell, Jul 08 2011
For n>0, counts closed walks of length (n) at a vertex of a triangle with two (x2) loops at each vertex.  David Neil McGrath, Sep 11 2014
From Michel Lagneau, Feb 26 2015: (Start)
a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.
Proof:
All integers of the set {2^(n1)+1, 2^(n1)+2,..., 2^n} are of the form 2^k(2m+1) where k and m integers. The greatest odd divisor of a such integer is 2m+1. Reciprocally, if 2m+1 is a odd integer <=2^n, there exists an unique integer in the set {2^(n1)+1, 2^(n1)+2,...,2^n} where 2m+1 is the greatest odd divisor. Hence the recurrence relation:
a(n) = a(n+1) + (1 + 3 +...+ 2*2^(n1)  1) = a(n1) + 4^(n1) for n>=2.
We obtain immediately : a(n) = a(1) + 4 +...+4^n = (4^n+2)/3.
(End)


LINKS

B. Berselli, Table of n, a(n) for n = 0..1000
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
B. Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 3748. See Conjecture 5.5.
Kremer, D. and Shiu, W. C. Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Mathematics 268 (2003), 171183.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.
Wikipedia, Permutation classes avoiding two patterns of length 4.
Index entries for linear recurrences with constant coefficients, signature (5,4).


FORMULA

nth difference of a(n), a(n1), ..., a(0) is 3^(n1) for n>=1.
a(n) = (4^n+2)/3 = 4*a(n1)2 = 5*a(n1)4*a(n2) = 2*A007583(n1) = A002450(n)+1.  Henry Bottomley, Aug 29 2000
a(n) = T(1,n), array T given by A047848.
With interpolated zeros, this is (2)^n/6+2^n/6+(1)^n/3+1/3.  Paul Barry, Aug 26 2003
a(n) = A007583(n)  A002450(n) = A001045(2n+1)  A001045(2n) .  Philippe Deléham, Feb 25 2004
Second binomial transform of A078008. Binomial transform of 1, 1, 3, 9, 81, .. (3^n/3+2*0^n/3). a(n) = A078008(2n).  Paul Barry, Mar 14 2004
G.f.: (13*x)/((1x)*(14*x)).  Herbert Kociemba, Jun 06 2004
a(n) = Sum_{k, 0<=k<=n} 2^k*A121314(n,k).  Philippe Deléham, Sep 15 2006
a(n) = A002450(n)+1.  Artur Jasinski, Jan 29 2007
a(n) = (A001045(2n+1)+1)/2.  Paul Barry, Dec 05 2007
From Bruno Berselli, Jul 27 2010: (Start)
a(n) = A020988(n)/2+1 = A039301(n+1)/2.
Sum(a(i), i=0..n) = A073724(n).
(End)
For n>=3, a(n) equals [2, 1, 1; 1, 2, 1; 1, 1, 2]^(n  2)*{1, 1, 2}*{1, 1, 2}.  John M. Campbell, Jul 09 2011


EXAMPLE

a(2) = 6 for the number of round trips in C_6 from the six round trips from, say, vertex no. 1: 12121, 16161, 12161, 16121, 12321 and 16561.  Wolfdieter Lang, Nov 08 2011


MATHEMATICA

a = {}; k = 1; Do[k = k + 2^(2x); AppendTo[a, k], {x, 0, 100}]; a (* Artur Jasinski, Jan 29 2007 *)
(4^Range[0, 30]+2)/3 (* or *) LinearRecurrence[{5, 4}, {1, 2}, 30] (* Harvey P. Dale, Nov 27 2015 *)


PROG

(PARI) a(n)=(4^n+2)/3
(MAGMA) [(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015


CROSSREFS

Cf. A002450, A007583.
Cf. A014916, A073724, A020988, A039301.  Bruno Berselli, Jul 27 2010
Sequence in context: A107245 A107246 A107247 * A277222 A150256 A150257
Adjacent sequences: A047846 A047847 A047848 * A047850 A047851 A047852


KEYWORD

nonn,easy,walk


AUTHOR

Clark Kimberling


EXTENSIONS

New name from Charles R Greathouse IV, Dec 22 2011
Minor correction by Henning Ulfarsson, May 14 2017, to pattern avoidance comment by Vincent Vatter.


STATUS

approved



