A073724 -id:A073724 - 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

A076024 a(n) = (2^n + 4)*(2^n - 1)/6.

Original entry on oeis.org

0, 1, 4, 14, 50, 186, 714, 2794, 11050, 43946, 175274, 700074, 2798250, 11188906, 44747434, 178973354, 715860650, 2863377066, 11453377194, 45813246634, 183252462250, 733008800426, 2932033104554, 11728128223914, 46912504507050, 187650001250986, 750599971449514

Offset: 0

Britney C. Gallivan (ogallivan(AT)verizon.net), Sep 30 2002

Provides loss function for folding paper in half. It tells how much normalized paper has been lost with n folds. The sequence sets a limit on the number of times things of finite thickness can be folded in one direction.
Developed with J. R. Gallivan.
Binomial transform of A007051, with leading zero.
Second binomial transform of A078008(n-1) + 0^n/2. - Paul Barry, Apr 27 2004

			a(12) = 2798250 means that for the 12th folding of paper in half that 2798250 times as much material has been lost to potential folding as was lost on the first fold. [corrected by _Rick L. Shepherd_, May 08 2003]

Britney C. Gallivan, How to fold paper in half twelve times (an "impossible challenge" solved and explained), Historical Society of Pomona Valley, Pomona California, (2002)

Ivan Panchenko, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Folding
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A007582.

List([0..30], n-> (2^n +4)*(2^n -1)/6) # G. C. Greubel, May 04 2019

[(2^n +4)*(2^n -1)/6 : n in [0..30]]; // Wesley Ivan Hurt, Jun 12 2014

A076024:=n->(2^n + 4)*(2^n - 1)/6; seq(A076024(n), n=0..30); # Wesley Ivan Hurt, Jun 12 2014

Table[(2^n+4)*(2^n-1)/6, {n,0,30}] (* Wesley Ivan Hurt, Jun 12 2014 *)

a(n) = 1<<(2*n-1)\3 + 1<<(n-1); \\ Kevin Ryde, Nov 26 2022 [replacing previous incorrect code]

[(2^n +4)*(2^n -1)/6 for n in (0..30)] # G. C. Greubel, May 04 2019

a(n) = Sum_{k <= n} A007582(k).
G.f.: x*(1-3*x)/((1-x)*(1-2*x)*(1-4*x)).
E.g.f.: (3*exp(2*x) + exp(4*x) - 4*exp(x))/6 = (exp(2*x)*(2*cosh(x) - sinh(x)) - 2)/3.
a(n) = Sum_{k=0..n} C(n, k)*(3^(k-1) + 1 - 4*0^k/3)/2.
a(n) = Sum_{k=0..n} C(n, k+1)*(3^k + 1).
a(n) = Sum_{i < n} a(i) + A073724(n-1). - Ivan N. Ianakiev, Jun 12 2014

A160128 a(n) = number of grid points that are covered after (2^n)th stage of A139250.

Original entry on oeis.org

3, 7, 19, 63, 235, 919, 3651, 14575, 58267, 233031, 932083, 3728287, 14913099, 59652343, 238609315, 954437199, 3817748731, 15270994855, 61083979347, 244335917311, 977343669163, 3909374676567, 15637498706179

Offset: 0

Omar E. Pol, May 09 2009

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Cf. A000079, A007583, A139250, A139251, A139252, A139560, A147614.

Cf. Same recurrence: A073724, A210985, A014825.

Vec((3 - 11*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^40)) \\ Colin Barker, May 13 2020

a(n) = A147614(A000079(n)).
a(n) = (1/9)*(2^(2*n+3) + 12*n + 19). [Nathaniel Johnston, Mar 29 2011]
It appears that a(n) = A139252(2^(n+1)). - Omar E. Pol, Sep 11 2012
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3). - Paul Curtz, May 07 2020
G.f.: (3 - 11*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)). - Colin Barker, May 13 2020

Terms after a(10) from Nathaniel Johnston, Mar 29 2011

A094195 Expansion of g.f.: (1-4x)/((1-5x)*(1-x)^2).

Original entry on oeis.org

1, 3, 10, 42, 199, 981, 4888, 24420, 122077, 610359, 3051766, 15258798, 76293955, 381469737, 1907348644, 9536743176, 47683715833, 238418579115, 1192092895522, 5960464477554, 29802322387711, 149011611938493, 745058059692400, 3725290298461932, 18626451492309589

Offset: 0

N. J. A. Sloane, Jun 01 2004

An approximation to A091843.

G. C. Greubel, Table of n, a(n) for n = 0..1000
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
Index entries for sequences related to Gijswijt's sequence
Index entries for linear recurrences with constant coefficients, signature (7,-11,5).

Cf. A047926, A073724, A090822, A091843.

A row of A094250.

[(5^(n+1) +12*n +11)/16: n in [0..40]]; // G. C. Greubel, Aug 18 2023

CoefficientList[Series[(1-4x)/((1-5x)(1-x)^2),{x,0,30}],x] (* or *) LinearRecurrence[{7,-11,5},{1,3,10},30] (* Harvey P. Dale, Dec 31 2011 *)

[(5^(n+1) +12*n +11)/16 for n in range(41)] # G. C. Greubel, Aug 18 2023

a(n) = (5^(n+1) + 12*n + 11)/16.
a(n) = 7*a(n-1) - 11*a(n-2) + 5*a(n-3), with a(0)=1, a(1)=3, a(2)=10. - Harvey P. Dale, Dec 31 2011
E.g.f.: (1/16)*(5*exp(5*x) + (11 + 12*x)*exp(x)). - G. C. Greubel, Aug 18 2023

A094250 Array, A(n, k) = ((n+2)^(k+1) + (k+1)n(n+1) - 1)/(n+1)^2, read by antidiagonals.

Original entry on oeis.org

1, 1, 3, 1, 3, 7, 1, 3, 8, 15, 1, 3, 9, 22, 31, 1, 3, 10, 31, 63, 63, 1, 3, 11, 42, 117, 185, 127, 1, 3, 12, 55, 199, 459, 550, 255, 1, 3, 13, 70, 315, 981, 1825, 1644, 511, 1, 3, 14, 87, 471, 1871, 4888, 7287, 4925, 1023, 1, 3, 15, 106, 673, 3273, 11203, 24420, 29133, 14767, 2047

Offset: 0

N. J. A. Sloane, Jun 02 2004

			Array, A(n, k), begins:
  1, 3,  7, 15,  31,   63,   127,    255,     511, ... A000225;
  1, 3,  8, 22,  63,  185,   550,   1644,    4925, ... A047926;
  1, 3,  9, 31, 117,  459,  1825,   7287,   29133, ... A073724;
  1, 3, 10, 42, 199,  981,  4888,  24420,  122077, ... A094195;
  1, 3, 11, 55, 315, 1871, 11203,  67191,  403115, ... A094259;
  1, 3, 12, 70, 471, 3273, 22882, 160140, 1120941, ...
Antidiagonals, T(n, k), begins as:
  1;
  1, 3;
  1, 3,  7;
  1, 3,  8, 15;
  1, 3,  9, 22,  31;
  1, 3, 10, 31,  63,   63;
  1, 3, 11, 42, 117,  185,  127;
  1, 3, 12, 55, 199,  459,  550,  255;
  1, 3, 13, 70, 315,  981, 1825, 1644,  511;
  1, 3, 14, 87, 471, 1871, 4888, 7287, 4925, 1023;

G. C. Greubel, Antidiagonals n = 0..50, flattened

Rows are A000225, A047926, A073724, A094195, A094259.

A094250:= func< n,k | ((n-k+2)^(k+1) + (k+1)*(n-k)*(n-k+1) - 1)/(n-k+1)^2 >;
[A094250(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Aug 18 2023

A094250[n_, k_]:= ((n-k+2)^(k+1) + (k+1)*(n-k)*(n-k+1) - 1)/(n-k+1)^2;
Table[A094250[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Aug 18 2023 *)

def A094250(n, k): return ((n-k+2)^(k+1) + (k+1)*(n-k)*(n-k+1) - 1)/(n-k+1)^2
flatten([[A094250(n,k) for k in range(n+1)] for n in range(16)]) # G. C. Greubel, Aug 18 2023

A(n, k) = ((n+2)^(k+1) + (k+1)*n*(n+1) - 1)/(n+1)^2 (array).
T(n, k) = ((n-k+2)^(k+1) + (k+1)*(n-k)*(n-k+1) - 1)/(n-k+1)^2 (antidiagonals).
G.f. for row n: (1-(n+1)*x)/((1-(n+2)*x)*(1-x)^2).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Python

Formula

Extensions

A076024 a(n) = (2^n + 4)*(2^n - 1)/6.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A160128 a(n) = number of grid points that are covered after (2^n)th stage of A139250.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A094195 Expansion of g.f.: (1-4*x)/((1-5*x)*(1-x)^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A094250 Array, A(n, k) = ((n+2)^(k+1) + (k+1)*n*(n+1) - 1)/(n+1)^2, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A099214 a(n)=4a(n-1)-4a(n-2)+4a(n-3).

Views

Author

Keywords

Comments

Crossrefs

Formula

A073722 Least k such that sigma(k) mod primepi(k) = n or zero if no such number exists.

Views

Author

Keywords

Examples

A094195 Expansion of g.f.: (1-4x)/((1-5x)*(1-x)^2).

A094250 Array, A(n, k) = ((n+2)^(k+1) + (k+1)n(n+1) - 1)/(n+1)^2, read by antidiagonals.