A047849 a(n) = (4^n + 2)/3.
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
Offset: 0
Examples
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
Links
- Bruno Berselli, Table of n, a(n) for n = 0..1000
- Jeffrey M. Barnes, Georgia Benkart, and Tom Halverson, McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
- Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
- Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
- Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
- Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 37-51.
- Pascal Caron, Jean-Gabriel Luque, and Bruno Patrou, A combinatorial approach for the state complexity of the Shuffle product, arXiv:1905.08120 [cs.FL], 2019.
- Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, and Seyed Ahmad Mojallal, Riordan graphs I: structural properties, Linear Algebra and its Applications, 579. pp. 89-135, Prop. 2.8. (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, and Sergey Kitaev, Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations, arXiv:2009.01410 [math.CO], 2020.
- D. Kremer and W. C. Shiu, 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).
Crossrefs
Programs
-
Magma
[(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015
-
Mathematica
(4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* Harvey P. Dale, Nov 27 2015 *) -
PARI
a(n)=(4^n+2)/3;
-
Python
def A047849(n): return (pow(4, n) +2)//3 print([A047849(n) for n in range(41)]) # G. C. Greubel, Jan 17 2025
-
Python
def A047849(n): return ((1 << (2 * n)) + 2) // 3 # John Reimer Morales, Aug 05 2025
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.
a(n) = 4*a(n-1) - 2.
a(n) = 5*a(n-1) - 4*a(n-2).
a(n) = A047848(1,n).
With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - Paul Barry, Aug 26 2003
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(2*n+1) + 1)/2. - Paul Barry, Dec 05 2007
From Bruno Berselli, Jul 27 2010: (Start)
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
From Elmo R. Oliveira, Dec 21 2023: (Start)
E.g.f.: (exp(x)*(exp(3*x) + 2))/3.
a(n) = A178789(n+1)/3. (End)
Extensions
New name from Charles R Greathouse IV, Dec 22 2011
Comments