A124805 -id:A124805 - cp's OEIS frontend

A285280 Array read by antidiagonals: T(m,n) = number of m-ary words of length n with cyclically adjacent elements differing by 2 or less.

1, 3, 1, 9, 4, 1, 27, 14, 5, 1, 81, 46, 19, 6, 1, 243, 162, 65, 24, 7, 1, 729, 574, 247, 84, 29, 8, 1, 2187, 2042, 955, 332, 103, 34, 9, 1, 6561, 7270, 3733, 1336, 417, 122, 39, 10, 1, 19683, 25890, 14649, 5478, 1717, 502, 141, 44, 11, 1

Offset: 3

Andrew Howroyd, Apr 15 2017

All rows are linear recurrences with constant coefficients. See PARI script to obtain generating functions.

			Table starts (m>=3, n>=0):
1  3  9  27  81  243   729  2187 ...
1  4 14  46 162  574  2042  7270 ...
1  5 19  65 247  955  3733 14649 ...
1  6 24  84 332 1336  5478 22658 ...
1  7 29 103 417 1717  7229 30793 ...
1  8 34 122 502 2098  8980 38928 ...
1  9 39 141 587 2479 10731 47063 ...
1 10 44 160 672 2860 12482 55198 ...

Andrew Howroyd, Table of n, a(n) for n = 3..1277

Rows 3-32 are A000244, A124805, A124806, A124807, A124828, A124843, A124851, A124852, A124857, A124858, A124864, A124892-A124894, A124898, A124935, A124947, A124948-A124958, A124994, A124998.

Cf. A285266, A276562, A285281.

