A047848 -id:A047848 - cp's OEIS frontend

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

Clark Kimberling

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 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:
   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)
The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - Peter Bala, Aug 12 2021
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
Also the cogrowth sequence for the 8-element dihedral group D8 = . - Sean A. Irvine, Nov 04 2024

			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

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).

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

Cf. A014916, A073724, A020988, A039301.

[(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015

(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;
```

def A047849(n): return (pow(4, n) +2)//3
print([A047849(n) for n in range(41)]) # G. C. Greubel, Jan 17 2025

def A047849(n): return ((1 << (2 * n)) + 2) // 3 # John Reimer Morales, Aug 05 2025

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) = 2*A007583(n-1) = A002450(n) + 1. (End)
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
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(2*n+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
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)
a(n) = A000302(n) - A020988(n). - John Reimer Morales, Aug 03 2025

New name from Charles R Greathouse IV, Dec 22 2011

A047850 a(n) = (5^n + 3)/4.

Original entry on oeis.org

1, 2, 7, 32, 157, 782, 3907, 19532, 97657, 488282, 2441407, 12207032, 61035157, 305175782, 1525878907, 7629394532, 38146972657, 190734863282, 953674316407, 4768371582032, 23841857910157, 119209289550782, 596046447753907

Offset: 0

Clark Kimberling

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-5).

Cf. A047848, A132079.

A047850:= func< n | (5^n + 3)/4 >; [A047850(n): n in [0..40]]; // G. C. Greubel, Jan 10 2025

(5^Range[0,40] +3)/4 (* G. C. Greubel, Jan 10 2025 *)

a(n)=(5^n+3)/4 \\ Charles R Greathouse IV, Oct 07 2015

def A047850(n): return (5^n+3)//4
print([A047850(n) for n in range(41)]) # G. C. Greubel, Jan 10 2025

a(n) = A047848(2,n).
From Philippe Deléham, Oct 06 2009: (Start)
a(n) = 6*a(n-1) - 5*a(n-2) for n > 1.
G.f.: (1-4*x)/((1-x)*(1-5*x)). (End)
a(n) = 5*a(n-1) - 3 (with a(0)=1). - Vincenzo Librandi, Aug 06 2010
From Elmo R. Oliveira, Dec 10 2023: (Start)
a(n) = A132079(n)/2.
E.g.f.: (1/4)*(exp(5*x) + 3*exp(x)). (End)

Better description from Michael Somos

A123490 Triangle whose k-th column satisfies a(n) = (k+3)a(n-1)-(k+2)a(n-2).

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 5, 2, 1, 16, 14, 6, 2, 1, 32, 41, 22, 7, 2, 1, 64, 122, 86, 32, 8, 2, 1, 128, 365, 342, 157, 44, 9, 2, 1, 256, 1094, 1366, 782, 260, 58, 10, 2, 1, 512, 3281, 5462, 3907, 1556, 401, 74, 11, 2, 1, 1024, 9842, 21846, 19532, 9332, 2802, 586, 92, 12, 2, 1

Offset: 0

Paul Barry, Oct 01 2006

			Triangle begins
     1;
     2,    1;
     4,    2,     1;
     8,    5,     2,     1;
    16,   14,     6,     2,    1;
    32,   41,    22,     7,    2,    1;
    64,  122,    86,    32,    8,    2,   1;
   128,  365,   342,   157,   44,    9,   2,  1;
   256, 1094,  1366,   782,  260,   58,  10,  2,  1;
   512, 3281,  5462,  3907, 1556,  401,  74, 11,  2, 1;
  1024, 9842, 21846, 19532, 9332, 2802, 586, 92, 12, 2, 1;

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Columns include A000079, A007051, A047849, A047850, A047851.

Cf. A047848, A103439 (row sums), A123491 (diagonal sums).

[((k+2)^(n-k) +k)/(k+1): k in [0..n], n in [0..12]]; // G. C. Greubel, Jun 15 2021

Table[((k+2)^(n-k) +k)/(k+1), {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Oct 14 2017 *)

for(n=0, 10, for(k=0,n, print1(((k+2)^(n-k)+k)/(k+1), ", "))) \\ G. C. Greubel, Oct 14 2017

flatten([[((k+2)^(n-k) +k)/(k+1) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Jun 15 2021

Column k has g.f.: x^k*(1-x(1+k))/((1-x)*(1-x(2+k))).
T(n,k) = ((k+2)^(n-k) + k)/(k+1), for 0 <= k <= n.
Sum_{k=0..n} T(n, k) = A103439(n+1).
Sum_{k=0..floor(n/2)} T(n-k, k) = A123491(n).

cp's OEIS Frontend

A196793 a(n) = A047848(n, n).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Python

Formula

Extensions

A047850 a(n) = (5^n + 3)/4.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

Extensions

A123490 Triangle whose k-th column satisfies a(n) = (k+3)*a(n-1)-(k+2)*a(n-2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A123490 Triangle whose k-th column satisfies a(n) = (k+3)a(n-1)-(k+2)a(n-2).