A124807 -id:A124807 - 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(); );

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

A364705 Expansion of 1/(1 - 4*x - x^2 + x^3).

Original entry on oeis.org

1, 4, 17, 71, 297, 1242, 5194, 21721, 90836, 379871, 1588599, 6643431, 27782452, 116184640, 485877581, 2031912512, 8497342989, 35535406887, 148607058025, 621466295998, 2598936835130, 10868606578493, 45451896853104, 190077257155779, 794892318897727, 3324194635893583

Offset: 0

G. C. Greubel, Aug 04 2023

nonn

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

Cf. A124807, A126393.

I:=[1,4,17]; [n le 3 select I[n] else 4*Self(n-1) +Self(n-2) -Self(n-3): n in [1..41]];

LinearRecurrence[{4,1,-1}, {1,4,17}, 41]

@CachedFunction
def a(n): # a = A364705
    if (n<3): return (1,4,17)[n]
    else: return 4*a(n-1) +a(n-2) -a(n-3)
[a(n) for n in range(41)]

G.f.: 1/(1 - 4*x - x^2 + x^3).
a(n) = 4*a(n-1) + a(n-2) - a(n-3).
a(n) = Sum_{k=0..n} Sum_{j=0..k} binomial(n-k, j)*binomial(n-k, k-j)*4^(n-2*k)*((1-sqrt(17))/2)^(k-j)*((1+sqrt(17))/2)^j.

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

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

A364705 Expansion of 1/(1 - 4*x - x^2 + x^3).

Views

Author

Keywords

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