diff = 2; m0 = diff + 1; mmax = 12;
TransferGf[m_, u_, t_, v_, z_] := Array[u, m].LinearSolve[IdentityMatrix[m] - z*Array[t, {m, m}], Array[v, m]]
RowGf[d_, m_, z_] := 1 + z*Sum[TransferGf[m, Boole[# == k] &, Boole[Abs[#1 - #2] <= d] &, Boole[Abs[# - k] <= d] &, z], {k, 1, m}];
row[m_] := row[m] = CoefficientList[RowGf[diff, m, x] + O[x]^mmax, x];
T[m_ /; m >= m0, n_ /; n >= 0] := row[m][[n + 1]];
Table[T[m - n, n], {m, m0, mmax}, {n, m - m0, 0, -1}] // Flatten (* Jean-François Alcover, Jun 16 2017, adapted from PARI *)

TransferGf(m,u,t,v,z)=vector(m,i,u(i))*matsolve(matid(m)-z*matrix(m,m,i,j,t(i,j)),vectorv(m,i,v(i)));
RowGf(d,m,z)=1+z*sum(k=1,m,TransferGf(m, i->if(i==k,1,0), (i,j)->abs(i-j)<=d, j->if(abs(j-k)<=d,1,0), z));
for(m=3, 10, print(RowGf(2,m,x)));
for(m=3, 10, v=Vec(RowGf(2,m,x) + O(x^8)); for(n=1, length(v), print1( v[n], ", ") ); print(); );

A206776 a(n) = 3a(n-1) + 2a(n-2) for n>1, a(0)=2, a(1)=3.

Original entry on oeis.org

2, 3, 13, 45, 161, 573, 2041, 7269, 25889, 92205, 328393, 1169589, 4165553, 14835837, 52838617, 188187525, 670239809, 2387094477, 8501763049, 30279478101, 107841960401, 384084837405, 1367938433017, 4871984973861, 17351831787617, 61799465310573

Offset: 0

Bruno Berselli, Jan 10 2013

This is the Lucas sequence V(3,-2).
Inverse binomial transform of this sequence is A072265.
a(n) = A124805(n) - 1 for n>0.

			G.f. = 2 + 3*x + 13*x^2 + 45*x^3 + 161*x^4 + 573*x^5 + 2041*x^6 + 7269*x^7 + ...

Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Exercise 7.49(c), pages 379, 573.

Bruno Berselli, Table of n, a(n) for n = 0..200
Wikipedia, Lucas sequence: Specific names.
Index entries for linear recurrences with constant coefficients, signature (3,2).

Cf. A189736 (same recurrence but with initial values reversed).

Cf. A007482, A072265, A124805.

[n le 1 select n+2 else 3*Self(n)+2*Self(n-1): n in [0..25]];

A206776 := proc(n)
    option remember ;
    if n <= 1 then
        n+2 ;
    else
        3*procname(n-1)+2*procname(n-2) ;
    end if;
end proc:
seq(A206776(n),n=0..30) ; # R. J. Mathar, Feb 18 2024

RecurrenceTable[{a[n] == 3 a[n - 1] + 2 a[n - 2], a[0] == 2, a[1] == 3}, a[n], {n, 25}]
LinearRecurrence[{3,2},{2,3},30] (* Harvey P. Dale, Apr 29 2014 *)
a[ n_] := If[ n < 0, (-2)^n a[ -n], ((3 + Sqrt[17])/2)^n + ((3 - Sqrt[17])/2)^n // Expand]; (* Michael Somos, Oct 13 2016 *)
a[ n_] := If[ n < 0, (-2)^n a[ -n], Boole[n == 0] + SeriesCoefficient[ ((1 + 3*x + Sqrt[1 + 6*x + 17*x^2])/2)^n, {x, 0, n}]]; (* Michael Somos, Oct 13 2016 *)

a[0]:2$ a[1]:3$ a[n]:=3*a[n-1]+2*a[n-2]$ makelist(a[n], n, 0, 25);

Vec((2-3*x)/(1-3*x-2*x^2) + O(x^30)) \\ Michel Marcus, Jun 26 2015

{a(n) = 2 * real(( (3 + quadgen(68)) / 2 )^n)}; /* Michael Somos, Oct 13 2016 */

{a(n) = my(w = quadgen(-8)); simplify(w^n * subst(2 * polchebyshev(n), x, -3/4*w))}; /* Michael Somos, Oct 13 2016 */

for(n=0,25,print1(round(((3+sqrt(17))/2)^n+((3-sqrt(17))/2)^n),", ")) \\ Hugo Pfoertner, Nov 19 2018

G.f.: (2-3*x)/(1-3*x-2*x^2).
a(n) = ((3-sqrt(17))^n+(3+sqrt(17))^n)/2^n.
a(n) = [x^n] ( (1 + 3*x + sqrt(1 + 6*x + 17*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
a(n) = (-2)^n * a(-n) for all n in Z. - Michael Somos, Oct 13 2016
If c = (3 + sqrt(17))/2, then c^n = (a(n) + sqrt(17)*A007482(n-1)) / 2. - Michael Somos, Oct 13 2016
E.g.f.: 2*exp(3*x/2)*cosh(sqrt(17)*x/2). - Stefano Spezia, Oct 21 2022
a(n) = 2*A007482(n)-3*A007482(n-1). - R. J. Mathar, Feb 18 2024

A124806 Number of circular n-letter words over the alphabet {0,1,2,3,4} with adjacent letters differing by at most 2.

Original entry on oeis.org

1, 5, 19, 65, 247, 955, 3733, 14649, 57583, 226505, 891219, 3507047, 13801285, 54313277, 213745019, 841177105, 3310392415, 13027820227, 51270096661, 201769982673, 794052091767, 3124938240153, 12297982928987, 48397879544975

Offset: 0

R. H. Hardin, Dec 28 2006

Empirical: a(base, n) = a(base-1, n) + A005191(n+1) for base >= 2*floor(n/2) + 1 where base is the number of letters in the alphabet.

G. C. Greubel, Table of n, a(n) for n = 0..1000
OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less
Index entries for linear recurrences with constant coefficients, signature (5,-3,-5,1,1).

Cf. A000032, A005191, A099503, A124805, A124807.

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-3*x^2-10*x^3+3*x^4+4*x^5)/((1-x-x^2)*(1-4*x+x^3)) )); // G. C. Greubel, Aug 03 2023

LinearRecurrence[{5,-3,-5,1,1}, {1,5,19,65,247,955}, 60] (* G. C. Greubel, Aug 03 2023 *)

@CachedFunction
def a(n): # a = A124806
    if (n<6): return (1,5,19,65,247,955)[n]
    else: return 5*a(n-1)-3*a(n-2)-5*a(n-3)+a(n-4)+a(n-5)
[a(n) for n in range(31)] # G. C. Greubel, Aug 03 2023

From Colin Barker, Jun 04 2017: (Start)
G.f.: (1 - 3*x^2 - 10*x^3 + 3*x^4 + 4*x^5) / ((1 - x - x^2)*(1 - 4*x + x^3)).
a(n) = 5*a(n-1) - 3*a(n-2) - 5*a(n-3) + a(n-4) + a(n-5) for n>5. (End)
a(n) = -4*[n=0] + LucasL(n-1) + 3*A099503(n) - 8*A099503(n-1). - G. C. Greubel, Aug 03 2023

A136493 Triangle of coefficients of characteristic polynomials of symmetrical pentadiagonal matrices of the type (1,-1,1,-1,1).

Original entry on oeis.org

1, -1, 1, 1, -2, 0, -1, 3, 0, 0, 1, -4, 1, 2, 0, -1, 5, -3, -5, 1, 1, 1, -6, 6, 8, -5, -2, 1, -1, 7, -10, -10, 14, 4, -4, 0, 1, -8, 15, 10, -29, -4, 12, 0, 0, -1, 9, -21, -7, 50, -4, -30, 4, 4, 0, 1, -10, 28, 0, -76, 28, 61, -20, -15, 2, 1

Offset: 0

Roger L. Bagula, Mar 21 2008

From Georg Fischer, Mar 29 2021: (Start)
The pentadiagonal matrices have 1 in the main diagonal, -1 in the first lower and upper diagonal, 1 in the second lower and upper diagonal, and 0 otherwise.
The linear recurrences that yield A124805, A124806, A124807 and similar can be derived from the rows of this triangle (the first element of a row must be removed and multiplied onto the remaining elements).
This observation extends to other sequences. For example the linear recurrence signature (5,-6,2,4,0) of A124698 "Number of base 5 circular n-digit numbers with adjacent digits differing by 1 or less" can be derived from the coefficients of the characteristic polynomial of a tridiagonal (type -1,1,-1) 5 X 5 matrix.
(End)

			Triangle begins:
   1;
  -1,   1;
   1,  -2,   0;
  -1,   3,   0,   0;
   1,  -4,   1,   2,   0;
  -1,   5,  -3,  -5,   1,  1;
   1,  -6,   6,   8,  -5, -2,   1;
  -1,   7, -10, -10,  14,  4,  -4,   0;
   1,  -8,  15,  10, -29, -4,  12,   0,   0;
  -1,   9, -21,  -7,  50, -4, -30,   4,   4,  0;
   1, -10,  28,   0, -76, 28,  61, -20, -15,  2,  1;

Anthony Ralston and Philip Rabinowitz, A First Course in Numerical Analysis, 1978, ISBN 0070511586, see p. 256.

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A011658, A087509, A124805 ff., A124696 ff., A124999 ff., A161680, A181983.

T[n_, m_]:= Piecewise[{{-1, 1+m==n || m==1+n}, {1, 2+m==n || m==n || m==2+n}}];
MO[d_]:= Table[T[n, m], {n,d}, {m,d}];
CL[n_]:= CoefficientList[CharacteristicPolynomial[MO[n], x], x];
Join[{{1}}, Table[Reverse[CL[n]], {n,10}]]//Flatten
(* For the signature of A124698 added by Georg Fischer, Mar 29 2021 : *)
Reverse[CoefficientList[CharacteristicPolynomial[{{1,-1,0,0,0}, {-1, 1,-1,0,0}, {0,-1,1,-1,0}, {0,0,-1,1,-1}, {0,0,0,-1,1}}, x], x]]

Sum_{k=1..n} T(n, k) = (-1)^(n mod 3) * A087509(n+1) + [n=1].
From G. C. Greubel, Aug 01 2023: (Start)
T(n, n) = A011658(n+2).
T(n, 1) = (-1)^(n-1).
T(n, 2) = A181983(n-1).
T(n, 3) = (-1)^(n-3)*A161680(n-3). (End)

Edited by Georg Fischer, Mar 29 2021

cp's OEIS Frontend

A285280 Array read by antidiagonals: T(m,n) = number of m-ary words of length n with cyclically adjacent elements differing by 2 or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A206776 a(n) = 3*a(n-1) + 2*a(n-2) for n>1, a(0)=2, a(1)=3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

Formula

A124806 Number of circular n-letter words over the alphabet {0,1,2,3,4} with adjacent letters differing by at most 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A136493 Triangle of coefficients of characteristic polynomials of symmetrical pentadiagonal matrices of the type (1,-1,1,-1,1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A206776 a(n) = 3a(n-1) + 2a(n-2) for n>1, a(0)=2, a(1)=3.