login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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..n-1). - Bruno Berselli, Jul 27 2010, Mar 02 2012

For n>=2, a(n) equals 2^n times the permanent of the (2n-2)X(2n-2) 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^(n-1)+1, 2^(n-1)+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^(n-1)+1, 2^(n-1)+2,...,2^n} where 2m+1 is the greatest odd divisor. Hence the recurrence relation:

   a(n) = a(n+1) + (1 + 3 +...+ 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) 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), 37-48. 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), 171-183.

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

n-th difference of a(n), a(n-1), ..., a(0) is 3^(n-1) for n>=1.

a(n) = (4^n+2)/3 = 4*a(n-1)-2 = 5*a(n-1)-4*a(n-2) = 2*A007583(n-1) = 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.: (1-3*x)/((1-x)*(1-4*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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 13:38 EST 2019. Contains 319271 sequences. (Running on oeis4.)