The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A047849 a(n) = (4^n + 2)/3. 33
 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; minor correction by Henning Ulfarsson, May 14 2017 This sequence is related to A014916 by A014916(n) = n*a(n)-Sum_{i=0..n-1} a(i). - 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 a 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. Georgia Benkart, Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020. B. Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian). Pascal Caron, Jean-Gabriel Luque, Bruno Patrou, A combinatorial approach for the state complexity of the Shuffle product, arXiv:1905.08120 [cs.FL], 2019. 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. Kittitat Iamthong, Ji-Hwan Jung, Sergey Kitaev, Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations, arXiv:2009.01410 [math.CO], 2020. 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. 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. From Henry Bottomley, Aug 29 2000: (Start) a(n) = (4^n+2)/3 = 4*a(n-1) - 2. a(n) = 5*a(n-1) - 4*a(n-2). a(n) = 2*A007583(n-1) = A002450(n) + 1. (End) 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..n} 2^k*A121314(n,k). - Philippe Deléham, Sep 15 2006 a(n) = (A001045(2n+1)+1)/2. - Paul Barry, Dec 05 2007 From Bruno Berselli, Jul 27 2010: (Start) a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2. Sum_{i=0..n} a(i) = 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 a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - Oboifeng Dira, May 29 2020 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 (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 EXTENSIONS New name from Charles R Greathouse IV, Dec 22 2011 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.

Last modified July 29 06:21 EDT 2021. Contains 346340 sequences. (Running on oeis4.)