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

%I #172 Jan 15 2024 15:14:50

%S 1,2,6,22,86,342,1366,5462,21846,87382,349526,1398102,5592406,

%T 22369622,89478486,357913942,1431655766,5726623062,22906492246,

%U 91625968982,366503875926,1466015503702,5864062014806,23456248059222,93824992236886,375299968947542

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

%C Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6. - _Paul Barry_, Mar 10 2004

%C 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

%C 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

%C Permutations with two fixed points avoiding 123 and 132.

%C Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302. - _Paul Curtz_, Mar 25 2008

%C 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

%C 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

%C 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

%C 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

%C From _Michel Lagneau_, Feb 26 2015: (Start)

%C a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.

%C Proof:

%C 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 an 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:

%C a(n) = a(n+1) + (1 + 3 + ... + 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) for n >= 2.

%C We obtain immediately: a(n) = a(1) + 4 + ... + 4^n = (4^n+2)/3. (End)

%C The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - _Peter Bala_, Aug 12 2021

%C Let q = 2^(2n+1) and Omega_n be the Suzuki ovoid with q^2 + 1 points. Then a(n) is the number of orbits of the finite Suzuki group Sz(q) on 3-subsets of Omega_n. Link to result in References. - _Paul M. Bradley_, Jun 4 2023

%H Bruno Berselli, <a href="/A047849/b047849.txt">Table of n, a(n) for n = 0..1000</a>

%H Jeffrey M. Barnes, Georgia Benkart, and Tom Halverson, <a href="https://doi.org/10.1112/plms/pdv075">McKay centralizer algebras</a>. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).

%H Christian Bean, <a href="https://hdl.handle.net/20.500.11815/1184">Finding structure in permutation sets</a>, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.

%H Georgia Benkart and Tom Halverson, <a href="https://hal.archives-ouvertes.fr/hal-02173744">McKay Centralizer Algebras</a>, hal-02173744 [math.CO], 2020.

%H Bruno Berselli, A description of the recursive method in Comments lines: website <a href="http://www.lanostra-matematica.org/2008/12/sequenze-numeriche-e-procedimenti.html">Matem@ticamente</a> (in Italian).

%H Paul Bradley and Peter Rowley, <a href="https://doi.org/10.5802/alco.195">Orbits on k-subsets of 2-transitive Simple Lie-type Groups</a>, Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 37-51.

%H Pascal Caron, Jean-Gabriel Luque, and Bruno Patrou, <a href="https://arxiv.org/abs/1905.08120">A combinatorial approach for the state complexity of the Shuffle product</a>, arXiv:1905.08120 [cs.FL], 2019.

%H Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, and Seyed Ahmad Mojallal, <a href="https://doi.org/10.1016/j.laa.2019.05.033">Riordan graphs I: structural properties</a>, Linear Algebra and its Applications, 579. pp. 89-135, Prop. 2.8. (2019).

%H B. N. Cooperstein and E. E. Shult, <a href="http://www.emis.de/journals/AG/1-1/1_037.pdf">A note on embedding and generating dual polar spaces</a>. Adv. Geom. 1 (2001), 37-48. See Conjecture 5.5.

%H Kittitat Iamthong, Ji-Hwan Jung, and Sergey Kitaev, <a href="https://arxiv.org/abs/2009.01410">Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations</a>, arXiv:2009.01410 [math.CO], 2020.

%H D. Kremer and W. C. Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Mathematics 268 (2003), 171-183.

%H T. Mansour and A. Robertson, <a href="http://arXiv.org/abs/math.CO/0204005">Refined restricted permutations avoiding subsets of patterns of length three</a>, arXiv:math/0204005 [math.CO], 2002.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-4).

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

%F From _Henry Bottomley_, Aug 29 2000: (Start)

%F a(n) = (4^n+2)/3 = 4*a(n-1) - 2.

%F a(n) = 5*a(n-1) - 4*a(n-2).

%F a(n) = 2*A007583(n-1) = A002450(n) + 1. (End)

%F a(n) = T(1,n), array T given by A047848.

%F With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - _Paul Barry_, Aug 26 2003

%F a(n) = A007583(n) - A002450(n) = A001045(2n+1) - A001045(2n) . - _Philippe Deléham_, Feb 25 2004

%F 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

%F G.f.: (1-3*x)/((1-x)*(1-4*x)). - _Herbert Kociemba_, Jun 06 2004

%F a(n) = Sum_{k=0..n} 2^k*A121314(n,k). - _Philippe Deléham_, Sep 15 2006

%F a(n) = (A001045(2n+1)+1)/2. - _Paul Barry_, Dec 05 2007

%F From _Bruno Berselli_, Jul 27 2010: (Start)

%F a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2.

%F Sum_{i=0..n} a(i) = A073724(n). (End)

%F 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

%F a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - _Oboifeng Dira_, May 29 2020

%F From _Elmo R. Oliveira_, Dec 21 2023: (Start)

%F E.g.f.: (exp(x)*(exp(3*x) + 2))/3.

%F a(n) = A178789(n+1)/3. (End)

%e 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

%t (4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* _Harvey P. Dale_, Nov 27 2015 *)

%o (PARI) a(n)=(4^n+2)/3;

%o (Magma) [(4^n+2)/3: n in [0..30]]; // _Vincenzo Librandi_, Dec 07 2015

%Y Cf. A000302, A001045, A002450, A007583, A024493, A047848, A078008, A121314, A131708, A178789, A199571.

%Y Cf. A014916, A073724, A020988, A039301. - _Bruno Berselli_, Jul 27 2010

%K nonn,easy,walk

%O 0,2

%A _Clark Kimberling_

%E New name from _Charles R Greathouse IV_, Dec 22 2011