A102518 -id:A102518 - cp's OEIS frontend

A001019 Powers of 9: a(n) = 9^n.

1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489, 3486784401, 31381059609, 282429536481, 2541865828329, 22876792454961, 205891132094649, 1853020188851841, 16677181699666569, 150094635296999121, 1350851717672992089, 12157665459056928801

Offset: 0

N. J. A. Sloane

Same as Pisot sequences E(1, 9), L(1, 9), P(1, 9), T(1, 9). Essentially same as Pisot sequences E(9, 81), L(9, 81), P(9, 81), T(9, 81). See A008776 for definitions of Pisot sequences.
Except for 1, the largest n-th power with n digits. - Amarnath Murthy, Feb 09 2002
The 2002 comment by Amarnath Murthy should say more precisely "n-th power with *at most* n digits": a(22) has only 21 digits etc., a(44) has only 42 digits etc. - Hagen von Eitzen, May 17 2009
1/1 + 1/9 + 1/81 + ... = 9/8. - Gary W. Adamson, Aug 29 2008
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 9-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
To be still more precise than Murthy and von Eitzen: the subsequence of the largest n-th power with n digits is a finite sequence, bounded by 9 and 109418989131512359209. It is guaranteed that 10^n has n + 1 digits in base 10, and clearly 9^n < 10^n. With a(22), the number n - log_10 a(n) crosses the 1.0 threshold, and obviously the gulf widens further after that, meaning that for n > 21, m^n can have fewer than n digits or more than n digits but not exactly n digits. - Alonso del Arte, Dec 12 2012
For n > 0, a(n) is also the number of n-digit zeroless numbers (A052382). - Stefano Spezia, Jul 07 2022
Erasing the last digit of the sum a(n) + a(n+1) brings back a(n). - Eric Angelini, Feb 05 2024

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
David Wells, The Penguin Dictionary of Curious and Interesting Integers. London: Penguin Books (1997): p. 196, entry for 109,418,989,131,512,359,209.

T. D. Noe, Table of n, a(n) for n = 0..100.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 274
Tanya Khovanova, Recursive Sequences
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 4.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Index entries for linear recurrences with constant coefficients, signature (9).

Cf. A016189, A067470.

Cf. A052382.

a001019 = (9 ^)
a001019_list = iterate (* 9) 1
-- Reinhard Zumkeller, Feb 12 2013

[9^n : n in [0..25]]; // Wesley Ivan Hurt, Sep 27 2016

A001019:=n->9^n: seq(A001019(n), n=0..25); # Wesley Ivan Hurt, Sep 27 2016

