A126393 -id:A126393 - cp's OEIS frontend

A126501 Number of n-tuples of numbers [0..5] (leading zeros allowed) in which adjacent digits differ by 4 or less.

1, 6, 34, 194, 1106, 6306, 35954, 204994, 1168786, 6663906, 37994674, 216628994, 1235123666, 7042134306, 40151166194, 228924368194, 1305226505746, 7441830001506, 42430056030514, 241917600158594, 1379308224915026

Offset: 0

R. H. Hardin, Dec 28 2006

For n>=1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,...,5} containing no subwords 00 and 11. - Milan Janjic, Jan 31 2015

See PARI script for proof of g.f. - Andrew Howroyd, Apr 15 2017

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

Cf. Base 6 differing by three or less A126474, two or less A126393, one or less A126360.

LinearRecurrence[{5, 4}, {1, 6}, 21] (* Jean-François Alcover, Oct 07 2017 *)

\\ Proof of generating function
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*TransferGf(m, i->1, (i,j)->abs(i-j)<=d, j->1, z);
print(RowGf(4,6,x)); \\ Andrew Howroyd, Apr 15 2017

[Empirical] a(base,n) = a(base-1,n)+9^(n-1) for base>=4n-3; a(base,n) = a(base-1,n)+9^(n-1)-2 when base=4n-4.
From Philippe Deléham, Mar 24 2012: (Start)
G.f.: (1+x)/(1-5*x-4*x^2).
a(n) = 5*a(n-1) + 4*a(n-2), a(0) = 1, a(1) = 6.
a(n) = Sum_{k, 0<=k<=n} A054458(n,k)*3^k. (End)
Conjecture: a(n) = (2^(-1-n)*((5-sqrt(41))^n*(-7+sqrt(41)) + (5+sqrt(41))^n*(7+sqrt(41)))) / sqrt(41). - Colin Barker, Jan 20 2017

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.

A126474 Number of arrays in [1..6]^n with adjacent elements differing by three or less.

Original entry on oeis.org

1, 6, 30, 154, 788, 4034, 20650, 105708, 541122, 2770018, 14179796, 72586754, 371573530, 1902094812, 9736874082, 49843318162, 255149275268, 1306115946338, 6686042370634, 34226029248972, 175203956722818

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

Original name: Number of base 6 n-digit numbers with adjacent digits differing by three or less.

			For n=2 the a(2)=30 solutions are [1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 3], [6, 4], [6, 5], [6, 6]. - _Robert Israel_, Jan 23 2018

Robert Israel, Table of n, a(n) for n = 0..1408

Cf. Base 6 differing by two or less A126393, one or less A126360.

f:= gfun:-rectoproc({a(n) = 5*a(n-1) + a(n-2) - 2*a(n-3),a(0)=1,a(1)=6,a(2)=30},a(n),remember):
map(f, [$0..30]); # Robert Israel, Jan 23 2018

Conjectures from Colin Barker, Jan 20 2017: (Start)
a(n) = 5*a(n-1) + a(n-2) - 2*a(n-3) for n>2.
G.f.: (1 + x - x^2) / (1 - 5*x - x^2 + 2*x^3).
(End)
From Robert Israel, Jan 23 2018: (Start)
a(n) = e^T M^(n-1) e where e = [1,1,1,1,1,1]^T and M is the 6 X 6 matrix with entries M(i,j) = 1 if |i-j|<=3, 0 otherwise.
The fact that (M^3-5*M^2-M+2I) e = 0 implies Colin Barker's recursion, and the G.f. follows. (End)

cp's OEIS Frontend

A126501 Number of n-tuples of numbers [0..5] (leading zeros allowed) in which adjacent digits differ by 4 or less.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A126474 Number of arrays in [1..6]^n with adjacent elements differing by three or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula