cp's OEIS Frontend

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

%I A047849 #194 Aug 12 2025 23:19:30
%S A047849 1,2,6,22,86,342,1366,5462,21846,87382,349526,1398102,5592406,
%T A047849 22369622,89478486,357913942,1431655766,5726623062,22906492246,
%U A047849 91625968982,366503875926,1466015503702,5864062014806,23456248059222,93824992236886,375299968947542
%N A047849 a(n) = (4^n + 2)/3.
%C A047849 Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6. - _Paul Barry_, Mar 10 2004
%C A047849 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 A047849 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 A047849 Permutations with two fixed points avoiding 123 and 132.
%C A047849 Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302. - _Paul Curtz_, Mar 25 2008
%C A047849 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 A047849 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 A047849 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 A047849 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 A047849 From _Michel Lagneau_, Feb 26 2015: (Start)
%C A047849 a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.
%C A047849 Proof:
%C A047849 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 A047849    a(n) = a(n+1) + (1 + 3 + ... + 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) for n >= 2.
%C A047849 We obtain immediately: a(n) = a(1) + 4 + ... + 4^n = (4^n+2)/3. (End)
%C A047849 The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - _Peter Bala_, Aug 12 2021
%C A047849 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 04 2023
%C A047849 Also the cogrowth sequence for the 8-element dihedral group D8 = <S,T | S^4, T^2, (ST)^2>. - _Sean A. Irvine_, Nov 04 2024
%H A047849 Bruno Berselli, <a href="/A047849/b047849.txt">Table of n, a(n) for n = 0..1000</a>
%H A047849 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 A047849 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 A047849 Georgia Benkart and Tom Halverson, <a href="https://hal.archives-ouvertes.fr/hal-02173744">McKay Centralizer Algebras</a>, hal-02173744 [math.CO], 2020.
%H A047849 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 A047849 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 A047849 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 A047849 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 A047849 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 A047849 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 A047849 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 A047849 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 A047849 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 A047849 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-4).
%F A047849 n-th difference of a(n), a(n-1), ..., a(0) is 3^(n-1) for n >= 1.
%F A047849 From _Henry Bottomley_, Aug 29 2000: (Start)
%F A047849 a(n) = (4^n + 2)/3.
%F A047849 a(n) = 4*a(n-1) - 2.
%F A047849 a(n) = 5*a(n-1) - 4*a(n-2).
%F A047849 a(n) = 2*A007583(n-1) = A002450(n) + 1. (End)
%F A047849 a(n) = A047848(1,n).
%F A047849 With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - _Paul Barry_, Aug 26 2003
%F A047849 a(n) = A007583(n) - A002450(n) = A001045(2n+1) - A001045(2n) . - _Philippe Deléham_, Feb 25 2004
%F A047849 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 A047849 G.f.: (1-3*x)/((1-x)*(1-4*x)). - _Herbert Kociemba_, Jun 06 2004
%F A047849 a(n) = Sum_{k=0..n} 2^k*A121314(n,k). - _Philippe Deléham_, Sep 15 2006
%F A047849 a(n) = (A001045(2*n+1) + 1)/2. - _Paul Barry_, Dec 05 2007
%F A047849 From _Bruno Berselli_, Jul 27 2010: (Start)
%F A047849 a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2.
%F A047849 Sum_{i=0..n} a(i) = A073724(n). (End)
%F A047849 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 A047849 a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - _Oboifeng Dira_, May 29 2020
%F A047849 From _Elmo R. Oliveira_, Dec 21 2023: (Start)
%F A047849 E.g.f.: (exp(x)*(exp(3*x) + 2))/3.
%F A047849 a(n) = A178789(n+1)/3. (End)
%F A047849 a(n) = A000302(n) - A020988(n). - _John Reimer Morales_, Aug 03 2025
%e A047849 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 A047849 (4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* _Harvey P. Dale_, Nov 27 2015 *)
%o A047849 (PARI) a(n)=(4^n+2)/3;
%o A047849 (Magma) [(4^n+2)/3: n in [0..30]]; // _Vincenzo Librandi_, Dec 07 2015
%o A047849 (Python)
%o A047849 def A047849(n): return (pow(4, n) +2)//3
%o A047849 print([A047849(n) for n in range(41)]) # _G. C. Greubel_, Jan 17 2025
%o A047849 (Python) def A047849(n): return ((1 << (2 * n)) + 2) // 3 # _John Reimer Morales_, Aug 05 2025
%Y A047849 Cf. A000302, A001045, A002450, A007583, A024493, A047848, A078008, A121314, A131708, A178789, A199571.
%Y A047849 Cf. A014916, A073724, A020988, A039301.
%K A047849 nonn,easy,walk
%O A047849 0,2
%A A047849 _Clark Kimberling_
%E A047849 New name from _Charles R Greathouse IV_, Dec 22 2011