Table[9^n, {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Feb 15 2011 *)
NestList[9#&,1,20] (* Harvey P. Dale, Jul 04 2014 *)

A001019(n):=9^n$
makelist(A001019(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

a(n)=9^n \\ Charles R Greathouse IV, Sep 24 2015

a(n) = 9^n.
a(0) = 1, a(n) = 9*a(n - 1) for n > 0.
G.f.: 1/(1 - 9*x).
E.g.f.: exp(9*x).
A000005(a(n)) = A005408(n + 1). - Reinhard Zumkeller, Mar 04 2007
a(n) = 4*A211866(n)+5. - Reinhard Zumkeller, Feb 12 2013
a(n) = det(|v(i+2,j)|, 1 <= i,j <= n), where v(n,k) are central factorial numbers of the first kind with odd indices. - Mircea Merca, Apr 04 2013

A015518 a(n) = 2a(n-1) + 3a(n-2), with a(0)=0, a(1)=1.

Original entry on oeis.org

0, 1, 2, 7, 20, 61, 182, 547, 1640, 4921, 14762, 44287, 132860, 398581, 1195742, 3587227, 10761680, 32285041, 96855122, 290565367, 871696100, 2615088301, 7845264902, 23535794707, 70607384120, 211822152361, 635466457082

Offset: 0

Olivier Gérard

Number of walks of length n between any two distinct vertices of the complete graph K_4. - Paul Barry and Emeric Deutsch, Apr 01 2004
For n >= 1, a(n) is the number of integers k, 1 <= k <= 3^(n-1), whose ternary representation ends in an even number of zeros (see A007417). - Philippe Deléham, Mar 31 2004
Form the digraph with matrix A=[0,1,1,1;1,0,1,1;1,1,0,1;1,0,1,1]. A015518(n) corresponds to the (1,3) term of A^n. - Paul Barry, Oct 02 2004
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the denominators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is 2. - Cino Hilliard, Sep 25 2005
(A046717(n))^2 + (2*a(n))^2 = A046717(2n). E.g., A046717(3) = 13, 2*a(3) = 14, A046717(6) = 365. 13^2 + 14^2 = 365. - Gary W. Adamson, Jun 17 2006
For n >= 2, number of ordered partitions of n-1 into parts of sizes 1 and 2 where there are two types of 1 (singletons) and three types of 2 (twins). For example, the number of possible configurations of families of n-1 male (M) and female (F) offspring considering only single births and twins, where the birth order of M/F/pair-of-twins is considered and there are three types of twins; namely, both F, both M, or one F and one M - where birth order within a pair of twins itself is disregarded. In particular, for a(3)=7, two children could be either: (1) F, then M; (2) M, then F; (3) F,F; (4) M,M; (5) F,F twins; (6) M,M twins; or (7) M,F twins (emphasizing that birth order is irrelevant here when both/all children are the same gender and when two children are within the same pair of twins). - Rick L. Shepherd, Sep 18 2004
a(n) is prime for n = {2, 3, 5, 7, 13, 23, 43, 281, 359, ...}, where only a(2) = 2 corresponds to a prime of the form (3^k - 1)/4. All prime terms, except a(2) = 2, are the primes of the form (3^k + 1)/4. Numbers k such that (3^k + 1)/4 is prime are listed in A007658. Note that all prime terms have prime indices. Prime terms are listed in A111010. - Alexander Adamchuk, Nov 19 2006
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-2, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=charpoly(A,1). - Milan Janjic, Jan 26 2010
Select an odd size subset S from {1,2,...,n}, then select an even size subset from S. - Geoffrey Critzer, Mar 02 2010
a(n) is the number of ternary sequences of length n where the numbers of (0's, 1's) are (even, odd) respectively, and, by symmetry, the number of such sequences where those numbers are (odd, even) respectively. A122983 covers (even, even), and A081251 covers (odd, odd). - Toby Gottfried, Apr 18 2010
An elephant sequence, see A175654. For the corner squares just one A[5] vector, with decimal value 341, leads to this sequence (without the leading 0). For the central square this vector leads to the companion sequence A046717 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010
Let R be the commutative algebra resulting from adjoining the elements of the Klein four-group to the integers (equivalently, K = Z[x,y,z]/{x*y - z, y*z - x, x*z - y, x^2 - 1, y^2 - 1, z^2 - 1}). Then a(n) is equal to the coefficients of x, y, and z in the expansion of (x + y + z)^n. - Joseph E. Cooper III (easonrevant(AT)gmail.com), Nov 06 2010
Pisano period lengths:  1, 2, 2, 4, 4, 2, 6, 8, 2, 4, 10, 4, 6, 6, 4, 16, 16, 2, 18, 4, ... - R. J. Mathar, Aug 10 2012
The ratio a(n+1)/a(n) converges to 3 as n approaches infinity. - Felix P. Muga II, Mar 09 2014
This is a divisibility sequence, also the values of Chebyshev polynomials, and also the number of ways of packing a 2 X n-1 rectangle with dominoes and unit squares. - R. K. Guy, Dec 16 2016
For n>0, gcd(a(n),a(n+1))=1. - Kengbo Lu, Jul 02 2020

John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences, arXiv:1911.01687 [math.CO], 2019.
Katerina Böhmová, Cristina Dalfó, and Clemens Huemer, On cyclic Kautz digraphs, Research Report, 2015.
Garry Bowlin and Matthew G. Brin, Coloring Planar Graphs via Colored Paths in the Associahedra, arXiv preprint arXiv:1301.3984 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 12 2013
AJ Bu and Doron Zeilberger, Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas, arXiv:2305.09030 [math.CO], 2023.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Sergio Falcón, Binomial Transform of the Generalized k-Fibonacci Numbers, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.
Dale Gerdemann, Fractal generated from (2,3) recursion, YouTube Video, Dec 05 2014.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 2.
Felix Pozon Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014.
Index entries for linear recurrences with constant coefficients, signature (2,3).
Index entries for sequences related to Chebyshev polynomials.

a(n) = A080926(n-1) + 1 = (1/3)*A054878(n+1) = (1/3)*abs(A084567(n+1)).
First differences of A033113 and A039300.
Partial sums of A046717.
The following sequences (and others) belong to the same family: A000129, A001333, A002532, A002533, A002605, A015518, A015519, A026150, A046717, A063727, A083098, A083099, A083100, A084057.
Cf. A046717.
Cf. A007658, A111010.
Cf. A001045, A078008, A097073, A115341. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
Cf. A007482, A059260.

[Round(3^n/4): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011

Table[(3^n-(-1)^n)/4,{n,0,30}] (* Alexander Adamchuk, Nov 19 2006 *)

a(n):= round(3^n/4)$ /* Dimitri Papadopoulos, Nov 28 2023 */

PARI
```
a(n)=round(3^n/4)
```

for n in range(0, 20): print(int((3**n-(-1)**n)/4), end=', ') # Stefano Spezia, Nov 30 2018

Sage
```
[round(3^n/4) for n in range(0,27)]
```

G.f.: x/((1+x)*(1-3*x)).
a(n) = (3^n - (-1)^n)/4 = floor(3^n/4 + 1/2).
a(n) = 3^(n-1) - a(n-1). - Emeric Deutsch, Apr 01 2004
E.g.f.: (exp(3*x) - exp(-x))/4. Second inverse binomial transform of (5^n-1)/4, A003463. Inverse binomial transform for powers of 4, A000302 (when preceded by 0). - Paul Barry, Mar 28 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2k+1)*2^(2k). - Paul Barry, May 14 2003
a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*4^(k-1). - Paul Barry, Apr 02 2003
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*2^(n-2*k)*3^k. - Paul Barry, Jul 13 2004
a(n) = U(n-1, i/sqrt(3))(-i*sqrt(3))^(n-1), i^2=-1. - Paul Barry, Nov 17 2003
G.f.: x*(1+x)^2/(1 - 6*x^2 - 8*x^3 - 3*x^4) = x(1+x)^2/characteristic polynomial(x^4*adj(K_4)(1/x)). - Paul Barry, Feb 03 2004
a(n) = sum_{k=0..3^(n-1)} A014578(k) = -(-1)^n*A014983(n) = A051068(3^(n-1)), for n > 0. - Philippe Deléham, Mar 31 2004
E.g.f.: exp(x)*sinh(2*x)/2. - Paul Barry, Oct 02 2004
a(2*n+1) = A054880(n) + 1. - M. F. Hasler, Mar 20 2008
2*a(n) + (-1)^n = A046717(n). - M. F. Hasler, Mar 20 2008
a(n) = ((1+sqrt(4))^n - (1-sqrt(4))^n)/4. - Al Hakanson (hawkuu(AT)gmail.com), Dec 31 2008
a(n) = abs(A014983(n)). - Zerinvary Lajos, May 28 2009
a(n) = round(3^n/4). - Mircea Merca, Dec 28 2010
a(n) = Sum_{k=1,3,5,...} binomial(n,k)*2^(k-1). - Geoffrey Critzer, Mar 02 2010
From Sergei N. Gladkovskii, Jul 19 2012: (Start)
G.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + 1/G(k+1)))))); (continued fraction).
E.g.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - (2*k+1)/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + (2*k+2)/G(k+1)))))); (continued fraction).  (End)
G.f.: G(0)*x/(2*(1-x)), where G(k) = 1 + 1/(1 - x*(4*k-1)/(x*(4*k+3) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
a(n+1) = Sum_{k = 0..n} A238801(n,k)*2^k. - Philippe Deléham, Mar 07 2014
a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-4)^k = (-1)^(n-1)*Sum_{k=0..n-1} (-3)^k. Equals (-1)^(n-1)*Phi(n,-3), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - Tom Copeland, Apr 14 2014
a(n) = 2*A006342(n-1) - n mod 2 if n > 0, a(0)=0. - Yuchun Ji, Nov 30 2018
a(n) = 2*A033113(n-2) + n mod 2 if n > 0, a(0)=0. - Yuchun Ji, Aug 16 2019
a(2*k) = 2*A002452(k), a(2*k+1) = A066443(k). - Yuchun Ji, Aug 14 2019
a(n+1) = 2*Sum_{k=0..n} a(k) if n odd, and 1 + 2*Sum_{k=0..n} a(k) if n even. - Kengbo Lu, May 30 2020
a(n) = F(n) + Sum_{k=1..(n-1)} a(k)*L(n-k), for F(n) and L(n) the Fibonacci and Lucas numbers. - Kengbo Lu and Greg Dresden, Jun 05 2020
From Kengbo Lu, Jun 11 2020: (Start)
a(n) = A002605(n) + Sum_{k = 1..n-2} a(k)*A002605(n-k-1).
a(n) = A006130(n-1) + Sum_{k = 1..n-1} a(k)*A006130(n-k-1). (End)
a(2n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)* 2^(2n-2i-2j-1)* 3^(i+j). - Kengbo Lu, Jul 02 2020
a(n) = 3*a(n-1) - (-1)^n. - Dimitri Papadopoulos, Nov 28 2023
G.f.: x/((1 + x)*(1 - 3*x)) = Sum_{n >= 0} x^(n+1) * Product_{k = 1..n} (k + 3*x + 1)(1 + k*x) (a telescoping series). Cf. A007482. - Peter Bala, May 08 2024
From Peter Bala, Jun 29 2025: (Start)
For n >= 1, a(n+1) = 2^n * hypergeom([1/2 - (1/2)*n, -(1/2)*n], [-n], -3).
G.f. A(x) = x*exp(Sum_{n >= 1} a(2*n)/a(n)*x^n/n) =  x + 2*x^2 + 7*x^3 + 20*x^4 + ....
sqrt(A(x)/x) is the g.f. of A002426.
The following series telescope:
Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)) = -1; Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)*a(n+2)*a(n+3)) = -1/98.
In general, for k >= 0, Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)*...*a(n+2*k+1)) = -1/((a(1)*a(2)*...*a(2*k+1))*a(2*k+1)).
Sum_{n >= 1} 3^n/(a(n)*a(n+1)*a(n+2)) = 1/4; Sum_{n >= 1} 3^n/(a(n)*a(n+1)*a(n+2)* a(n+3)*a(n+4)) = 1/5600.
In general, for k >= 1, Sum_{n >= 1} 3^n/(a(n)*a(n+1)*...*a(n+2*k)) = 1/((a(1)*a(2)*...*a(2*k))*a(2*k)). (End)

