A003947 -id:A003947 - cp's OEIS frontend

A003945 Expansion of g.f. (1+x)/(1-2*x).

1, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472, 6442450944, 12884901888

Offset: 0

N. J. A. Sloane

Coordination sequence for infinite tree with valency 3.
Number of Hamiltonian cycles in K_3 X P_n.
Number of ternary words of length n avoiding aa, bb, cc.
For n > 0, row sums of A029635. - Paul Barry, Jan 30 2005
Binomial transform is {1, 4, 13, 40, 121, 364, ...}, see A003462. - Philippe Deléham, Jul 23 2005
Convolved with the Jacobsthal sequence A001045 = A001786: (1, 4, 12, 32, 80, ...). - Gary W. Adamson, May 23 2009
Equals (n+1)-th row sums of triangle A161175. - Gary W. Adamson, Jun 05 2009
a(n) written in base 2: a(0) = 1, a(n) for n >= 1: 11, 110, 11000, 110000, ..., i.e.: 2 times 1, (n-1) times 0 (see A003953(n)). - Jaroslav Krizek, Aug 17 2009
INVERTi transform of A003688. - Gary W. Adamson, Aug 05 2010
An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 42, 138, 162 and 168, lead to this sequence. For the corner squares these vectors lead to the companion sequence A083329. - Johannes W. Meijer, Aug 15 2010
A216022(a(n)) != 2 and A216059(a(n)) != 3. - Reinhard Zumkeller, Sep 01 2012
Number of length-n strings of 3 letters with no two adjacent letters identical. The general case (strings of r letters) is the sequence with g.f. (1+x)/(1-(r-1)*x). - Joerg Arndt, Oct 11 2012
Sums of pairs of rows of Pascal's triangle A007318, T(2n,k)+T(2n+1,k); Sum_{n>=1} A000290(n)/a(n) = 4. - John Molokach, Sep 26 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Yasemin Alp and E. Gokcen Kocer, Exponential Almost-Riordan Arrays, Results Math. (2024) Vol. 79, 173.
F. Faase, Counting Hamiltonian cycles in product graphs
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 151
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 304
Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012
C. Richard and U. Grimm, On the entropy and letter frequencies of ternary squarefree words, arXiv:math/0302302 [math.CO], 2003.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (2).
Index entries for sequences related to trees

Essentially same as A007283 (3*2^n) and A042950.
Cf. A001787, A001045, A161175.
Generating functions of the form (1+x)/(1-k*x) for k=1 to 12: A040000, A003945, A003946, A003947, A003948, A003949, A003950, A003951, A003952.
Generating functions of the form (1+x)/(1-k*x) for k=13 to 30: A170732, A170733, A170734, A170735, A170736, A170737, A170738, A170739, A170740, A170741, A170742, A170743, A170744, A170745, A170746, A170747, A170748.
Generating functions of the form (1+x)/(1-k*x) for k=31 to 50: A170749, A170750, A170751, A170752, A170753, A170754, A170755, A170756, A170757, A170758, A170759, A170760, A170761, A170762, A170763, A170764, A170765, A170766, A170767, A170768, A170769.
Cf. A003688.

k := 3; if n = 0 then 1 else k*(k-1)^(n-1); fi;

Join[{1}, 3*2^Range[0, 60]] (* Vladimir Joseph Stephan Orlovsky, Jun 09 2011 *)
Table[2^n+Floor[2^(n-1)], {n,0,30}] (* Martin Grymel, Oct 17 2012 *)
CoefficientList[Series[(1+x)/(1-2x),{x,0,40}],x] (* or *) LinearRecurrence[ {2},{1,3},40] (* Harvey P. Dale, May 04 2017 *)

a(n)=if(n,3<Charles R Greathouse IV, Jan 12 2012

a(0) = 1; for n > 0, a(n) = 3*2^(n-1).
a(n) = 2*a(n-1), n > 1; a(0)=1, a(1)=3.
More generally, the g.f. (1+x)/(1-k*x) produces the sequence [1, 1 + k, (1 + k)*k, (1 + k)*k^2, ..., (1+k)*k^(n-1), ...], with a(0) = 1, a(n) = (1+k)*k^(n-1) for n >= 1. Also a(n+1) = k*a(n) for n >= 1. - Zak Seidov and N. J. A. Sloane, Dec 05 2009
The g.f. (1+x)/(1-k*x) produces the sequence with closed form (in PARI notation) a(n)=(n>=0)*k^n+(n>=1)*k^(n-1). - Jaume Oliver Lafont, Dec 05 2009
Binomial transform of A000034. a(n) = (3*2^n - 0^n)/2. - Paul Barry, Apr 29 2003
a(n) = Sum_{k=0..n} (n+k)*binomial(n, k)/n. - Paul Barry, Jan 30 2005
a(n) = Sum_{k=0..n} A029653(n, k)*x^k for x = 1. - Philippe Deléham, Jul 10 2005
Binomial transform of A000034. Hankel transform is {1,-3,0,0,0,...}. - Paul Barry, Aug 29 2006
a(0) = 1, a(n) = 2 + Sum_{k=0..n-1} a(k) for n >= 1. - Joerg Arndt, Aug 15 2012
a(n) = 2^n + floor(2^(n-1)). - Martin Grymel, Oct 17 2012
E.g.f.: (3*exp(2*x) - 1)/2. - Stefano Spezia, Jan 31 2023

Edited by N. J. A. Sloane, Dec 04 2009

A003463 a(n) = (5^n - 1)/4.

Original entry on oeis.org

0, 1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031, 61035156, 305175781, 1525878906, 7629394531, 38146972656, 190734863281, 953674316406, 4768371582031, 23841857910156, 119209289550781, 596046447753906, 2980232238769531

Offset: 0

N. J. A. Sloane

5^a(n) is the highest power of 5 dividing (5^n)!. - Benoit Cloitre, Feb 04 2002
n such that A002294(n) is not divisible by 5. - Benoit Cloitre, Jan 14 2003
Without leading zero, i.e., sequence {a(n+1) = (5*5^n-1)/4}, this is the binomial transform of A003947. - Paul Barry, May 19 2003 [Edited by M. F. Hasler, Oct 31 2014]
Numbers n such that a(n) is prime are listed in A004061(n) = {3, 7, 11, 13, 47, 127, 149, 181, 619, 929, ...}. Corresponding primes a(n) are listed in A086122(n) = {31, 19531, 12207031, 305175781, 177635683940025046467781066894531, ...}. 3^(m+1) divides a(2*3^m*k). 31 divides a(3k). 13 divides a(4k). 11 divides a(5k). 71 divides a(5k). 7 divides a(6k). 19531 divides a(7k). 313 divides a(8k). 19 divides a(9k). 829 divides a(9k). 71 divides a(10k). 521 divides a(10k). 17 divides a(16k). p divides a(p-1) for all prime p except p = {2,5}. p^(m+1) divides a(p^m*(p-1)) for all prime p except p = {2,5}. p divides a((p-1)/2) for prime p = {11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, ...} = A045468, Primes congruent to {1, 4} mod 5. p divides a((p-1)/3) for prime p = {13, 67, 127, 163, 181, 199, 211, 241, 313, 337, 367, 379, 409, 457, ...}. p divides a((p-1)/4) for prime p = {101, 109, 149, 181, 269, 389, 401, 409, 449, 461, 521, 541, ...} = A107219, Primes of the form x^2+100y^2. p divides a((p-1)/5) for prime p = {31, 191, 251, 271, 601, 641, 761, 1091, 1861, ...}. p divides a((p-1)/6) for prime p = {181, 199, 211, 241, 379, 409, 631, 691, 739, 769, 1039, ...}. - Alexander Adamchuk, Jan 23 2007
Starting with 1 = convolution square of A026375: (1, 3, 11, 45, 195, 873, ...). - Gary W. Adamson, May 17 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=5, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det(A). - Milan Janjic, Jan 27 2010
This is the sequence A(0,1;4,5;2) = A(0,1;6,-5;0) of the family of sequences [a,b:c,d:k] considered by Gary Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
It is the Lucas sequence U(6,5). - Felix P. Muga II, Mar 21 2014
a(2*n+1) is the sum of the numerators and denominators of the reduced fractions 0 < b/5^n < 1 plus 1, with b < 5^n. - J. M. Bergot, Jul 24 2015
The sequence multiplied by 10 (0, 10, 60, 310, 1560, ...) is the maximum number of coins which can be decided by n weighings on 2 balances in the counterfeit coin problem with undecided under/overweight. [Halbeisen and Hungerbuhler, Disc. Math. 147 (1995) 139 Theorem 1]. - R. J. Mathar, Sep 10 2015
Order of the rank-n projective geometry PG(n-1,5) over the finite field GF(5). - Anthony Hernandez, Oct 05 2016
Number of zeros in the substitution system {0 -> 11100, 1 -> 11110} at step n from initial string "1" (1 -> 11110 -> 1111011110111101111011100 -> ...). - Ilya Gutkovskiy, Apr 10 2017
a(n) is the numerator of Sum_{k=1..n} 1/5^k, which approaches a limit of 1/4. The denominators are 5^n. In general, Sum_{k=1..n} 1/x^k approaches a limit of 1/(x-1). It is of interest to note that as x increases, so does the rate of convergence. See Crossrefs for numerators for other values of x which have the general form (x^n-1)/(x-1). - Gary Detlefs, Aug 31 2021

			Base 5...........decimal
0......................0
1......................1
11.....................6
111...................31
1111.................156
11111................781
111111..............3906
1111111............19531
11111111...........97656
111111111.........488281
1111111111.......2441406
etc. ...............etc.
- _Zerinvary Lajos_, Jan 14 2007

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 282.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Joseph E. Bonin and Joseph P. S. Kung The Number of Points In A Combinatorial Geometry With No 8-Point-Line Minors, Mathematical Essays in Honor of Gian-Carlo Rota, B. Sagan and R. P. Stanley, eds., Birkhäuser, 1998, 271-284.
Carlos M. da Fonseca and Anthony G. Shannon, A formal operator involving Fermatian numbers, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 491-498.
Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 374
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (6,-5).

Cf. A004061, A026375, A045468, A060458, A074479, A086122, A107219.

Cf. A003462, A002450, A003464, A023000, A023001, A002452, A002275.

[(5^n-1)/4 : n in [0..30]]; // Wesley Ivan Hurt, Sep 25 2014

a:=n->sum(5^(n-j),j=1..n): seq(a(n), n=0..23); # Zerinvary Lajos, Jan 04 2007
A003463:=1/(5*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation
a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=6*a[n-1]-5*a[n-2]od: seq(a[n], n=0..23); # Zerinvary Lajos, Feb 21 2008

lst={}; Do[p=(5^n-1)/4; AppendTo[lst, p], {n, 0, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Sep 29 2008 *)
Table[((5^n-1)/4),{n,0,25}] (* Vincenzo Librandi, Aug 20 2012 *)
NestList[5 # + 1 &, 0, 23] (* Bruno Berselli, Feb 06 2013 *)
LinearRecurrence[{6,-5},{0,1},30] (* Harvey P. Dale, Sep 20 2023 *)

A003463(n):=floor((5^n-1)/4)$ makelist(A003463(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

a(n)=5^n\4; \\ Charles R Greathouse IV, Jul 15 2011

[lucas_number1(n,6,5) for n in range(0, 24)] # Zerinvary Lajos, Apr 22 2009

[gaussian_binomial(n,1,5) for n in range(0,24)] # Zerinvary Lajos, May 28 2009

Second binomial transform of A015518; binomial transform of A000302 (preceded by 0). - Paul Barry, Mar 28 2003
a(n) = Sum_{k=1..n} binomial(n,k)*4^(k-1). - Paul Barry, Mar 28 2003
a(n) = (-1)^n times the (i, j)-th element of M^n (for all i and j such that i is not equal to j), 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) = A125118(n,4) for n>3. - Reinhard Zumkeller, Nov 21 2006
a(n) = ((3+sqrt(4))^n - (3-sqrt(4))^n)/4. - Al Hakanson (hawkuu(AT)gmail.com), Dec 31 2008
a(n) = 6*a(n-1) - 5*a(n-2) n>1, a(0)=0, a(1)=1. - Philippe Deléham, Jan 01 2009
From Wolfdieter Lang, Oct 18 2010: (Start)
O.g.f.: x/((1-5*x)*(1-x)).
a(n) = 4*a(n-1) + 5*a(n-2) + 2, a(0)=0, a(1)=1.
a(n) = 5*a(n-1) + a(n-2) - 5*a(n-3) = 7*a(n-1) - 11*a(n-2) + 5*a(n-3), a(0)=0, a(1)=1, a(2)=6. Observation by G. Detlefs. See the W. Lang comment and link. (End)
a(n) = 5*a(n-1) + 1 with n>0, a(0)=0. - Vincenzo Librandi, Nov 17 2010
a(n) = a(n-1) + A000351(n-1) n>0, a(0)=0. - Felix P. Muga II, Mar 19 2014
a(n) = a(n-1) + 20*a(n-2) + 5 for n > 1, a(0)=0, a(1)=1. - Felix P. Muga II, Mar 19 2014
a(n) = A060458(n)/2^(n+2), for n > 0. - R. J. Cano, Sep 25 2014
From Ilya Gutkovskiy, Oct 05 2016: (Start)
E.g.f.: (exp(4*x) - 1)*exp(x)/4.
Convolution of A000351 and A057427. (End)

A003948 Expansion of (1+x)/(1-5*x).

Original entry on oeis.org

1, 6, 30, 150, 750, 3750, 18750, 93750, 468750, 2343750, 11718750, 58593750, 292968750, 1464843750, 7324218750, 36621093750, 183105468750, 915527343750, 4577636718750, 22888183593750, 114440917968750, 572204589843750, 2861022949218750, 14305114746093750

Offset: 0

N. J. A. Sloane

Coordination sequence for infinite tree with valency 6.
The n-th term of the coordination sequence of the infinite tree with valency 2m is the same as the number of reduced words of size n in the free group on m generators. In the five sequences A003946, A003948, A003950, A003952, A003954, m is 2, 3, 4, 5, 6. - Avi Peretz (njk(AT)netvision.net.il), Feb 23 2001 and Ola Veshta (olaveshta(AT)my-deja.com), Mar 30 2001
Hamiltonian path in S_4 X P_2n.
For n>=1, a(n+1) is equal to the number of functions f:{1,2,...,n+1}->{1,2,3,4,5,6} such that for fixed, different x_1, x_2,...,x_n in {1,2,...,n+1} and fixed y_1, y_2,...,y_n in {1,2,3,4,5,6} we have f(x_i)<>y_i, (i=1..n). - Milan Janjic, May 10 2007
For n>=1, a(n) equals the numbers of words of length n over the alphabet {0..5} with no two adjacent letters identical.  - Milan Janjic, Jan 31 2015 [Corrected by David Nacin, May 30 2017]
a(n) equals the numbers of sequences of length n on {0,...,5} where no two adjacent terms differ by three. - David Nacin, May 30 2017
It appears that these are the only n>1 for which alpha(n)=2n, where alpha(n) is the entry point of n in the Fibonacci sequence, see A001177.  - Philippe Schnoebelen, Apr 11 2024

T. D. Noe, Table of n, a(n) for n = 0..200
F. Faase, Counting Hamiltonian cycles in product graphs
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 307
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
A. M. Nemirovsky et al., Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (5).
Index entries for sequences related to trees

Cf. A003946, A003947, A003949, A003950, A003952, A003954, A029653.

Concatenation([1], List([1..30], n-> 6*5^(n-1) )); # G. C. Greubel, Sep 24 2019

[1] cat [6*5^(n-1): n in [1..30]]; // G. C. Greubel, Sep 24 2019

k := 6; if n = 0 then 1 else k*(k-1)^(n-1); fi;

q = 6; Join[{a = 1}, Table[If[n != 0, a = q*a - a, a = q*a], {n, 0, 25}]] (* and *) Join[{1}, 6*5^Range[0, 25]] (* Vladimir Joseph Stephan Orlovsky, Jul 11 2011 *)
Join[{1},NestList[5#&,6,30]] (* Harvey P. Dale, Dec 31 2013 *)
CoefficientList[Series[(1+x)/(1-5x), {x,0,30}], x] (* Michael De Vlieger, Dec 10 2016 *)

Vec((1+x)/(1-5*x)+O(x^30)) \\ Charles R Greathouse IV, Nov 20 2012

[1]+[6*5^(n-1) for n in (1..30)] # G. C. Greubel, Sep 24 2019

G.f.: (1+x)/(1-5*x).
a(n) = Sum_{k=0..n} A029653(n, k)*x^k for x = 4. - Philippe Deléham, Jul 10 2005
The Hankel transform of this sequence is [1,-6,0,0,0,0,0,0,0,0,...]. - Philippe Deléham, Nov 21 2007
a(n) = 6*5^(n-1) for n>0, a(0)=1. - Vincenzo Librandi, Nov 18 2010
G.f.: 2/x - 5 - 8/(x*U(0)) where U(k)= 1 + 2/(3^k - 3^k/(2 + 1 - 12*x*3^k/(6*x*3^k + 1/U(k+1)))) ; (continued fraction, 4-step). - Sergei N. Gladkovskii, Oct 30 2012
E.g.f.: (6*exp(5*x) - 1)/5. - Ilya Gutkovskiy, Dec 10 2016
Sum_{n>=0} 1/a(n) = 29/24. - Bernard Schott, Oct 25 2021

Definition corrected by Frans J. Faase, Feb 07 2009

Edited by N. J. A. Sloane, Dec 04 2009

A003949 Expansion of g.f. (1+x)/(1-6*x).

Original entry on oeis.org

1, 7, 42, 252, 1512, 9072, 54432, 326592, 1959552, 11757312, 70543872, 423263232, 2539579392, 15237476352, 91424858112, 548549148672, 3291294892032, 19747769352192, 118486616113152, 710919696678912, 4265518180073472, 25593109080440832, 153558654482644992

Offset: 0

N. J. A. Sloane

Coordination sequence for infinite tree with valency 7.
For n >= 1, a(n+1) is equal to the number of functions f:{1,2,...,n+1}->{1,2,3,4,5,6,7} such that for fixed, different x_1, x_2,...,x_n in {1,2,...,n+1} and fixed y_1, y_2,...,y_n in {1,2,3,4,5,6,7} we have f(x_i)<>y_i, (i=1,2,...,n). - Milan Janjic, May 10 2007
For n >= 1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,2,3,5,6} with no two adjacent letters identical. - Milan Janjic, Jan 31 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 308
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (6).
Index entries for sequences related to trees

Cf. A003947, A003948, A003950, A003951.

k:=7;; Concatenation([1], List([1..25], n-> k*(k-1)^(n-1) )); # G. C. Greubel, Sep 24 2019

k:=7; [1] cat [k*(k-1)^(n-1): n in [1..25]]; // G. C. Greubel, Sep 24 2019

R:=PowerSeriesRing(Rationals(), 25); Coefficients(R!( (1+x)/(1-6*x))); // Marius A. Burtea, Jan 20 2020

k:=7; seq(`if`(n=0, 1, k*(k-1)^(n-1)), n = 0..25); # modified by G. C. Greubel, Sep 24 2019

q = 7; Join[{a = 1}, Table[If[n != 0, a = q*a - a, a = q*a], {n, 0, 25}]] (* or *) Join[{1}, 7*6^Range[0, 25]] (* Vladimir Joseph Stephan Orlovsky, Jul 11 2011 *)
CoefficientList[Series[(1+x)/(1-6*x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 10 2012 *)
LinearRecurrence[{6},{1,7},30] (* or *) Join[{1},NestList[6#&,7,30]] (* Harvey P. Dale, May 03 2025 *)

a(n)=if(n,7*6^(n-1),1) \\ Charles R Greathouse IV, Mar 22 2016

k=7; [1]+[k*(k-1)^(n-1) for n in (1..25)] # G. C. Greubel, Sep 24 2019

G.f.: (1+x)/(1-6*x).
a(n) = Sum_{k=0..n} A029653(n, k)*x^k for x = 5. - Philippe Deléham, Jul 10 2005
a(0)=1; for n > 0, a(n) = 7*6^(n-1). - Vincenzo Librandi, Nov 18 2010
a(0)=1, a(1)=7, a(n) = 6*a(n-1). - Vincenzo Librandi, Dec 10 2012
E.g.f.: (7*exp(6*x) - 1)/6. - G. C. Greubel, Sep 24 2019

Edited by N. J. A. Sloane, Dec 04 2009

A126473 Number of strings over a 5 symbol alphabet with adjacent symbols differing by three or less.

Original entry on oeis.org

1, 5, 23, 107, 497, 2309, 10727, 49835, 231521, 1075589, 4996919, 23214443, 107848529, 501037445, 2327695367, 10813893803, 50238661313, 233396326661, 1084301290583, 5037394142315, 23402480441009, 108722104190981, 505095858086951, 2346549744920747

Offset: 0

R. H. Hardin, Dec 27 2006

[Empirical] a(base,n) = a(base-1,n) + 7^(n-1) for base >= 3n-2; a(base,n) = a(base-1,n) + 7^(n-1)-2 when base = 3n-3.
From Johannes W. Meijer, Aug 01 2010: (Start)
The a(n) represent the number of n-move routes of a fairy chess piece starting in a given side square (m = 2, 4, 6 or 8) on a 3 X 3 chessboard. This fairy chess piece behaves like a king on the eight side and corner squares but on the central square the king goes crazy and turns into a red king, see A179596.
For the side squares the 512 red kings lead to 47 different red king sequences, see the cross-references for some examples.
The sequence above corresponds to four A[5] vectors with the decimal [binary] values 367 [1,0,1,1,0,1,1,1,1], 463 [1,1,1,0,0,1,1,1,1], 487 [1,1,1,1,0,0,1,1,1] and 493 [1,1,1,1,0,1,1,0,1]. These vectors lead for the corner squares to A179596 and for the central square to A179597.
This sequence belongs to a family of sequences with g.f. (1+x)/(1-4*x-k*x^2). Red king sequences that are members of this family are A003947 (k=0), A015448 (k=1), A123347 (k=2), A126473 (k=3; this sequence) and A086347 (k=4). Other members of this family are A000351 (k=5), A001834 (k=-1), A111567 (k=-2), A048473 (k=-3) and A053220 (k=-4)
Inverse binomial transform of A154244. (End)
Equals the INVERT transform of A055099: (1, 4, 14, 50, 178, ...). - Gary W. Adamson, Aug 14 2010
Number of one-sided n-step walks taking steps from {E, W, N, NE, NW}. - Shanzhen Gao, May 10 2011
For n>=1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,2,3,4} containing no subwords 00 and 11. - Milan Janjic, Jan 31 2015

Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Index entries for linear recurrences with constant coefficients, signature (4,3).

Cf. 5 symbol differing by two or less A126392, one or less A057960.
Cf. Red king sequences side squares [numerical value A[5]]: A086347 [495], A179598 [239], A126473 [367], A123347 [335], A179602 [95], A154964 [31], A015448 [327], A152187 [27], A003947 [325], A108981 [11], A007483 [2]. - Johannes W. Meijer, Aug 01 2010
Cf. A055099.

with(LinearAlgebra): nmax:=19; m:=2; A[5]:= [1,0,1,1,0,1,1,1,1]: A:=Matrix([[0,1,0,1,1,0,0,0,0],[1,0,1,1,1,1,0,0,0],[0,1,0,0,1,1,0,0,0],[1,1,0,0,1,0,1,1,0],A[5],[0,1,1,0,1,0,0,1,1],[0,0,0,1,1,0,0,1,0],[0,0,0,1,1,1,1,0,1],[0,0,0,0,1,1,0,1,0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax); # Johannes W. Meijer, Aug 01 2010
# second Maple program:
a:= n-> (M-> M[1,2]+M[2,2])(<<0|1>, <3|4>>^n):
seq(a(n), n=0..24);  # Alois P. Heinz, Jun 28 2021

LinearRecurrence[{4, 3}, {1, 5}, 24] (* Jean-François Alcover, Dec 10 2024 *)

a(n)=([0,1; 3,4]^n*[1;5])[1,1] \\ Charles R Greathouse IV, May 10 2016

From Johannes W. Meijer, Aug 01 2010: (Start)
G.f.: (1+x)/(1-4*x-3*x^2).
a(n) = 4*a(n-1) + 3*a(n-2) with a(0) = 1 and a(1) = 5.
a(n) = ((1+3/sqrt(7))/2)*(A)^(-n) + ((1-3/sqrt(7))/2)*(B)^(-n) with A = (-2 + sqrt(7))/3 and B = (-2-sqrt(7))/3.
Lim_{k->oo} a(n+k)/a(k) = (-1)^(n+1)*A000244(n)/(A015530(n)*sqrt(7)-A108851(n))
(End)
a(n) = A015330(n)+A015330(n+1). - R. J. Mathar, May 09 2023

Edited by Johannes W. Meijer, Aug 10 2010

A287804 Number of quinary sequences of length n such that no two consecutive terms have distance 1.

Original entry on oeis.org

1, 5, 17, 59, 205, 713, 2481, 8635, 30057, 104629, 364225, 1267923, 4413861, 15365465, 53490097, 186209299, 648230545, 2256616133, 7855718641, 27347281995, 95201200637, 331413874569, 1153716087665, 4016309864843, 13981555011321, 48672509644725

Offset: 0

David Nacin, Jun 01 2017

			For n=2 the a(2)=17=25-8 sequences contain every combination except these eight: 01,10,12,21,23,32,34,43.

Index entries for linear recurrences with constant coefficients, signature (5,-5,-1).

Cf. A040000, A003945, A083318, A078057, A003946, A126358, A003946, A055099, A003947, A015448, A126473. A287804-A287819.

LinearRecurrence[{5, -5, -1}, {1, 5, 17}, 50]

def a(n):
    if n in [0,1,2]:
        return [1,5,17][n]
    return 5*a(n-1)-5*a(n-2)-a(n-3)

a(n) = 5*a(n-1) - 5a(n-2) - a(n-3), a(0)=1, a(1)=5, a(2)=17.

G.f.: (1 - 3*x^2)/(1 - 5*x + 5*x^2 + x^3).

A287819 Number of nonary sequences of length n such that no two consecutive terms have distance 4.

Original entry on oeis.org

1, 9, 71, 561, 4433, 35031, 276827, 2187585, 17287073, 136608591, 1079529611, 8530826457, 67413620993, 532726379847, 4209793089371, 33267280400913, 262889866978817, 2077449112980255, 16416740845208075, 129730917736941417, 1025179795159015841

Offset: 0

David Nacin, Jun 02 2017

			For n=2 the a(2) = 81 - 10 = 71 sequences contain every combination except these ten: 04,40,15,51,26,62,37,73,48,84.

Index entries for linear recurrences with constant coefficients, signature (8,1,-14).

Cf. A040000, A003945, A083318, A078057, A003946, A126358, A003946, A055099, A003947, A015448, A126473. A287804-A287819.

LinearRecurrence[{8, 1, -14}, {1, 9, 71, 561}, 40]

def a(n):
    if n in [0, 1, 2, 3]:
        return [1, 9, 71, 561][n]
    return 8*a(n-1)+a(n-2)-14*a(n-3)

For n>2, a(n) = 8*a(n-1) + a(n-2) - 14*a(n-3), a(0)=1, a(1)=9, a(2)=71, a(3)=561.

G.f.: (1 + x - 2 x^2 - 2 x^3)/(1 - 8 x - x^2 + 14 x^3).

A287825 Number of sequences over the alphabet {0,1,...,9} such that no two consecutive terms have distance 1.

Original entry on oeis.org

1, 10, 82, 674, 5540, 45538, 374316, 3076828, 25291120, 207889674, 1708825732, 14046322404, 115458919774, 949057110644, 7801124426174, 64124215108032, 527092600834054, 4332631742719370, 35613662169258228, 292739611493034596, 2406281042646218328

Offset: 0

David Nacin, Jun 02 2017

Index entries for linear recurrences with constant coefficients, signature (9, -4, -21, 9, 5).

Cf. A040000, A003945, A083318, A078057, A003946, A126358, A003946, A055099, A003947, A015448, A126473. A287804-A287819. A287825-A287831.

LinearRecurrence[{9, -4, -21, 9, 5}, {1, 10, 82, 674, 5540, 45538}, 40]

def a(n):
    if n in [0, 1, 2, 3, 4, 5]:
        return [1, 10, 82, 674, 5540, 45538][n]
    return 9*a(n-1) - 4*a(n-2) - 21*a(n-3) + 9*a(n-4) + 5*a(n-5)

For n>5, a(n) = 9*a(n-1) - 4*a(n-2) - 21*a(n-3) + 9*a(n-4) + 5*a(n-5), a(0)=1, a(1)=10, a(2)=82, a(3)=674, a(4)=5540, a(5)=45538.

G.f.: (-1 - x + 4*x^2 + 3*x^3 - 3*x^4 - x^5)/(-1 + 9*x - 4*x^2 - 21*x^3 + 9*x^4 + 5*x^5).

A015449 Expansion of (1-4x)/(1-5x-x^2).

Original entry on oeis.org

1, 1, 6, 31, 161, 836, 4341, 22541, 117046, 607771, 3155901, 16387276, 85092281, 441848681, 2294335686, 11913527111, 61861971241, 321223383316, 1667978887821, 8661117822421, 44973567999926, 233528957822051

Offset: 0

Olivier Gérard

Row m=5 of A135597.
Binomial transform of A152187. - Johannes W. Meijer, Aug 01 2010
For n>=1, row sums of triangle
m/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....5
.2..|..1.....5....25
.3..|..1....10....25.....125
.4..|..1....10....75.....125....625
.5..|..1....15....75.....500....625....3125
.6..|..1....15...150.....500...3125....3125...15625
.7..|..1....20...150....1250...3125...18750...15625...78125
which is triangle for numbers 5^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012
a(n+1) is (for n>=0) the number of length-n strings of 6 letters {0,1,2,3,4,5} with no two adjacent nonzero letters identical. The general case (strings of L letters) is the sequence with g.f. (1+x)/(1-(L-1)*x-x^2). - Joerg Arndt, Oct 11 2012
With offset 1, the sequence is the INVERT transform (1, 5, 5*4, 5*4^2, 5*4^3, ...); i.e., of A003947. The sequence can also be obtained by taking powers of the matrix [(1,5); (1,4)] and extracting the upper left terms. - Gary W. Adamson, Jul 31 2016

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Joerg Arndt, Matters Computational (The Fxtbook)
Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Generalized Leonardo Number Entries, Ann. Math. Silesianae (2023). See p. 16.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Tanya Khovanova, Recursive Sequences
Index entries for linear recurrences with constant coefficients, signature (5,1).

Cf. A084057, A108306, A164549.

a:=[1,1];; for n in [3..30] do a[n]:=5*a[n-1]+a[n-2]; od; a; # G. C. Greubel, Oct 23 2019

[n le 2 select 1 else 5*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 06 2012

a[0]:=1: a[1]:=1: for n from 2 to 26 do a[n]:=5*a[n-1]+a[n-2] od: seq(a[n], n=0..21); # Zerinvary Lajos, Jul 26 2006

Transpose[NestList[Flatten[{Rest[#],ListCorrelate[{1,5},#]}]&, {1,1},40]][[1]]  (* Harvey P. Dale, Mar 23 2011 *)
LinearRecurrence[{5,1}, {1,1}, 30] (* Vincenzo Librandi, Nov 06 2012 *)
CoefficientList[Series[(1-4*x)/(1-5*x-x^2), {x,0,30}], x] (* G. C. Greubel, Dec 19 2017 *)
Sum[Fibonacci[Range[30] +k-2, 5], {k,0,1}] (* G. C. Greubel, Oct 23 2019 *)

Vec((1-4*x)/(1-5*x-x^2) +O('x^30)) \\ _G. C. Greubel, Dec 19 2017

def A015449_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-4*x)/(1-5*x-x^2)).list()
A015449_list(30) # G. C. Greubel, Oct 23 2019

a(n) = 5*a(n-1) + a(n-2).
a(n) = Sum_{k=0..n} 4^k*A055830(n,k). - Philippe Deléham, Oct 18 2006
G.f.: (1-4*x)/(1-5*x-x^2). - Philippe Deléham, Nov 20 2008
For n >= 2, a(n) = F_n(5) + F_(n+1)(5), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} C(n-i-1,i)*x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
a(n) = Sum_{k=0..n} A046854(n-1,k)*5^k. - R. J. Mathar, Feb 10 2024

A060925 a(n) = 2a(n-1) + 3a(n-2), a(0) = 1, a(1) = 4.

Original entry on oeis.org

1, 4, 11, 34, 101, 304, 911, 2734, 8201, 24604, 73811, 221434, 664301, 1992904, 5978711, 17936134, 53808401, 161425204, 484275611, 1452826834, 4358480501, 13075441504, 39226324511, 117678973534, 353036920601

Offset: 0

Wolfdieter Lang, Apr 20 2001

Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-1, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=charpoly(A,2). - Milan Janjic, Jan 26 2010

Harry J. Smith, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (2,3).

Cf. A000204, A003947, A060922.

[(5*3^n - (-1)^n)/4: n in [0..30]]; // G. C. Greubel, Apr 06 2021

A060925:= n-> (5*3^n - (-1)^n)/4; seq(A060925(n), n=0..30); # G. C. Greubel, Apr 06 2021

f[n_]:=3/(n+2);x=2;Table[x=f[x];Denominator[x],{n,0,5!}] (* Vladimir Joseph Stephan Orlovsky, Mar 11 2010 *)
LinearRecurrence[{2,3},{1,4},30] (* Harvey P. Dale, Mar 07 2014 *)

{a(n) = (5*3^n - (-1)^n)/4};
vector(30, n, a(n-1)) \\ Harry J. Smith, Jul 19 2009 \\ modified by G. C. Greubel, Apr 06 2021

[(5*3^n - (-1)^n)/4 for n in (0..30)] # G. C. Greubel, Apr 06 2021

Row sums of Lucas convolution triangle A060922.
Inverse binomial transform of A003947. - Philippe Deléham, Jul 23 2005
a(n) = Sum_{m=0..n} A060922(n, m) = Sum_{j=1..n} (a(j-1)*A000204(n-j+1)) + A000204(n+1).
a(n) = (5*3^n - (-1)^n)/4.
G.f.: (1+2*x)/(1 - 2*x - 3*x^2).
a(2n) = 3*a(2n-1) - 1; a(2n+1) = 3*a(2n) + 1. - Philippe Deléham, Jul 23 2005
Binomial transform is A003947. - Paul Barry, May 19 2003
E.g.f.: (-exp(-x) + 5*exp(3*x))/4. - G. C. Greubel, Apr 06 2021

Recurrence, now used as definition, from Philippe Deléham, Jul 23 2005

Entry revised by N. J. A. Sloane, Sep 10 2006

cp's OEIS Frontend

A003945 Expansion of g.f. (1+x)/(1-2*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003463 a(n) = (5^n - 1)/4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Sage

Sage

Formula

A003948 Expansion of (1+x)/(1-5*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A003949 Expansion of g.f. (1+x)/(1-6*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A126473 Number of strings over a 5 symbol alphabet with adjacent symbols differing by three or less.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A287804 Number of quinary sequences of length n such that no two consecutive terms have distance 1.

Views

A015449 Expansion of (1-4x)/(1-5x-x^2).

A060925 a(n) = 2a(n-1) + 3a(n-2), a(0) = 1, a(1) = 4.