More terms from Emeric Deutsch, Apr 01 2004

Edited by Ralf Stephan, Aug 30 2004

A003683 a(n) = 2^(n-1)*(2^n - (-1)^n)/3.

Original entry on oeis.org

0, 1, 2, 12, 40, 176, 672, 2752, 10880, 43776, 174592, 699392, 2795520, 11186176, 44736512, 178962432, 715816960, 2863333376, 11453202432, 45813071872, 183251763200, 733008101376, 2932030308352, 11728125427712

Offset: 0

N. J. A. Sloane

a(n) = A001045(n) * A011782(n). - Paul Barry, May 20 2003
The sequence 1,2,12,... is the binomial transform of (1, 1, 9, 9, 81, 81, ...) = 2*3^n/3 + (-3)^n/3. - Paul Barry, Jul 17 2003
Form a graph whose adjacency matrix is the tensor product of that of C_3 and [1,1;1,1]. a(n) counts walks of length n between any pair of adjacent nodes. A054881(n) counts closed walks of length n at a node.
Arises in connection with merit factor of the GRS sequences - see Hoeholdt et al.
2*a(n) = the constant term of the reduction by x^2->x+2 of the polynomial p(n,x) = ((x+d)^n-(x-d)^n)/(2d), where d=sqrt(x+2); see A192382.  For an introduction to reductions of polynomials by substitutions such as x^2->x+2, see A192232. - Clark Kimberling, Jun 30 2011
Apparently a(n+1) is the number of 3D tilings of a 2 X 2 X n room with bricks of 1 X 2 X 2 shape. - R. J. Mathar, Dec 06 2013
The ratio a(n+1)/a(n) converges to 4 as n approaches infinity. - Felix P. Muga II, Mar 10 2014

M. Gardner, Riddles of the Sphinx, New Mathematical Library, M.A.A., 1987, p. 145. Math. Rev. 89i:00015.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
T. Hoeholdt, H. E. Jensen, and J. Justesen, Aperiodic correlations and the merit factor of a class of binary sequences, IEEE Trans. Inform. Theory, 13 (1985), 549-552
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 7.
F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014; Preprint on ResearchGate.
Eric Weisstein's World of Mathematics, Octahedral Graph
Index entries for linear recurrences with constant coefficients, signature (2,8).

Cf. A001045, A003674, A011782, A054881, A192232, A192382, A238801.

[2^(n-1)*(2^n - (-1)^n)/3: n in [0..30]]; // Vincenzo Librandi, Aug 19 2011

A003683:=n->2^(n-1)*(2^n - (-1)^n)/3; seq(A003683(n), n=0..50); # Wesley Ivan Hurt, Dec 06 2013

Table[2^(n-1) (2^n-(-1)^n)/3,{n,0,30}] (* or *) LinearRecurrence[{2,8},{0,1},30] (* Harvey P. Dale, Sep 15 2013 *)

PARI
```
a(n)=if(n<0,0,2^(n-1)*(2^n-(-1)^n)/3)
```

a(n)=(2^n-(-1)^n)<<(n-1)/3 \\ Charles R Greathouse IV, Apr 17 2012

[lucas_number1(n,2,-8) for n in range(0, 24)] # Zerinvary Lajos, Apr 22 2009

a(n) = A003674(n)/3.
a(n) = 2*a(n-1) + 8*a(n-2), with a(0)=0, a(1)=1. - Barry E. Williams, Jan 04 2000
G.f.: x/((1+2*x)*(1-4*x)).
a(n) = ((1+3)^n-(1-3)^n)/6. - Paul Barry, May 14 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k+1)*9^k. - Paul Barry, May 20 2003
E.g.f.: exp(x)*sinh(3*x)/3. - Paul Barry, Jul 09 2003
a(n+1) = 2^n*A001045(n+1). - R. J. Mathar, Jul 08 2009
a(n+1) = Sum_{k=0..n} A238801(n,k)*3^k. - Philippe Deléham, Mar 07 2014

Erroneous references to spanning trees in K_2 X P_n deleted by Frans Faase, Feb 07 2009

A013708 a(n) = 3^(2*n+1).

Original entry on oeis.org

3, 27, 243, 2187, 19683, 177147, 1594323, 14348907, 129140163, 1162261467, 10460353203, 94143178827, 847288609443, 7625597484987, 68630377364883, 617673396283947, 5559060566555523, 50031545098999707, 450283905890997363, 4052555153018976267, 36472996377170786403

Offset: 0

N. J. A. Sloane

1/3 + 1/27 + 1/243 + ... = 3/8. - Gary W. Adamson, Aug 29 2008

Number k such that if a=k, b=8*k, c=15*k, d=36*k*sqrt(3*k), then a^3 + b^3 + c^3 = d^2; e.g.: a=3, b=24, c=45, d=324, 3^3 + 24^3 + 45^3 = 324^2. - Vincenzo Librandi, Nov 20 2010

Delbert L. Johnson, Table of n, a(n) for n = 0..1047
Tanya Khovanova, Recursive Sequences.
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 4.
Index entries for linear recurrences with constant coefficients, signature (9).

Cf. A000244.

NestList[9#&,3,20] (* Harvey P. Dale, Apr 21 2014 *)

a(n)=3^(2*n+1) \\ Charles R Greathouse IV, Aug 05 2015

print([3**(2*n+1) for n in range(18)]) # Michael S. Branicky, Mar 27 2021

From Philippe Deléham, Nov 23 2008: (Start)
a(n) = 9*a(n-1), n > 0; a(0)=3.
G.f.: 3/(1-9*x). (End)
a(n) = A000244(2*n+1). - R. J. Mathar, Jul 10 2015
E.g.f.: 3*exp(9*x). - Stefano Spezia, Jul 09 2024

A054878 Number of closed walks of length n along the edges of a tetrahedron based at a vertex.

Original entry on oeis.org

1, 0, 3, 6, 21, 60, 183, 546, 1641, 4920, 14763, 44286, 132861, 398580, 1195743, 3587226, 10761681, 32285040, 96855123, 290565366, 871696101, 2615088300, 7845264903, 23535794706, 70607384121, 211822152360, 635466457083

Offset: 0

Paolo Dominici (pl.dm(AT)libero.it), May 23 2000

Number of closed walks of length n at a vertex of C_4, the cyclic graph on 4 nodes. 3*A015518(n) + a(n) = 3^n. - Paul Barry, Feb 03 2004
Form the digraph with matrix A = [0,1,1,1; 1,0,1,1; 1,1,0,1; 1,0,1,1]; a(n) corresponds to the (1,1) term of A^n. - Paul Barry, Oct 02 2004
Absolute values of A084567 (compare generating functions).
For n > 1, 4*a(n)=A218034(n)= the trace of the n-th power of the adjacency matrix for a complete 4-graph, a 4 X 4 matrix with a null diagonal and all ones for off-diagonal elements. The diagonal elements for the n-th power are a(n) and the off-diagonal are a(n)+1 for an odd power and a(n)-1 for an even (cf. A001045). - Tom Copeland, Nov 06 2012

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
R. J. Mathar, Counting Walks on Finite Graphs, (Nov 2020), Section 2.
Index entries for linear recurrences with constant coefficients, signature (2,3).

Row n=4 of A109502. A084567 (signed version).
{a(n)/3} for n>0 is A015518, non-closed walks.
Cf. A001045, A078008, A097073, A115341, A015518 (sequences where a(n)=3^n-a(n-1)). - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

[(3^n+(-1)^n*3)/4: n in [0..35]]; // Vincenzo Librandi, Jun 30 2011

A054878:=n->(3^n + (-1)^n*3)/4: seq(A054878(n), n=0..50); # Wesley Ivan Hurt, Sep 16 2017

Table[(3^n + (-1)^n*3)/4, {n, 0, 26}] (* or *)
CoefficientList[Series[1/4*(3/(1 + x) + 1/(1 - 3 x)), {x, 0, 26}], x] (* Michael De Vlieger, Sep 15 2017 *)

a(n) = (3^n + 3*(-1)^n)/4; \\ Altug Alkan, Sep 17 2017

a(n) = (3^n + (-1)^n*3)/4.
G.f.: 1/4*(3/(1+x) + 1/(1-3*x)).
E.g.f.: (exp(3*x) + 3*exp(-x))/4. - Paul Barry, Apr 20 2003
a(n) = 3^n - a(n-1) with a(0)=0. - Labos Elemer, Apr 26 2003
G.f.: (1 - 3*x^2 - 2*x^3)/(1 - 6*x^2 - 8*x^3 - 3*x^4) = (1 - 3*x^2 - 2*x^3)/charpoly(adj(C_4)). - Paul Barry, Feb 03 2004
From Paul Barry, Oct 02 2004: (Start)
G.f.: (1-2*x)/(1 - 2*x - 3*x^2).
a(n) = 2*a(n-1) + 3*a(n-2). (End)
G.f.: 1 - x + x/Q(0), where Q(k) = 1 + 3*x^2 - (3*k+4)*x + x*(3*k+1 - 3*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013
a(n+m) = a(n)*a(m) + a(n+1)*a(m+1)/3. - Yuchun Ji, Sep 12 2017
a(n) = 3*a(n-1) + 3*(-1)^n. - Yuchun Ji, Sep 13 2017
From Peter Bala, May 28 2024: (Start)
a(n) = (-1)^n + Sum_{k = 1..n} (-1)^(n-k)*binomial(n, k)*4^(k-1).
G.f.: A(x) = 1/(1 - x^2) o 1/(1 - x^2), where o denotes the black diamond product of power series as defined by Dukes and White. Cf. A015575.
The black diamond product A(x) o A(x) is the g.f. for the number of closed walks of length n at a vertex along the edges of the 15-simplex. (End)

A066443 Number of distinct paths of length 2n+1 along edges of a unit cube between two fixed adjacent vertices.

Original entry on oeis.org

1, 7, 61, 547, 4921, 44287, 398581, 3587227, 32285041, 290565367, 2615088301, 23535794707, 211822152361, 1906399371247, 17157594341221, 154418349070987, 1389765141638881, 12507886274749927, 112570976472749341

Offset: 0

John W. Layman, Aug 12 2002

All members of sequence are also hex, or central hexagonal, numbers (A003215). (If n is a hex number, 9n - 2 is always a hex number; see recurrence.) - Matthew Vandermast, Mar 30 2003
The sequence 1,1,7,61,547,... with g.f. (1-9x+6x^2)/((1-x)(1-9x)) and a(n) = A054879(n)/3 + 2*0^n/3 gives the denominators in the probability that a random walk on the cube returns to its starting corner on the 2n-th step. - Paul Barry, Mar 11 2004
Equals row sums of even row terms of triangle A158303. - Gary W. Adamson, Mar 15 2009
It appears that a(n) is the n-th record value in A120437, which gives the  differences of A037314 (positive integers n such that the sum of the base 3 digits of n equals the sum of the base 9 digits of n). - John W. Layman, Dec 14 2010
Numbers in base 9 are 1, 6+1, 66+1, 666+1, 6666+1, 66666+1, etc.; that is, n 6's + 1. - Yuchun Ji, Aug 15 2019
All prime factors of a(n) are 1 mod 6. In addition, if n is not 1 mod 3 (first index being n=0), then 3 is a cubic residue modulo all prime factors of a(n). This provides a simple proof that there are infinitely many primes 1 mod 6 that have 3 as a cubic residue. - William Hu, Jul 26 2024

			From _Michael B. Porter_, Aug 22 2016: (Start)
Give coordinates (a,b,c) to the vertices of the cube, where a, b, and c are either 0 or 1. For n = 1, the a(1) = 7 paths of length 2n + 1 = 3 from (0,0,0) to (0,0,1) are:
(0,0,0) -> (0,0,1) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (0,0,1) -> (0,1,1) -> (0,0,1)
(0,0,0) -> (0,0,1) -> (1,0,1) -> (0,0,1)
(0,0,0) -> (0,1,0) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (0,1,0) -> (0,1,1) -> (0,0,1)
(0,0,0) -> (1,0,0) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (1,0,0) -> (1,0,1) -> (0,0,1) (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..200
G. Benkart and D. Moon, A Schur-Weyl Duality Approach to Walking on Cubes, arXiv preprint arXiv:1409.8154 [math.RT], 2014 and Ann. Combin. 20 (3) (2016) 397-417.
E. Estrada and J. A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013. - _N. J. A. Sloane_, Feb 28 2013
E. Estrada and J. A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
M. Kac, Random walk and the theory of Brownian motion, Amer. Math. Monthly, 54:369-391, 1947.
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 5.
Vladimir Pletser, Congruence conditions on the number of terms in sums of consecutive squared integers equal to squared integers, arXiv:1409.7969 [math.NT], 2014.
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (10,-9).

Cf. A158303, A037314, A120437, A083234 (binomial transform), A083233 (inverse binomial transform), A054879 (recurrent walks), A125857 (walks ending on face diagonal), A054880 (walks ending on space diagonal).

[(3^(2*n+1)+1)/4: n in [0..20]]; // Vincenzo Librandi, Jun 16 2011

seq((3^(2*n+1) + 1)/4, n=0..18); # Zerinvary Lajos, Jun 16 2007

NestList[9 # - 2 &, 1, 18] (* or *)
Table[(3^(2 n + 1) + 1)/4, {n, 0, 18}] (* or *)
CoefficientList[Series[(1 - 3 x)/((1 - x) (1 - 9 x)), {x, 0, 18}], x] (* Michael De Vlieger, Aug 22 2016 *)

a(n)=3^(2*n+1)\/4 \\ Charles R Greathouse IV, Jul 02 2013

Vec((1-3*x)/((1-x)*(1-9*x)) + O(x^50)) \\ Altug Alkan, Nov 13 2015

a(n) = (3^(2*n+1)+1)/4. - Vladeta Jovovic, Dec 22 2002
a(n) = 9*a(n-1) - 2. - Matthew Vandermast, Mar 30 2003
From Paul Barry, Apr 21 2003: (Start)
G.f.: (1-3*x)/((1-x)*(1-9*x)).
E.g.f.: (3*exp(9*x) + exp(x))/4. (End)
a(n) = (-1)^n times the (i, i)-th element of M^n (for any i), where M = ((1, 1, 1, -2), (1, 1, -2, 1), (1, -2, 1, 1), (-2, 1, 1, 1)). - Simone Severini, Nov 25 2004
a(n) = Sum_{k=0..n} binomial(2*n+1, 2*k)*4^(n-k). - Paul Barry, Jan 22 2005
a(n) = A054880(n) + 1.
a(n) = A057660(3^n). - Henry Bottomley, Nov 08 2015
a(n) = Sum_{k=0..2n} (-3)^k == 1 + Sum_{k=1..n} 2*3^(2k-1). - Bob Selcoe, Aug 21 2016
a(n) = 3^(2*n+1) * a(-1-n) for all n in Z. - Michael Somos, Jul 02 2017
a(n) = 6*A002452(n) + 1. - Yuchun Ji, Aug 15 2019

Corrected by Vladeta Jovovic, Dec 22 2002

A033113 Base-3 digits are, in order, the first n terms of the periodic sequence with initial period 1,0.

Original entry on oeis.org

1, 3, 10, 30, 91, 273, 820, 2460, 7381, 22143, 66430, 199290, 597871, 1793613, 5380840, 16142520, 48427561, 145282683, 435848050, 1307544150, 3922632451, 11767897353, 35303692060, 105911076180, 317733228541, 953199685623

Offset: 1

Clark Kimberling

Written in base 3, this yields A056830. - M. F. Hasler, Oct 05 2018

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 906
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 6.
Index entries for linear recurrences with constant coefficients, signature (3,1,-3).

Cf. A003462, A039300.

[Round(3^(n+1)/8): n in [1..30]]; // Vincenzo Librandi, Jun 25 2011

a[0]:=0: a[1]:=1: for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2]+1 od: seq(a[n], n=1..33);# Zerinvary Lajos, Dec 14 2008
g:=x*(1/(1-3*x)/(1-x))/(1+x): gser:=series(g, x=0, 43): seq(coeff(gser, x, n), n=1..30);# Zerinvary Lajos, Jan 11 2009
A033113 := proc(n) (9*3^(n-1)-(-1)^n-2)/8 ; end proc: # R. J. Mathar, Jan 08 2011

Join[{a=1,b=3},Table[c=2*b+3*a+1;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Feb 01 2011 *)
Module[{nn=30,d},d=PadRight[{},nn,{1,0}];Table[FromDigits[Take[d,n],3],{n,nn}]] (* or *) LinearRecurrence[{3,1,-3},{1,3,10},30] (* Harvey P. Dale, May 24 2014 *)

a(n)=3^n*3\8 \\ Simplified by M. F. Hasler, Oct 06 2018

A033113(n)=3^(n+1)>>3 \\ M. F. Hasler, Oct 05 2018

a(n) = A039300(n)-1.
a(n)+a(n+1) = A003462(n+1).
a(n) = 3*a(n-1) + a(n-2) -3*a(n-3). - R. J. Mathar, Jun 28 2010
From Paul Barry, Nov 12 2003: (Start)
G.f.: x/((1-x)*(1+x)*(1-3*x)).
a(n) = 2*a(n-1) + 3*a(n-2) + 1.
Partial sums of A015518. (End)
E.g.f.: (1/2)*exp(x)*(sinh(x))^2. - Paul Barry, Mar 12 2003
a(n) = Sum_{k=0..floor(n/2)} C(n+2, 2k+2)*4^k. - Paul Barry, Aug 24 2003
a(n) = Sum_{k=0..floor(n/2)} 3^(n-2*k); a(n) = Sum_{k=0..n} Sum_{j=0..k} (-1)^(j+k)*3^j. - Paul Barry, Nov 12 2003
Convolution of A000244 and A059841 (3^n and periodic{1, 0}). a(n) = Sum_{k=0..n} (1 + (-1)^(n-k))*3^k/2. - Paul Barry, Jul 19 2004
a(n) = round(3^(n+1)/8) = floor((3^(n+1)-1)/8) = ceiling((3^(n+1)-3)/8) = round((3^(n+1)-3)/8). a(n) = a(n-2) + 3^(n-1), n > 2. - Mircea Merca, Dec 27 2010
a(n) = floor((3^(n+1))/4) / 2 = A081251(n)/2, n >= 1. - Wolfdieter Lang, Apr 13 2012

A054879 Closed walks of length 2n along the edges of a cube based at a vertex.

Original entry on oeis.org

1, 3, 21, 183, 1641, 14763, 132861, 1195743, 10761681, 96855123, 871696101, 7845264903, 70607384121, 635466457083, 5719198113741, 51472783023663, 463255047212961, 4169295424916643, 37523658824249781, 337712929418248023, 3039416364764232201, 27354747282878089803, 246192725545902808221

Offset: 0

Paolo Dominici (pl.dm(AT)libero.it), May 23 2000

a(n) is the number of words of length 2n on alphabet {0,1,2} with an even number (possibly zero) of each letter. - Geoffrey Critzer, Dec 20 2012

Equivalently, the cogrowth sequence of the 8-element group C2^3. - Sean A. Irvine, Nov 04 2024

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
G. Benkart and D. Moon, A Schur-Weyl Duality Approach to Walking on Cubes, arXiv preprint arXiv:1409.8154 [math.RT], 2014 and Ann. Combin. 20 (3) (2016) 397-417
R. B. Brent, Generalizing Tuenter's Binomial Sums, J. Int. Seq. 18 (2015) # 15.3.2.
G. R. Franssens, On a number pyramid related to the binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.
Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]
Ji-Hwan Jung, Oriented Riordan graphs and their fractal property, arXiv:2009.01677 [math.CO], 2020.
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 5.
L. Reyzin, Number of closed walks on an n-cube, Mathoverflow.
Index entries for linear recurrences with constant coefficients, signature (10,-9).

Cf. A081294, A092812, A121822, A122983.

[(3^(2*n)+3)/4: n in [0..25]]; // Vincenzo Librandi, Jun 30 2011

nn = 40; Select[Range[0, nn]! CoefficientList[Series[Cosh[x]^3, {x, 0, nn}], x], # > 0 &]  (* Geoffrey Critzer, Dec 20 2012 *)
Table[(3^(2n)+3)/4,{n,0,30}] (* or *) LinearRecurrence[{10,-9},{1,3},30] (* Harvey P. Dale, Mar 17 2023 *)

a(n) = (3^(2*n)+3)/4.
G.f.: 1/4*1/(1-9*x)+3/4*1/(1-x).
a(n) = Sum_{k=0..n} 3^k*4^(n-k)*A121314(n,k). - Philippe Deléham, Aug 26 2006
E.g.f.: cosh^3(x). O.g.f.: 1/(1-3*1*x/(1-2*2*x/(1-1*3*x))) (continued fraction). - Peter Bala, Nov 13 2006
(-1)^n*a(n) = Sum_{k=0..n} A086872(n,k)*(-4)^(n-k). - Philippe Deléham, Aug 17 2007
a(n) = (1/2^3)*Sum_{j = 0..3} binomial(3,j)*(3 - 2*j)^(2*n). See Reyzin link. - Peter Bala, Jun 03 2019
a(n) = 9*a(n-1) - 6. - Klaus Purath, Mar 13 2021

cp's OEIS Frontend

A001019 Powers of 9: a(n) = 9^n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Formula

A015518 a(n) = 2*a(n-1) + 3*a(n-2), with a(0)=0, a(1)=1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Python

Sage

Formula

Extensions

A003683 a(n) = 2^(n-1)*(2^n - (-1)^n)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A013708 a(n) = 3^(2*n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A054878 Number of closed walks of length n along the edges of a tetrahedron based at a vertex.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A066443 Number of distinct paths of length 2n+1 along edges of a unit cube between two fixed adjacent vertices.

Views

Author

Keywords

A015518 a(n) = 2a(n-1) + 3a(n-2), with a(0)=0, a(1)=1.